Linked Lists for Beginners

What are linked lists?

Linked list simply is a sequence of data nodes where each node points to another node. The starting node of the linked list is called the head node. Each node has a data value and a pointer that references the node next to it. So basically, we just have to know the head node of a linked list to access any of its elements.

How is a linked list different from an array?

Array is a collection of elements that are stored in contiguous memory locations, whereas nodes in a linked list can be stored at different memory locations as shown in the figure above. We can directly access any element of an array through its index, in contrast to that, linked list must be traversed from the head node in order to access a particular node. Having said that, inserting/deleting new elements is much easier in linked lists because in arrays, inserting or deleting an element causes a part of the array to shift. Arrays are static i.e creating an array means that you’re reserving some fixed part of the computer memory which might not be enough sometimes and may go unused sometimes. Linked lists are dynamic in nature, meaning that the nodes can be created at random memory locations, anywhere and anytime from the pool of our computer’s unused memory. However, the nodes in linked list require extra memory space to hold the values of pointer to the next. Hence, linked lists are better utilizers of memory but are costlier when it comes to accessing a particular node.

Traversing a linked list:

A linked list is characterized just by its head node. We can traverse the linked list accessing the next pointer of each node, starting from the head node and continuously looping until we find the node which points to nothing i.e whose next= NULL. It’s like reaching an address through several stations where each station has an address to another station and this process would finally lead you to your final destination.

Inserting/Deleting in Linked lists:

Assume that we’re inserting a node between the second and third node.

• Find the 2nd node i.e traverse the list until you find the second node.
• Create a new node. Here, a new node is created dynamically at a random memory location, let’s say 40020.
• Initially the next of the second node was pointing to the third node. Now the second node’s next should point to the newly created memory location i.e. 40020.
• The next of the newly created node should point to the third node i.e. 300010.

Deleting a node can be done in a similar way.

Implementing a linked list using Python:

class node : 
 def __init__(self, value=None):
  self.value=value 
  self.next=None
#lets make our own linked list 
class MyLinkedList:
 def __init__(self):
  self.head=None
 #This is to check if the linked list is empty.
 def is_Empty(self):
  if self.head==None:
   return True
 else:
   return False
#This is to add a new nodes to our linked list
 def add_node(self,data): 
  new_node= node(data) 
  if self.is_Empty():
   self.head=new_node 
  else:
   tmp_node=self.head 
   while (tmp_node.next): 
    tmp_node=tmp_node.next
   tmp_node.next=new_node 
  def add_begining(self,data):
   new_node=node(data)
   if self.is_Empty():
    self.head=new_node
   else:
    start_node=self.head
    self.head=new_node
    new_node.next=start_node
  def show_list(self):
   start=self.head 
   while start is not None:
    print(start.value)
    start=start.next
my_list = MyLinkedList() 
my_list.add_node(4)
my_list.add_node(3)
my_list.add_begining(1)
my_list.add_begining(2)
my_list.show_list()

Implementing linked lists with python will also help you better understand the concepts of OOP. You’ll learn how we can make our own class, create our own objects and how these objects invoke the class functions. I’ll be explaining every part of the code for your convenience.

Lets start…

class node :
 def __init__(self, value=None):
  self.value=value
  self.next=None

The class node is defined to have two attributes : a value, which holds the actual value of the node and a next, which holds the reference/pointer to its next node. The __init__() function is called the constructor and is automatically called when any object of class node is created. This function initializes the attributes of the created node. Whenever any node is created, it is independent until we add it to a list, that’s why we’re initializing it’s next to null. The self parameter in the function is the pointer of the object that is invoking the function.

class MyLinkedList:
 def __init__(self):
  self.head=None
#This is to check if the linked list is empty.
 def is_Empty(self):
  if self.head==None:
   return True
 else:
   return False
#This is to add a new nodes to our linked list
 def add_node(self,data): 
  new_node= node(data) 
  if self.is_Empty():
   self.head=new_node 
  else:
   tmp_node=self.head 
   while (tmp_node.next): 
    tmp_node=tmp_node.next
   tmp_node.next=new_node
def add_begining(self,data):
   new_node=node(data)
   if self.is_Empty():
    self.head=new_node
   else:
    start_node=self.head
    self.head=new_node
    new_node.next=start_node
def show_list(self):
   start=self.head 
   while start is not None:
    print(start.value)
    start=start.next

The __init__() function is called when any object of class MyLinkedList is created. The class we defined above i.e the node is for creating nodes whereas the class MyLinkedList is for creating a linked list where the node objects can be added to form a list. As said before, just a head is enough for a linked list to characterize itself, meaning that all the nodes in a list can be accessed if we know the head node. Whenever an object of MyLinkedList is created (whenever __init__() is called ), an empty list is created with the head pointing to null.

The function is_Empty() returns True if the list is empty else returns False. When the list is initialized, its head is set to null meaning that the head is not a node but nothing. If no nodes have been added to the list then, the head must be null.

The function add_node() is for adding a new node at the end of the list. There might be two conditions : either we’re adding to an empty node or we’re adding a new node at the end of a non empty list. If the list is empty, then we have to make the new node as the head of the list. If the list is not empty then we have to traverse to the end node of the list and then add the new node to it.

my_list = MyLinkedList() 
my_list.add_node(4)
my_list.add_node(3)
my_list.add_begining(1)
my_list.add_begining(2)
my_list.show_list()

Here, my_list is an object of class MyLinkedList, which invokes the __init__() function of the class and initializes its head to null. Similarly, the object my_list invokes the add_node() function and a node is added to the list. The list can be printed out using the show_list() function.

Thanks for reading!