Singly/Doubly Linked List, Stack (LIFO), Queue (FIFO) in DSA
Table of Contents
Introduction to Linked Lists, Stacks, and Queues
In the world of computer science, Data Structures are essential components for solving complex problems efficiently. Among the fundamental data structures are Singly/Doubly Linked Lists, Stacks (LIFO), and Queues (FIFO). This article provides an exhaustive and SEO-optimized overview of these structures—covering their definitions, mechanisms, code examples, advantages, disadvantages, and real-world use cases, guided by Data Structures & Algorithms (DSA) principles.
Singly Linked List
What is a Singly Linked List?
A Singly Linked List is a type of linear data structure, consisting of nodes where each node contains data and a reference (next pointer) to the next node in the sequence.
Unlike arrays, linked lists allow dynamic memory allocation and easy insertions/removals.
Structure of a Node
class Node:
def __init__(self, data):
self.data = data
self.next = None
Basic Operations
- Insertion (at beginning, end, or specified position)
- Deletion (of a node by value or position)
- Traversal (visiting all nodes in order)
- Searching (for an element with specific value)
Python Example: Insertion at End
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
Advantages
- Dynamic size—memory efficient
- Easy insertions and deletions (no shifting required)
- No wasted space (unlike arrays with reserved capacity)
Disadvantages
- No direct/indexed access (O(n) for search)
- Extra memory for pointer/reference
- More complex implementation vs arrays
Doubly Linked List
What is a Doubly Linked List?
Doubly Linked List extends the concept of singly linked lists by adding a previous pointer. Each node contains data, a next pointer, and a prev pointer.
Structure of a Doubly Linked List Node
class DoublyNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
Key Advantages
- Traversal is possible in both directions
- Easy node deletion without traversing from head
Key Disadvantages
- Requires extra space for prev pointer
- More complex to implement and maintain
Python Example: Insert at Front
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_front(self, data):
new_node = DoublyNode(data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
Stack (LIFO)
What is a Stack?
A Stack is a linear data structure following the LIFO (Last-In, First-Out) principle. The element added last is the first to be removed. The main stack operations are push (insert), pop (remove), and peek (view top element).
Abstract Representation
stack = []
stack.append(1) # push
top = stack.pop() # pop
- Push: Add element at the top.
- Pop: Remove element from the top.
- Peek: View the top element without removing it.
Stack Applications
- Function call management (call stack)
- Undo operations in editors
- Expression parsing (postfix/prefix evaluation)
Advantages
- Simple structure; fast O(1) push/pop
- Used for backtracking and recursive algorithms
Disadvantages
- Limited access: can only access the top element
- Overflow if maximum size is reached (in static implementation)
Queue (FIFO)
What is a Queue?
A Queue follows the FIFO (First-In, First-Out) principle. Elements are inserted at the rear and removed from the front. Important queue operations: enqueue (insert), dequeue (remove), peek (front element).
from collections import deque
queue = deque()
queue.append(1) # enqueue
front = queue.popleft() # dequeue
Real-World Examples of Queues
- Print queues in operating systems
- Customer service/message queues
- Breadth-first search in graphs
Advantages
- Orderly access to elements
- O(1) time per enqueue/dequeue (with proper implementation)
Disadvantages
- Difficult to search or access non-front/rear elements
- Overflow in static array implementation
Comparative Analysis
| Feature | Singly Linked List | Doubly Linked List | Stack (LIFO) | Queue (FIFO) |
|---|---|---|---|---|
| Main Access Pattern | Sequential | Bidirectional | Last-In, First-Out | First-In, First-Out |
| Memory Overhead | Low (1 ptr/node) | High (2 ptr/node) | Low | Low |
| Direct Access | No | No | Top only | Front/Rear only |
| Insertion/Deletion Complexity | O(1) if pointer known | O(1) if pointer known | O(1) at top | O(1) at front/rear |
Real-World Applications
Singly Linked List
- Implementing dynamic memory allocation (e.g., heap management)
- Maintaining sequence of elements (playlist, image viewer navigation)
Doubly Linked List
- Browser history navigation (forward and backward)
- MRU/LRU cache implementations
Stack (LIFO)
- Undo/redo in text editors
- Expression evaluation (postfix, prefix)
- Syntax parsing in compilers
Queue (FIFO)
- Job scheduling (OS)
- Message servers (Web APIs)
- Print spooling
Conclusion
Understanding Singly and Doubly Linked Lists, Stack (LIFO), and Queue (FIFO) is crucial for mastering Data Structures & Algorithms. These structures serve as the foundation for complex algorithms and efficient problem-solving in real-life software systems. Their choice and implementation directly impact the performance and scalability of applications, underpinning everything from simple applications to enterprise-grade systems.
Frequently Asked Questions
Q1. Can we implement Stack and Queue using Linked Lists?
Yes, both Stack and Queue can be implemented using linked lists. A stack uses a singly linked list with push/pop operations at the head, whereas a queue maintains both front and rear pointers for enqueue/dequeue operations.
Q2. Which is better: Array or Linked List?
It depends on the requirements. Arrays offer fast indexed access, but linked lists are better for frequent dynamic insertions/deletions.
Q3. Where are doubly linked lists best used?
Situations demanding fast bidirectional traversal and frequent deletion/insertion not necessarily at the ends—such as implementing navigation in browsers, LRUs in caching, etc.
Q4. What is the major drawback of Stacks and Queues?
Restricted access—cannot arbitrarily access elements except top/front or rear.
Q5. Is there a real-world example of Queue in networking?
Yes, network routers use queues to process data packets in FIFO order, ensuring fair transmission.
, Queue (FIFO) in DSA: In-Depth Guide){kind=link}
0 Comments