DS: Singly Linked List in Python

1	Singly Linked List
2	Doubly Linked List
3	Circular Linked List

What is a 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.

Singly Linked List

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.

Basic Operations on any list

• 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

---

Linked list class

class LinkedList:
    def __init__(self):
        self.head = None

self.head stores the starting point of the list.

Traversing 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

Add item to head or beginning

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

The above 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?

Add item to tail or end

Modifying the 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.

Add item after a particular item

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

Removing an item from the list

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.