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.

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.

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.

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

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.

def __init__(self):
## initializing the head with 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.

####

def insert(self, new_node):
## check whether the head is empty or not
## getting the last node
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:
## assigning the node to head

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.

####

def display(self):
## variable for iteration

## 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

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

def insert(self, new_node):
## check whether the head is empty or not
## getting the last node
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:
## assigning the node to head

def display(self):
## variable for iteration

## 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__':

## inserting the data into the linked list

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.

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.

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.

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

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

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

####

def insert(self, new_node):
## check whether the head is empty or not
## getting the last node
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.

####

def display(self):

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

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
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 ðŸ™‚