How to implement Linked List Data Structure Using Python

Last updated: September 13, 2024 By Sunil Shaw

Introduction to Linked Lists

The linked list is a linear structure that consists of elements such that each element is an individual object and contains information regarding. So let’s How to implement Linked List Data Structure Using Python.

In linked list, we call each element a node.

So you can see in the diagram, the reference to the first node is called Head. It is the entry point of the linked list. If the list is empty, then the head points to null. The last node of the linked list refers to null.

As you can increase or decrease the number of nodes as per requirement, people consider linked list to be dynamic data structures. However, in a linked list, direct access to data is not possible. Search for any item starts from the head, and you will have to go through each reference to get that item. A linked list occupies more memory.

The linked list described above is called a singly linked list. So there is one more type of linked list known as doubly linked list. A double linked list has the reference to the next node and the previous node.

Implementation of Node Class

In this section, we will learn how to implement a Node class. A Node contains

Data
Reference to the next node

Process involved: To create a node object, we pass data value to the constructor. The constructor assigns the data value to data, and sets node’s reference to None. We create all the objects, then assign the memory address of the second objects as the reference to the first node, the memory address of the third object as the reference to the second object, and so on. The last object, thus have no (or none as) reference.

The code for the Node class will be as follows:

Code

class Node:
    def __init__(self,data = None):
        self.data = data
        self.reference = None

Execution

    #Driver Code
    objNode1 = Node(1)
    objNode2 = Node(2)
    objNode3 = Node(3)
    objNode4 = Node(4)

    objNode1.reference = objNode2
    objNode2.reference = objNode3
    objNode3.reference = objNode4
    objNode4.reference = None

    print("DATA VALUE =", objNode1.data, "REFERENCE = ",objNode1.reference)
    print("DATA VALUE =", objNode2.data, "REFERENCE = ",objNode2.reference)
    print("DATA VALUE =", objNode3.data, "REFERENCE = ",objNode3.reference)
    print("DATA VALUE =", objNode4.data, "REFERENCE = ",objNode4.reference)

Final Code

class Node:
    def __init__(self,data = None):
        self.data = data
        self.reference = None


    #Execution
    objNode1 = Node(1)
    objNode2 = Node(2)
    objNode3 = Node(3)
    objNode4 = Node(4)

    objNode1.reference = objNode2
    objNode2.reference = objNode3
    objNode3.reference = objNode4
    objNode4.reference = None

    print("DATA VALUE =", objNode1.data, "REFERENCE = ",objNode1.reference)
    print("DATA VALUE =", objNode2.data, "REFERENCE = ",objNode2.reference)
    print("DATA VALUE =", objNode3.data, "REFERENCE = ",objNode3.reference)
    print("DATA VALUE =", objNode4.data, "REFERENCE = ",objNode4.reference)

How to Add a Node at the beginning of a linked list

We will add a new method to insert a node at the beginning of a linked lists in the same code mentioned in the last example.

In the last example, we pointed the head of the linked list object to the first node object.

linkObj.head = objNode1

When we add the node at the beginning, we just have to make the linkObj.head = new_node and New node.reference = obj_Node1

For this, we write a code where, the value of the linkObj.head is first passed on to new node.refernce and then linkObj.head is set to the new node object.

    def insert_at_Beginning(self, data):
        new_data = Node(data)
        new_data.reference = self.head
        self.head = new_data

So, the full code would be as follows

Code

class Node:
    def __init__(self, data = None):
        self.data = data
        self.reference = None


class Linked_list:
    def __init__(self):
        self.head = None

    def traverse(self):
        presentNode = self.head
        while presentNode:
            print("DATA VALUE =", presentNode.data)
            presentNode = presentNode.reference

    def insert_at_Beginning(self, data):
        new_data = Node(data)
        new_data.reference = self.head
        self.head = new_data

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)

linkObj = Linked_list()
# head of the linked list to first object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj.insert_at_Beginning(5)
linkObj.traverse()

to be continue

How to add a Node at the end of a linked list

In order to add a node at the end of the linked list, it is important that you point the reference of the last node to the new node that you create.

Step 1: Define the function

def insert_at_end(self,data):

Step 2: Create a new Node object

new_data = Node(data)

Step 3: Traverse through the linked list to reach the last node

Remeber that you cannot directly access the last node in the linked list. You will have to traverse through all the nodes and reach th elast node in order to take the next step.

presentNode = self.head
		while presentNode.reference != None:
			presentNode = presentNode.reference

Step 4: Add the new node at the end

After traversing through the linked list, you know that you have reached the last node when presentNode.reference = None. Since this won’t remain, the last node anymore, you need to do the following:

