Singly Linked List in DSA
Data is arranged as a series of connected elements, or nodes, in a singly linked list, a basic linear data structure. Each node in a linked list has two main components a data element and a reference (or pointer) to the node after it in the sequence. This is in contrast to arrays, which store data in contiguous memory areas. A singly linked list’s end is usually indicated by a None or NULL reference at the last node.
A linked list structure usually tracks references to its head and tail. Links have an advantage over arrays because they can dynamically resize without memory copy costs.
Operations on a Singly Linked List
In order to perform operations on a single linked list, these nodes and their subsequent references must be change
Insertion:
- At the Head: Adding a new entry to the start of a singly linked list is very effective and usually takes O(1) in the worst-case scenario. This entails generating a new node, changing the list’s head to point to the new node, and setting its next reference to the existing head.
- If the list has an explicit tail reference, inserting at the end of the list is likewise O(1) time. The previous tail is modified to point to the new node as the next reference, and the new node becomes the new tail. The list may be originally empty, in which case special handling may be required.
- Before a Specified Node: In a singly linked list, it may be less efficient to insert a node before an arbitrary node (not the head or tail). This takes O(N) time since discovering the predecessor of the specified node may require traversing the list from the head.
Deletion:
- By simply relocating the head to the following node in the sequence, the first element can be removed in an O(1) operation.
- From the Tail: In an O(N) time, it is inefficient to remove the final node of a singly linked list. This is due to the fact that you cannot follow the next links from the tail to directly visit the node before the tail. Start at the top to find the second-to-last node.
- Searching for an arbitrary node in the midst of a singly linked list and its predecessor can take O(N) time.
Searching:
In computer science, searching is a basic process that entails locating a certain piece within a data structure. Efficiently locating a target value is the main objective of searching algorithms. The time complexity of a search method, which is frequently represented using Big O notation, is usually used to gauge its efficiency.
Traversal: This process entails going to each list node.
- Forward Traversal: This takes O(N) time and begins at the head and proceeds to the next pointers until none are found.
- The inefficiency of traversing a singly linked list in reverse order is known as reverse traversal. The time complexity is O(N^2) since each step’s predecessor must be found by traversing from the beginning in the absence of a previous pointer, which is present in doubly linked lists. Lists that are doubly linked are advised for effective bi-directional traversal.
Implementing a Stack ADT using a Singly Linked List
Operating on the Last-In, First-Out (LIFO) principle, a stack is an Abstract Data Type (ADT). This indicates that just the “top” of the stack the end from which pieces are added and removed is affected.
By placing the top of the stack at the head of the linked list, a single linked list’s operations completely conform to the stack’s LIFO principle, making it a great candidate for implementing a stack ADT. This enables the efficient execution of all primary stack operations in O(1) worst-case time.
Typical stack operations map to singly linked list operations as follows:
- Push(e): This adds an element e to the top of the stack by creating a new node for e, setting its next pointer to the linked list’s current head, and then updating the list’s head to point to the new node. Putting an element at the head of the singly linked list is the same as doing this.
- pop() Updates the head to point to the next node in the sequence after retrieving the element from the current head node in order to remove and return the element from the top of the stack. Removing the element from the singly linked list’s head is the same as doing this.
- Simply access the data element of the head node to return the element at the top without deleting it using top() or peek(). If there is nothing in the stack, an Empty exception should be raised.
- is_empty(): This function determines whether any elements are present in the stack. If there is no head reference (or if the size is 0), it returns True.
- len(): Push and pop operations usually maintain and update an instance variable size to return the number of elements. Len() can now be an O(1) operation as a result.
Example for a Stack Implemented by a Singly Linked List
The code structure that follows illustrates how a single linked list might be used to implement a stack in python:
class Empty(Exception):
"""Error attempting to access an element from an empty container."""
pass
class LinkedStack:
"""LIFO Stack implementation using a singly linked list for storage."""
# nested Node class
class _Node:
"""Lightweight, nonpublic class for storing a singly linked node."""
__slots__ = '_element', '_next'
def __init__(self, element, next_node):
self._element = element
self._next = next_node
# stack methods
def __init__(self):
"""Create an empty stack."""
self._head = None
self._size = 0
def __len__(self):
"""Return the number of elements in the stack."""
return self._size
def is_empty(self):
"""Return True if the stack is empty."""
return self._size == 0
def push(self, e):
"""Add element e to the top of the stack."""
# Create and link a new node
self._head = self._Node(e, self._head)
self._size += 1
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise Empty("Stack is empty")
return self._head._element
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise Empty("Stack is empty")
answer = self._head._element
self._head = self._head._next
self._size -= 1
return answer
# Example Usage
print("--- Initializing Stack ---")
s = LinkedStack()
print(f"Is stack empty? {s.is_empty()}")
print(f"Stack size: {len(s)}")
print("\n--- Pushing elements ---")
s.push(10)
s.push(20)
s.push(30)
print(f"Pushed 10, 20, 30.")
print(f"Is stack empty? {s.is_empty()}")
print(f"Stack size: {len(s)}")
print(f"Top element: {s.top()}")
print("\n--- Popping elements ---")
print(f"Popped: {s.pop()}")
print(f"Stack size after pop: {len(s)}")
print(f"Top element after pop: {s.top()}")
s.push(40)
print(f"Pushed 40.")
print(f"Stack size: {len(s)}")
print(f"Top element: {s.top()}")
print(f"Popped: {s.pop()}")
print(f"Popped: {s.pop()}")
print(f"Stack size after 2 more pops: {len(s)}")
print("\n--- Demonstrating Empty Stack Behavior ---")
try:
print(f"Top element (should raise Empty): {s.top()}")
except Empty as e:
print(f"Caught exception: {e}")
try:
print(f"Popped (should raise Empty): {s.pop()}")
except Empty as e:
print(f"Caught exception: {e}")
print(f"Is stack empty now? {s.is_empty()}")Output:
Initializing Stack
Is stack empty? True
Stack size: 0
Pushing elements
Pushed 10, 20, 30.
Is stack empty? False
Stack size: 3
Top element: 30
Popping elements
Popped: 30
Stack size after pop: 2
Top element after pop: 20
Pushed 40.
Stack size: 3
Top element: 40
Popped: 40
Popped: 20
Stack size after 2 more pops: 1
Demonstrating Empty Stack Behavior
Top element (should raise Empty): 10
Popped (should raise Empty): 10
Is stack empty now? True