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
prevnode to thecurnode - Connect the reference field of
curnode to thenextnode
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
curnode's previous nodeprevand next nodenextfirst - Link
prevnode's reference field to thenextnode, eventually unlinkingcurnode 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!
SOCIAL SHARE CARD GENERATOR