|1||Singly Linked List|
|2||Doubly Linked List|
|3||Circular Linked List|
Linked list a data structure used to store and access a collection of data in a formatted way.
They are various types of linked list
- Singly Linked List
- Doubly Linked List
- Circular Linked List
We will discuss each one in a different post.
This list consists of a number of nodes in which each node has a pointer pointing to the next element/item. The last element/item points to null.
- Traversing the list (display or find)
- Add item to head or beginning (append)
- Add item to tail or end (prepend)
- Add item after particular item (insertAfter)
- Delete a given item (delete)
Let us implement singly using python language.
Node is the smallest item in the list which holds data and pointer
class Node: def __init__(self, data): self.data = data self.next = None
class LinkedList: def __init__(self): self.head = None
self.head stores the starting point of the list.
We have to get the starting point from
self.head then loop over each element until we reach null.
def display(self): currentNode = self.head while currentNode: print(currentNode.data) currentNode = currentNode.next
let's add the first item to the list.
def append(self, data): newNode = Node(data) self.head = newNode return; llist = LinkedList() llist.append("A") llist.display() # A
append method holds good for the first time you add an element to the list, what if you want to add another item to the list?
append method to suit our new requirement will look like this
def append(self, data): newNode = Node(data); if self.head is None: self.head = newNode return; lastNode = self.head while lastNode.next: lastNode = lastNode.next lastNode.next = newNode; llist = LinkedList() llist.append("A") llist.append("B") llist.display() # A B
we have to first check if the head is already set or not? In our case, we have already added the item "A". It will move forward to the next block of code which is traversing the list to find the last item
item.next until we reach the end of the list.
Add the new node to the
lastNode.next and the flow ends there.
As you can see from the above diagram. In order to insert an element in the middle, we have to do certain operations in a step by step manner.
- Check if a given node is not empty
- Create a new node
- New node to copy the next pointer from the previous node
- Update the previous node next pointer to point our new node
Below program will help you do it.
def insertAfter(self, previousNode, data): if not previousNode: print('send prev node') return newNode = Node(data) newNode.next = previousNode.next previousNode.next = newNode llist = LinkedList() llist.append("A") llist.append("B") llist.insertAfter(llist.head.next,"C") llist.display() # A C B
I will leave this section for you to complete and you can answer in the comment section.
The complete file can be found here
This explains basic operation on the linked list. As you could see the list can increase on runtime and ease of access.
In the next post, we will discuss the doubly linked list and its advantages over the singly linked list.
Thank you for passing by ;)
If you have any comments or questions please use the comments section below.