What is a Singly Linked list ⛓️⛓️...?
Simply put, a singly Linked List can be defined as a collection of nodes where each node consists of two parts --> a data value and a pointer that points to the next node in the list.
- Graphical Illustration of a node 🍃🍃in a Linked List:
We use the term "Head" to define the first node in the Linked List. If the list is empty, the head points to NULL !!
- Graphical Illustration of a Singly Linked List:
How to Create a Singly Linked List 🤔🤔!!
Since Linked List consists of nodes, we need to make a class that represents the instance of a node.
- I will be using Python 🐍 for this blog. If you aren't familiar with Python, I will try my best to be a lot more explanative at every point.
Node Representation
class Node:
data = None
next_node = None
def __init__(self, data):
self.data = data
def __repr__(self):
return "<Node Data: %s>" % self.data
- The class "Node" helps us to create an object for storing a single node of a linked list. It models two attributes - data and the link to the next node in the List.
- Python repr Function returns a printable representation of an object in Python.
- The init method lets the class initialize the object's attributes and serves no other purpose.
- The self in Python represents the instance of the class. By using the “self”, we can access the attributes and methods of the class in python.
Now, since we have a class "Node" to model each node of the Linked List, we can actually move one step up the Ladder and start creating our very first Singly Linked List.
class LinkedList:
head = None
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def __repr__(self):
return "I am a Linked List"
In the above code snippet, we just declared a class named "LinkedList", added an attribute named "head" and coded a few methods to get started.
init will initialize the head of the Linked List to None. A practice that we follow to set attributes to a safe state.
isEmpty() function checks if the list is empty. It does so by comparing "head" to "None"
We have coded a repr function to return a statement just so that when we issue the name of the Linked List, we get something back to the screen. We will update it later!!
Okay, so now, since we have configured our Linked List class and have coded a few methods, why don't we test them? huh.
I am using an online Python Interpreter by Programiz to test my Code.
- What goes in the above Testing..?
- I just declared a variable "wordle" and made it an instance of the class "LinkedList"
- Next, I just wrote 'wordle' and pressed ENTER KEY and my repr function gets executed and I get to see "I am a Linked List" on the Screen.
- Lastly, I just test my isEmpty() function which returns "True" since we don't have anything inside our Linked List "wordle".
Now, let's do some Insertions 🔨🔨!!
We will break the insertion process into three parts
- Inserting a new node at the beginning of the list
- Inserting a new node at the end of the list
- Inserting a new node at any position in the list
Inserting a New Node at the beginning of the Linked List!!
We will start off by inserting a New Node at the beginning of the Linked List!!
- We will call this method "push".
- This method ADDs a new Node containing data at the head of the list
def push(self, data): // 1. Using new Data, create an instance of a new node new_node = Node(data) // 2. Assign the "next_node" property of "new_node" to current head of the Linked List new_node.next_node = self.head // 3. Move the "head" property of the Linked List to point to the new_node self.head = new_node
def __repr__(self):
nodes = []
current = self.head
while current:
if current is self.head:
nodes.append("[Head: %s]" % current.data)
elif current.next_node is None:
nodes.append("[Tail: %s]" % current.data)
else:
nodes.append("[%s]" % current.data)
current = current.next_node
return '->'.join(nodes)
WHAT we did in the above code snippet 🤷♂️🤷♂️..?
- We declared an array "nodes" and then a variable "current" and set its value to the current head of the Linked List.
- "while current" is equals to "while current != None". This will make sure that we iterate over the whole Linked List
- Inside the while loop, we have an if-elif-else construct. After every iteration, we are moving to next node in our list using "current = current.next_node"
- After exiting while loop, return '->'.join(nodes) will return all the elements of the array "node" joined together with this "->" symbol for a nice representation!!
- Since we are updating repr, let's include one more functionality to see the size of our Linked list
def size(self):
count = 0
current = self.head
while current:
count = count+1
current = current.next_node
return count
In the above code snippet:
- We declared a variable "count" and set its value to 0. Declared another variable "current" and set its value to the current Head of our Linked List.
- Then we start a while loop that will keeping iterating until we reach the end of the loop.
- We each iteration, we are incrementing the value of the count. Therefore, when we exit the while loop, we have a value of count set exactly to a number of nodes in our list.
- At last, we return the count variable.
That was so much coding 😩!! I know, so for a break, why don't we do some TESTING 📋📋..?
- What goes in the above Testing..?
- I just declared a variable "wordle" that is an instance of the class "LinkedList"
- Now, I called the push method three times on the wordle object, each time with a different value.
- Next, I just wrote 'wordle' and pressed ENTER KEY and my repr function gets executed and I get to see a beautiful representation of our Linked List on the Screen.
Inserting a New Node at the end of the Linked List!!
Now, let's make another insert function that will Insert a New Node at the end of the Linked List!!
- We will call this method "append".
- This method ADDs a new Node containing data at the end of the list
def append(self, data):
// 1. Using new Data, create an instance of a new node
new_node = Node(data)
// 2. Check if the list is empty, if so make a new node as head of the list
if self.head is None:
self.head = new_node
return
//3. Else, traverse through the list until you get to the last node
current = self.head
// while current.next_node!=None: is same as while current.next_node:
while current.next_node:
current = current.next_node
// 4. Change the "next_node" property of the last node
current.next_node = new_node
🛎️🛎️Important - Why did we use this logic..?
while current.next_node:
current = current.next_node
Because we know that whatever the last node will be in the Linked List, its "next_node" property will point to the "None". We will be using this logic a lot in the coming methods that we design!!
Inserting a new node containing data at any position in the list
- We will call this method "insert".
- This method ADDs a new Node containing data at the position specified in the function call!!
- We will break this function into 4 cases:
- position is 1 i.e., at the beginning of the list
- position is one offset more than the size of the list. For instance, if the size of the list is 5 and the value of the position is 6. It means --> to insert at the end of the list
- position is out of bounds
- Neither at the beginning nor at the end --> means anywhere in the middle!!
def insert(self, position, data):
// 1. if position is 0, which basically means to insert a new node at the beginning of the list
if position == 1:
self.push(data)
// 2. if position is just one offset more than length of the list, which basically means to insert a new node at the end of the list
elif position == self.size()+1:
self.append(data)
// 3. In case, the position entered is out of Bound, we will raise an exception
elif position > self.size()+1 or position < 0:
raise Exception(
"Position entered is out of Bounds of the Linked List Size!!")
// 4. position is anywhere in the middle
else:
index = 1
current = self.head
new_node = Node(data)
while index < position-1:
current = current.next_node
index += 1
prev_node = current
next_node = current.next_node
prev_node.next_node = new_node
new_node.next_node = next_node
Now, since we have made all the required insert methods. I think we can do some testing on them. In the testing below, all I did is declared a variable "wordle" and made it an instance of the class "LinkedList". Then I used all three types of insertion methods that we designed. After every function call, I am just writing "wordle" and pressing "ENTER - KEY" that calls my "repr" function and we get to see a beautiful representation of our Linked list.
Now, since we have learned how to insert nodes into a Linked list, we can officially design a method to remove the existing nodes in a Linked List.
If you have the same question, we got you covered 😉😉!!
Removing a node at any position in the list:
- We will call this method "remove".
- This method removes an existing Node containing data at the position specified in the function call!!
def remove(self, position):
// 1. if position is out of bounds!!
if position > self.size() or position < 1:
raise Exception(
"Position entered is out of Bounds of the Linked List Size!!")
// 2. If position is 1, which basically means to remove the node at the beginning of the list
elif (position == 1):
current = self.head
self.head = current.next_node
// 3.
else:
index = 1
previous = None
current = self.head
while current and index < position:
previous = current
current = current.next_node
index += 1
previous.next_node = current.next_node
current.next_node = None
Let's test this "remove" method that we just designed!! In the testing below, I started off as usual by creating an instance of the class "LinkedList" named "wordle". Then we added few values to it using "push" method.
Now, we test our remove method by removing from different positions. You will notice that we get an error/exception when we try to remove from position 7 since our Linked List at that point consist of just two nodes.
Looking up any Node at any position in the list:
Let's wrap this Blog up by adding one last functionality to Linked List that will help us to look up any Node in our List.
- We will name this function "lookup"🤓🤓.
- It will return us the node located at the position specified in the function call
def lookUp(self, position):
// 1. If position is 1, it basically means we need to return the head of the linked list
if position == 1:
return self.head
// 2. If position is equals to the size of the list, we need to return the last node in the list
elif position == self.size():
// traverse through the list until you get to the last node
current = self.head
while current.next_node:
current = current.next_node
return current
// 3. if position entered is out of bounds!!
elif position > self.size() or position < 0:
raise Exception(
"Position entered is out of Bounds of the Linked List Size!!")
// 4. If node looking up is anywhere in the between
else:
index = 1
current = self.head
while index < position:
current = current.next_node
index += 1
return current
Here is the Entire code that we designed until now:
class Node:
data = None
next_node = None
def __init__(self, data):
self.data = data
def __repr__(self):
return "<Node Data: %s>" % self.data
class LinkedList:
head = None
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def size(self):
count = 0
current = self.head
while current:
count = count+1
current = current.next_node
return count
def push(self, data):
new_node = Node(data)
new_node.next_node = self.head
self.head = new_node
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current = self.head
while current.next_node:
current = current.next_node
current.next_node = new_node
def lookUp(self, position):
if position == 1:
return self.head
elif position == self.size():
current = self.head
while current.next_node:
current = current.next_node
return current
elif position > self.size() or position < 0:
raise Exception(
"Position entered is out of Bounds of the Linked List Size!!")
else:
index = 1
current = self.head
while index < position:
current = current.next_node
index += 1
return current
def remove(self, position):
if position > self.size() or position < 1:
raise Exception(
"Position entered is out of Bounds of the Linked List Size!!")
elif (position == 1):
current = self.head
self.head = current.next_node
else:
index = 1
previous = None
current = self.head
while current and index < position:
previous = current
current = current.next_node
index += 1
previous.next_node = current.next_node
current.next_node = None
def insert(self, position, data):
if position == 1:
self.push(data)
elif position == self.size()+1:
self.append(data)
elif position > self.size()+1 or position < 0:
raise Exception(
"Position entered is out of Bounds of the Linked List Size!!")
else:
index = 1
current = self.head
new_node = Node(data)
while index < position-1:
current = current.next_node
index += 1
prev_node = current
next_node = current.next_node
prev_node.next_node = new_node
new_node.next_node = next_node
def __repr__(self):
nodes = []
current = self.head
while current:
if current is self.head:
nodes.append("[Head: %s]" % current.data)
elif current.next_node is None:
nodes.append("[Tail: %s]" % current.data)
else:
nodes.append("[%s]" % current.data)
current = current.next_node
return '->'.join(nodes)
FINAL TESTING 🖥️🖥️!!
- We tested all the methods that we designed. Hopefully, this blog would get you started with Singly Linked List Data Structure.
I publish a new blog every single week. Lol 😂, this is my first blog. Well, I will try to write one every single week. Nevertheless, I am always working on some cool Projects. So feel free to follow me on these platforms:
©️ Hamit Sehjal 2022