presentNode.reference = new_data

with this we have added a new node at the end of a linked list.

Code

class Node:
	def __init__(self, data = None):
		self.data = data
		self.reference = None


class Linked_list:
	def __init__(self):
		self.head = None

	def traverse(self):
		presentNode = self.head
		while presentNode:
			print("DATA VALUE = ",presentNode.data)
			presentNode = presentNode.reference

	def insert_at_end(self,data):
		new_data = Node(data)
		presentNode = self.head
		while presentNode.reference != None:
			presentNode = presentNode.reference
		presentNode.reference = new_data

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
linkObj = Linked_list()

#head of the linked list to first object
linkObj.head = objNode1

# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4

linkObj.insert_at_end(5)
linkObj.insert_at_end(6)
linkObj.insert_at_end(7)

linkObj.traverse()

Output

DATA VALUE =  1
DATA VALUE =  2
DATA VALUE =  3
DATA VALUE =  4
DATA VALUE =  5
DATA VALUE =  6
DATA VALUE =  7
[Finished in 10ms]

Inserting a node between two nodes in a linked list

The solution for this problem is very similar to adding a node to the beginning. The only differenceis that when we add a node at the beginning we point the head value to the new node, whereas in this case, the function will take take two parameters. First will be the node object. Once the new node is created, we pass on the reference value stored in the existing node object to it and the existing node is then made to point at the new node object.

Step 1: Define the functions

This function will take two parameters:

The code object after which the data is to be inserted
Data for the new node object.

def insert_at_middle(self, insert_data, new_data):

Step 2: Assign references

new_node = Node(new_data)
		new_node.reference = insert_data.reference
		insert_data.reference = new_node

Code

class Node:
	def __init__(self, data = None):
		self.data = data
		self.reference = None


class Linked_list:
	def __init__(self):
		self.head = None

	def traverse(self):
		presentNode = self.head
		while presentNode:
			print("DATA VALUE = ",presentNode.data)
			presentNode = presentNode.reference


	def insert_at_middle(self, insert_data, new_data):
		new_node = Node(new_data)
		new_node.reference = insert_data.reference
		insert_data.reference = new_node

Execution

# Execution
objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)

linkObj = Linked_list()

# head of the linked list to first object
linkObj.head = objNode1

# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj.insert_at_middle(objNode3, 8)
linkObj.traverse()

Output

DATA VALUE =  1
DATA VALUE =  2
DATA VALUE =  3
DATA VALUE =  8
DATA VALUE =  4
[Finished in 11ms]

Removing a node from a linked list

Suppose, we have a linked list as follow

A -> B -> C

A. reference = B

B. reference = C

C. reference = A

To remove B, we traverse through the linked list. When we reach node A that has reference pointing to B, we replace that value with the reference value stored in B(that points to C). So that will make A point to C and B is removed from the chain.

The function code will be as follows:

	def remove(self, removeObj):
		presentNode = self.head
		while presentNode:
			if(presentNode.reference == removeObj):
				presentNode.reference = removeObj.reference
			presentNode = presentNode.reference

The function takes the Nodes object as a parameter and traverses the linked list until it reaches the object that it needs to remove. We simply change the reference value to the reference value stored in the object removeObj, so the node now points directly to the node after the removeObj.

class Node:
	def __init__(self, data = None):
		self.data = data
		self.reference = None

class Linked_list:
	def __init__(self):
		self.head = None

	def traverse(self):
		presentNode = self.head
		while presentNode:
			print("DATA VALUE = ",presentNode.data)
			presentNode = presentNode.reference


	def remove(self, removeObj):
		presentNode = self.head
		while presentNode:
			if(presentNode.reference == removeObj):
				presentNode.reference = removeObj.reference
			presentNode = presentNode.reference

Execution

# Execution
objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)

linkObj = Linked_list()

# head of the linked list to first object
linkObj.head = objNode1

# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj.remove(objNode2)
linkObj.traverse()

Output

DATA VALUE =  1
DATA VALUE =  3
DATA VALUE =  4
[Finished in 16ms]

Printing the values of the node in the centre of a linked list

Printing the values of the node in the centre of a linked list involves counting the number of nodes in the object. If the length is even, print the data of the two nodes in the middle; otherwise, print only the data of the nodes in the center.

Step 1: Define he function

	def find_middle(self, list):

Step 2: Find the length of the counter

Here, we set a variable counter = 0. As we traverse through the linked list we increment the counter. At the end of the while loop we get the count of number of nodes in the linked list. This is also the length of the linked list.

counter = 0
		presentNode = self.head
		while presentNode:
			presentNode = presentNode.reference
			counter = counter + 1
		print("size of linked list = ", counter)

