Singly Linked Lists

In this new blog series of mine, we'll be adventuring into the realm of DSA. The intent of this blog series is to explore the fundamentals of DSA while trying to maintain the KISS (keep it simple, stupid) principle. Hence, all the implementations throughout this series will be with python.

Now that you have the context, without further ado, let's dive in.
To start with one of the most basic data structures we'll be implementing the linked lists in this post.

What are Singly Linked Lists?

A linked list is a type of data structure in which each element is actually a separate object while all the objects are linked together by a reference field. If you try to envision it, it might look something like the below representation:

There are two types of linked lists:
1) Singly Linked List
2) Doubly Linked list
In this post, we'll be exploring the singly linked list specifically.

Each object is a node in a linked list and is connected to only one other node in a Singly linked list.

Adding a node

To add a node to a singly linked list, lets consider the node that we want to add as cur and initialize it. We want to insert the cur node between prev node and next node. To do this we have to:

Connect the reference field of prev node to the cur node
Connect the reference field of cur node to the next node

Unlike an array, we don’t have to move all elements past the inserted element. Therefore, you can insert a new node into a linked list in O(1) time complexity if you have a reference to prev, which is very efficient.

Deleting a node

To delete a node, lets consider the same example with cur, prev and next. cur is the node you want to delete.

Find the cur node's previous node prev and next node next first
Link prev node's reference field to the next node, eventually unlinking cur node in the process

Finding the next node using the reference field is easy. But to find the previous node prev, we have to traverse the linked list from the head node, hence the time complexity of deleting a node in a linked list is O(n) where n is the length of the list.

Implementation with Python

Here's the implementation of the singly linked list with python:

class LinkedNode:
    def __init__(self, val):
        self.val = val
        self.next = None


class SinglyLinkedList:

    def __init__(self):
        self.head = None
        self.length = 0

    def get_with_index(self, index):
        if index < 0 or index >= self.length:
            # Raise an error if the index is out of bounds
            raise IndexError("Index out of bounds")

        cur = self.head
        for _ in range(index):
            # Traverse the list to the specified index
            cur = cur.next

        return cur.val

    def add_to_head(self, val):
        new = LinkedNode(val)

        if not self.head:
            # If the list is empty, the new node becomes the head
            self.head = new
        else:
            # Otherwise, make the new node the new head and link it to the previous head
            new.next = self.head
            self.head = new
        self.length += 1

    def add_to_tail(self, val):
        new = LinkedNode(val)

        if self.length == 0:
            # If the list is empty, the new node becomes the head
            self.head = new
        else:
            cur = self.head
            while cur.next:
                # Traverse to the end of the list
                cur = cur.next
            cur.next = new
        self.length += 1

    def add_at_index(self, index, val):
        new = LinkedNode(val)

        if index < 0 or index > self.length:
            # Raise an error if the index is out of bounds
            raise IndexError("Index out of bounds")

        if index == 0:
            # If index is 0, the new node becomes the head
            self.head = new
            self.length+=1
            return

        cur = self.head
        for _ in range(index - 1):
            # Traverse to the node just before the specified index
            cur = cur.next

        new.next = cur.next
        cur.next = new
        self.length += 1

    def delete_at_index(self, index):
        if index < 0 or index >= self.length:
            # Raise an error if the index is out of bounds
            raise IndexError("Index out of bounds")

        if index == 0:
            # If index is 0, remove the head node
            self.head = self.head.next
            self.length -= 1

        cur = self.head
        for _ in range(index - 1):
            # Traverse to the node just before the specified index
            cur = cur.next

        cur.next = cur.next.next
        self.length -= 1

Now that's about singly linked lists, in the next blog post we'll have a look at the doubly linked lists. Until then, Sayonara!

Blog

Adheeban Manoharan

What are Singly Linked Lists?

Adding a node

Deleting a node

Implementation with Python

Join Our Newsletter. No Spam, Only the good stuff.

Related