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
- 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. 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.
- Create a class called LinkedList with head initialized to None. See the code below.
- 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. 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. 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. Run the above program to get the following result. 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
- Creating a node for the doubly-linked list with the previous node pointer, data, and next node pointer.
- Doubly linked list class.
- A method to insert a new node into the doubly-linked list.
- A method to display the doubly-linked list data. 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 🙂