Step 3: Reach the middle of the linked list

The node before the middle stores the reference to the middle nodes. So, in the for loop instead of iterating(counter/2) times, we iterate (counter-1/2) times. This brings us to the nodes placed just before the center value.

presentNode = self.head


		for i in range((counter-1)//2):
			presentNode = presentNode.reference

Step 4: Display the result depending on whether the number of nodes in the linked list

If the linked list has even number of nodes then print the value of reference stored in the present node and the next node.

if (counter%2 == 0):
				nextNode = presentNode.reference
				print("Since the length of Linked list is an even number the two middle elements are:")
				print(presentNode.data, nextNode.data)

Else, print the value of the present node.

else:
				print("Since the length of the linked list is an odd number, the middle element is:")
				print(presentNode.data)

Code

class Node:
	def __init__(self, data = None):
		self.data = data
		self.reference = None

class Linked_list:
	def __init__(self):
		self.head = None

	def find_middle(self, list):
		counter = 0
		presentNode = self.head
		while presentNode:
			presentNode = presentNode.reference
			counter = counter + 1
		print("size of linked list = ", counter)
		presentNode = self.head


		for i in range((counter-1)//2):
			presentNode = presentNode.reference
			if (counter%2 == 0):
				nextNode = presentNode.reference
				print("Since the length of Linked list is an even number the two middle elements are:")
				print(presentNode.data, nextNode.data)
			else:
				print("Since the length of the linked list is an odd number, the middle element is:")
				print(presentNode.data)


# Execution
objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
objNode4 = Node(5)

linkObj = Linked_list()

# head of the linked list to first object
linkObj.head = objNode1

# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
objNode3.reference = objNode5

linkObj.find_middle(linkObj)

Output

size of linked list =  4
Since the length of Linked list is an even number the two middle elements are:
2 3

Implementation of doubly linked list

A doubly linked list has three parts:

Pointer to the previous node
Data
Pointer to the next node

Implementation of doubly linked list is easy. We just need to ensure that each nodes connect to the next and the previous data.

Step 1: Create a Node class

The node class will have a constructor that initializes three parameters: data, reference to next node – refNext and reference to previous node – refPrev.

class Node:
	def __init__(self, data = None):
		self.data = data
		self.refNext = None
		self.refPrev = None

Step 2: Create functions to traverse through the double linked list

Traverse Forward

To traverse forward with the help of refNext that points to the next value of the linked list. We start with the head and move on to the next node using refNext.

	def traverse(self):
		presentNode = self.head
		while presentNode:
			print("DATA VALUE = ", presentNode.data)
			presentNode = presentNode.refNext

2. Traverse Reverse

In a word traverse reverse is opposite of traverse forward. We are able to traverse backwards with the help of refPrev because it points to previous node using refPrev.

	def traverseReverse(self):
		presentNode = self.tail
		while presentNode:
			print("DATA VALUE = ",presentNode.data)
			presentNode = presentNode.refPrev

Step 3: Write a function to add a node at the end

Appending a node at the end of the doubly linked list is same as appending in linked list the only difference is that we have to ensure that the node that is appended has its refPrev poinitng to the node after which it has been added.

def append(self, data):
		new_data = Node(data)
		presentNode = self.head
		while presentNode.refNext != None:
			presentNode = presentNode.refNext
		presentNode.refNext = new_data
		new_data.refPrev = presentNode
		self.tail = new_data

Step 4: Write function to remove a node

This functiontakes the node object that needs to be removed as parameter. In order to remove a nodewe iterate through the doubly linked list twice. We first start with the head and move forward using refNext and when we encounter the object thatneeds to be removed we change the refNext value of the present node (which is presently pointing to the object that need to be removed) to the node that comes after the object that needs to be removed. We then traverse through the linked list backwards starting from tail and when we encounter the object to be removed again. We change the refPrev value of the present node to the node that is placed before it.

	def remove(self, removeObj):
		presentNode = self.head
		presentNodeTail = self.tail
		while presentNode.refNext != None:
			if(presentNode.refNext == removeObj):
				presentNode.refNext = removeObj.refNext
			presentNode = presentNode.refNext

		while presentNodeTail.refPrev != None:
			if(presentNodeTail.refPrev == removeObj):
				presentNodeTail.refPrev = removeObj.refPrev
			presentNodeTail = presentNodeTail.refPrev

Code

class Node:
	def __init__(self, data = None):
		self.data = data
		self.refNext = None
		self.refPrev = None

class dLinked_list:
	def __init__(self):
		self.head = None
		self.tail = None

	def append(self, data):
		new_data = Node(data)
		presentNode = self.head
		while presentNode.refNext != None:
			presentNode = presentNode.refNext
		presentNode.refNext = new_data
		new_data.refPrev = presentNode
		self.tail = new_data

	def traverse(self):
		presentNode = self.head
		while presentNode:
			print("DATA VALUE = ", presentNode.data)
			presentNode = presentNode.refNext


	def traverseReverse(self):
		presentNode = self.tail
		while presentNode:
			print("DATA VALUE = ",presentNode.data)
			presentNode = presentNode.refPrev

	def remove(self, removeObj):
		presentNode = self.head
		presentNodeTail = self.tail
		while presentNode.refNext != None:
			if(presentNode.refNext == removeObj):
				presentNode.refNext = removeObj.refNext
			presentNode = presentNode.refNext

		while presentNodeTail.refPrev != None:
			if(presentNodeTail.refPrev == removeObj):
				presentNodeTail.refPrev = removeObj.refPrev
			presentNodeTail = presentNodeTail.refPrev

Execution

 # Driver Code
objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
# objNode5 = Node(5)

dlinkObj = dLinked_list()

# head of the linked list to first object
dlinkObj.head = objNode1
dlinkObj.tail = objNode4

# reference of the first node object to second object
dlinkObj.head.refNext = objNode2
dlinkObj.tail.refPrev = objNode3
objNode2.refNext = objNode3
objNode3.refNext = objNode4

objNode4.refPrev = objNode3
objNode3.refPrev = objNode2
objNode2.refPrev = objNode1

print("Appending Values")
dlinkObj.append(8)
dlinkObj.append(9)
print("traversing forward after Append")

dlinkObj.traverse()
print("traversing reverse after Append")
dlinkObj.traverseReverse()
print("Removing Values")
dlinkObj.remove(objNode2)
print("traversing forward after Remove")
dlinkObj.traverse()
print("traversing reverse after Remove")
dlinkObj.traverseReverse()

Output

Appending Values
traversing forward after Append
DATA VALUE =  1
DATA VALUE =  2
DATA VALUE =  3
DATA VALUE =  4
DATA VALUE =  8
DATA VALUE =  9
traversing reverse after Append
DATA VALUE =  9
DATA VALUE =  8
DATA VALUE =  4
DATA VALUE =  3
DATA VALUE =  2
DATA VALUE =  1
Removing Values
traversing forward after Remove
DATA VALUE =  1
DATA VALUE =  3
DATA VALUE =  4
DATA VALUE =  8
DATA VALUE =  9
traversing reverse after Remove
DATA VALUE =  9
DATA VALUE =  8
DATA VALUE =  4
DATA VALUE =  3
DATA VALUE =  1

Reversing a linked list

To reverse a linked list we have to reverse the pointers. The first table shows how information is stored in the linked list. The second table shows how the parameters are initialized in the reverse() function before beginning to traverse through the list and reversing the elements.

		while nextval != None:
			presentNode.refNext = previous
			previous = presentNode
			presentNode = nextval
			nextval = nextval.refNext

		presentNode.refNext = previous
		self.head = presentNode

You can see as we iterate through the while loop how the value of presentnode.refNext change. Node1 that was earlier pointing to Node2 changes its pointer to none. Same way node2 changes its pointer value to node1, so on.

Code

class Node:
	def __init__(self, data = None):
		self.data = data
		self.refNext = None

class Linked_list:
	def __init__(self):
		self.head = None

	def reverse(self):
		previous = None
		presentNode = self.head
		nextval = presentNode.refNext
		while nextval != None:
			presentNode.refNext = previous
			previous = presentNode
			presentNode = nextval
			nextval = nextval.refNext

		presentNode.refNext = previous
		self.head = presentNode


	def traverse(self):
		presentNode = self.head
		while presentNode:
			print("DATA VALUE = ",presentNode.data)
			presentNode = presentNode.refNext

Output

traverse before reversing
DATA VALUE =  1
DATA VALUE =  2
DATA VALUE =  3
DATA VALUE =  4
traversing after reversing
DATA VALUE =  4
DATA VALUE =  3
DATA VALUE =  2
DATA VALUE =  1

Conclusions

You learned How to implement Linked List Data Structure Using Python in this articles. Python does not offer linked lists as part of its standard library. Linked list contain data elements in a sequence, and links connect these data elements to each other. One can easily remove or insert list elements in a linked list without affecting its basic structures. Also it is a dynamic data structure that can shrink or grow during runtime. However linked lists occupy more memory and traversal though a linked list can be difficult.

Implementing Queue Data Structure Algorithm in Python: A Detailed Guide