Unit II: Linked Lists and Queues
1. Introduction to Linked Lists
A Linked List is a linear collection of data elements called nodes. Unlike arrays, elements are not stored in contiguous memory locations. Instead, each node contains two parts:
- Data: The actual information to be stored.
- Next (Pointer): A reference to the address of the next node in the sequence.
Advantages Over Arrays
- Dynamic Size: They can grow or shrink during runtime, avoiding the static limitations of arrays.
- Efficient Insertion/Deletion: No need to shift elements; only pointer updates are required.
2. Types: Singly, Doubly & Circular
Singly Linked List
The simplest form where each node points only to the next node. The last node's pointer is NULL.
Doubly Linked List (DLL)
Each node contains two pointers: one pointing to the next node and one to the previous node.
- Benefit: Allows bidirectional traversal (forward and backward).
- Cost: Requires extra memory for the second pointer.
Circular Linked List
In this variation, the last node of the list does not point to NULL but points back to the first node (Head).
- Circular Singly: Last node points to the first.
- Circular Doubly: Last node points to first, and first node's 'previous' points to the last.
3. Stack Representation in Lists
Stacks can be implemented using linked lists to overcome the fixed size limitation of arrays.
Normal Representation
The Top of the stack is always the Head of the linked list.
- Push: Insert a new node at the beginning (Head).
- Pop: Delete the node at the beginning.
Circular Representation of Stack
Using a circular linked list to represent a stack ensures that the "Top" node points to the bottom-most node, maintaining a closed loop. This is often used in buffer management.
4. Self-Organizing & Skip Lists
Self-Organizing Lists
A list that reorders its elements based on access frequency to improve search time.
- Move-to-Front: When an element is accessed, it is moved to the head of the list.
- Transpose: When an element is accessed, it is swapped with its predecessor.
Skip Lists
A probabilistic data structure that allows O(log n) search complexity. It consists of multiple layers of linked lists where the bottom layer is a standard list and upper layers act as "express lanes" to skip nodes.
5. Queues: Array & Linked Representation
A Queue is a linear structure following the FIFO (First-In, First-Out) principle.
Array Representation
Uses two pointers: Front (for deletion) and Rear (for insertion).
Warning: In a simple array queue, even if space is available at the front after deletions, you cannot insert more elements if Rear reaches the end. This is solved by Circular Queues.
Linked Representation
Maintains 'Front' and 'Rear' pointers to a linked list.
- Enqueue: Add node at the Rear.
- Dequeue: Remove node from the Front.
6. De-queue & Priority Queues
De-queue (Double-Ended Queue)
A generalized queue where elements can be added or removed from either the front or the rear.
- Input-Restricted: Deletions from both ends, but insertions only at one end.
- Output-Restricted: Insertions at both ends, but deletions only at one end.
Priority Queues
Each element is assigned a priority. Elements with higher priority are dequeued before elements with lower priority, regardless of their arrival order.
Application: CPU Scheduling and Dijkstra's Shortest Path Algorithm.
7. Exam Focus & FAQs
Exam Tips
- Derivations: Practice drawing the state of pointers before and after an Insert-at-Middle operation in a DLL.
- Complexity: Remember that searching in a Singly Linked List is O(n), while in a Skip List it is O(log n).
- Circular Queues: Formula for next position: Rear = (Rear + 1) % Size.
Frequently Asked Questions
Q: Why is a DLL preferred over a SLL?
DLL allows moving in both directions, making deletions of a given node easier as you have immediate access to the predecessor.
Q: What is a Skip List?
It is a sorted linked list with multiple levels of pointers that allow "skipping" over many elements, providing search speeds comparable to binary search trees.
Mnemonic: Q-FIFO
Remember Q-FIFO: Queues are First-In, First-Out.