Linked Lists in Data Structure Using Python

In this article we are going to discuss the linked list. A linked list is one of the most common data structures. Before moving to linked lists we will talk about arrays. An array is a contiguous data structure. Suppose we have created an array, arr=[1,2,3], the value of 1,2,3 will be stored continuously in the memory. But on the other hand, linked lists do not store data in contiguous memory.

A linked list is a linear data structure. It is also called self-referential data structure or un-ordered implementation list (in other words, array). In the linked list we see that random data values are linked with each other through a reference that is called a pointer. There is a requirement of maintaining contiguous memory allocation.

In order to make the linked list we must maintain the memory pointer address for each link. Suppose we have a head node which contains the address of the next data point and this will keep going at the end node; there is no reference so it is called tail node.

Node Class:

Before moving to linked lists you have to create a node class. The node class is inserted in the linked list.

Like our human body made of millions of cells, a linked list is made of a number of nodes which are connected with each other. A node of a linked list has two things in it. One is data value, and the other is reference to the next node. To construct the node you must assign the node data value.

Nodes must be assigned data values, called the head node.

1
2
3
4
class Node:
  def __init__(self, data):
  self.data = data
self.next = None

Creating a Linked List:

Above we see the node class. Now we will merge all the node classes to form a linked list, using various methods. Initially the linked list contains the head node. This is referenced as the start node/first node of the linked list.

1
2
3
class Linked_List:
  def __init__(self):
  self.head = None

Below, we will create one complete linked list using all the functions of node class and linked list class.

1
2
3
4
5
6
7
class Linked_List:
  def __init__(self):
  self.head = None
def add(self, data):
  node = Node(data)
node.next = self.head
self.head = node

Traversing a Linked List:

Linked list traversal is the process of visiting each node of the linked list. We do it by making the start pointer refer as temp start from the head of the linked list. We visit each node and keep updating the temp pointer to the next node.

Traversing the linked list is a very useful technique which we use to print, size, add, delete, or update any value inside the linked list.

1
2
3
4
5
6
7
def traverse(head):
  temp = head
if head is None:
  print('empty linked list')
while temp is not none:
  print(temp.data)
temp = temp.next

Adding Elements in a Linked List:

There are many locations to insert elements in the linked list, like the beginning, end, or any position in the linked list.

Insert at Beginning:

This is the basic way to insert an item in the linked list. In this method we make a node object calling the node class n. Now we reference the next of this node object to the previous head of the linked list; now the new head of the linked list will be the current node object. You can see this in the code below.

1
2
3
4
def insert_at_begining(self, data):
  node = Node(data)
node.next = self.head
self.head = node

Adding Elements at the End of a Linked List:

In this function, the value will be inserted at the end of the linked list. This is a time-consuming process because we will traverse the complete linked list. As we reach the tail of the linked list, we will insert the node at the final position. Like before, here also we will make the node object of the node class and make the temp pointer for traversing the linked list. When we reach the end of the linked list we will stop traversing. Assign the reference of the tail of the linked list to the above created node object.

1
2
3
4
5
6
7
8
9
def insert_at_end(self, data):
  node = Node(data)
if self.head is None:
  self.head = node
return
temp = self.head
while temp.next is not None:
  temp = temp.next
temp.next = node

Insert Value at Any Position:

Using the same approach as above we will traverse the linked list to reach the desired position, then we stop traversing the linked list. Like before, here I also make the node object using node class. Using the pointer approach discussed above, we will merge values into it.

1
2
3
4
5
6
7
8
9
10
11
12
def insert_any_position(self, x, data):
  temp = self.head
while temp is not None:
  if temp.data == x:
  break
temp = temp.next
if temp is None:
  print("item not in linked list")
else:
  node = Node(data)
node.next = temp.next
temp.next = node

Now that we have reviewed insertion, we will learn how to remove an element from the linked list.

Delete Node in the Linked List:

Deletion in the linked list is like losing a pointer/reference of the particular node which you want to delete. Suppose we want to delete any value in the linked list which contains the pointer1 reference to the next pointer2. Now we will remove the reference of the pointer.

1
2
3
4
5
6
7
8
def delete_end(self):
  if self.head is None:
  print("list is empty")
return
temp = self.head
while temp.next.next is not None:
  temp = temp.next
temp.next = None

Reverse the Linked List:

For reversing the linked list we must keep the three variables, like current, next, and previous. This is for storing the address during any traversal. The previous variable will store the address of the previous node. The next variable will store the address of the next node. And the current is for storing the address of the current situation.

We will use a while loop for traversing the complete linked list. Make the current variable storing the reference of the head. Here are three basic steps you will need to keep in mind.

1. Store the value of head of linked list;

2. Current pointing to next node will store in next variable;

3. Update the current pointer to previous pointer which contains the none value;

4. Now previous will store reference of current pointer.

After the end of the loop, previous point to last of the node.

1
2
3
4
5
6
7
8
def reverse(head):
  current = head
prev = None
while current.next is not None:
  next = current.next
current.next = prev
prev = current
current = next