# Understanding Linked Lists Implementation in Python

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.

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, 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 = Noneclass 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.

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 🙂