[gtranslate]
Geekflare is supported by our audience. We may earn affiliate commissions from buying links on this site.
In Development Last updated: August 30, 2023
Share on:
Invicti Web Application Security Scanner – the only solution that delivers automatic verification of vulnerabilities with Proof-Based Scanning™.

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.

``````class LinkedList:

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.

``````class LinkedList:

####

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.

``````class LinkedList:

####

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

``````class LinkedList:

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

``````class LinkedList:

####

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.

Also, check how to use the python index method to find the index of an item in a list.

Happy Coding 😀

• Hafeezul Kareem Shaik
Author