Data structures play a key role in the programming world. They help us to organize our data in a way that can be used efficiently.

In this tutorial, we are going to learn about the singly-linked list and doubly-linked list.

A linked list is a linear data structure. It doesn’t store the data in contiguous memory locations like arrays. And each element in linked is called a node and they are connected using the pointers. The first node in the linked list is called the head.

The size of the linked list is dynamic. So, we can have any number of nodes as we want unless the storage is available in the device.

There are two types of linked lists. Let’s see the detailed tutorial about them one by one.

#1. Singly Linked List

A singly linked list contains a single pointer connected to the next node in the linked list. We have to store the data and pointer for each node in the linked list.

The last node in the linked list contains null as the next pointer to represent the ending of the linked list.

You can see the illustration of a linked below.

Understanding Linked Lists Implementation in Python Development Python

Now, we have a full understanding of a singly linked list. Let’s see the steps to implement it in Python.

Singly Linked List Implementation

1. The first step is to create the node for the linked list.

How to create it?

In Python, we can easily create the node using the class. The class contains data and a pointer for the next node.

Look at the code for the node.

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

We can create the node with any type of data using the above class. We’ll see it in a bit.

Now, we have the node with us. Next, we have to create a linked list with multiple nodes. Let’s create another class for a linked list.

2. Create a class called LinkedList with head initialized to None. See the code below.

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. We have Node and LinkedList classes with us. How do we insert a new node into the linked list? A simple answer might be using a method in the LinkedList class. Yeah, that would be nice. Let’s write a method to insert a new node into the linked list.

To insert a new node into the linked list, we have to follow certain steps.

Let’s see them.

  • Check whether the head is empty or not.
  • If the head is empty, then assign the new node to the head.
  • If the head is not empty, get the last node of the linked list.
  • Assign the new node to the last node next pointer.

Let’s see the code to insert a new node in the linked list.

class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

Hurray! we have completed the method to insert a new node in the linked list. How can we access the nodes data from the linked list?

To access the data from the linked list, we have to iterate through the linked using the next pointer as we do to get the last node in the insertion method. Let’s write a method inside the LinkedList class to print all nodes data in the linked list.

4. Follow the below steps to print all nodes data in the linked list.

  • Initialize a variable with head.
  • Write a loop that iterates until we reach the end of the linked list.
    • Print the node data.
    • Move the next pointer

Let’s see the code.

class LinkedList:

	####

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')

Phew! we completed creating the linked with necessary methods. Let’s test the linked list by instantiating it with some data.

We can create the node with Node(1) code. Let’s see the complete code of the linked list implementation along with the sample usage.

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')


if __name__ == '__main__':
	## instantiating the linked list
	linked_list = LinkedList()

	## inserting the data into the linked list
	linked_list.insert(Node(1))
	linked_list.insert(Node(2))
	linked_list.insert(Node(3))
	linked_list.insert(Node(4))
	linked_list.insert(Node(5))
	linked_list.insert(Node(6))
	linked_list.insert(Node(7))

	## printing the linked list
	linked_list.display()

Run the above program to get the following result.

1->2->3->4->5->6->7->Null

That’s it for the linked list. Now, you know how to implement a singly-linked list. You can easily implement the doubly-linked list with the knowledge of the singly-linked list. Let’s dive into the next section of the tutorial.

#2. Doubly Linked List

A double-linked list contains two pointers connected to the previous node and the next node in the linked list. We have to store the data and two pointers for each node in the linked list.

The previous pointer of the first node is null and the next pointer of the last node is null for representing the ending of the linked list at both sides.

You can see the illustration of a linked below.

Understanding Linked Lists Implementation in Python Development Python

The doubly-linked list also has similar steps as the singly-linked list in implementation. Again explaining the same things will be boring for you. Go through the code in each step and you will understand it very quickly. Let’s go.

Doubly Linked List Implementation

1. Creating a node for the doubly-linked list with the previous node pointer, data, and next node pointer.

class Node:

	def __init__(self, data):
		## previous pointer
		self.prev = None

		## data of the node
		self.data = data

		## next pointer
		self.next = None

2. Doubly linked list class.

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. A method to insert a new node into the doubly-linked list.

class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the last node to the previous pointer of the new node
			new_node.prev = last_node

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

4. A method to display the doubly-linked list data.

class LinkedList:

	####

	def display(self):

		## printing the data in normal order
		print("Normal Order: ", end='')

		temp_node = self.head
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.next
		print()

		## printing the data in reverse order using previous pointer
		print("Reverse Order: ", end='')

		## getting the last node
		last_node = self.head
		while last_node.next != None:
			last_node = last_node.next

		temp_node = last_node
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.prev
		print()

We have seen the code of the doubly-linked list. And there’s no code for the usage of the doubly-linked list class. That’s for you. Use the doubly-linked list class similar to the singly-linked list. Have fun 🙂

Conclusion

You can find many problems based on linked lists. But, you have to know the basic implementation of the linked that you have learned in this tutorial. Hope you had a great time learning the new concept.

Happy Coding 🙂

,
Show Comments