Singly Linked Lists
Tags: beginners, learning, python, algorithms
Published: 2023-10-21 13:55:54

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:

![Singly Linked List](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9pno9x5u7y1ll6njlegf.png)

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:
```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!