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!

## Top comments (0)