Unit 2: Linked Lists and Queues

1. Linked Lists

A Linked List is a linear data structure, like an array, but its elements are not stored in contiguous memory locations. Instead, elements are linked using pointers.

Each element in a linked list is called a node. A node consists of two parts:

1. Data: The actual value stored in the node.
2. Next (Pointer/Link): A pointer that stores the memory address of the next node in the sequence.

The entry point to the linked list is a special pointer called the head, which points to the first node. The last node in the list has its next pointer set to NULL.

Arrays vs. Linked Lists

Singly Linked Lists

This is the standard linked list described above, where each node has one pointer (next) pointing to the next node in the list. Traversal is one-way (forward) only.

Basic Operations:

• Traversal: Start from head, follow next pointers until NULL.
• Insertion:
  • At Beginning (O(1)): Create a new node. Point its next to the current head. Update head to point to the new node.
  • At End (O(n)): Traverse to the last node. Point its next to the new node.
  • At Middle (O(n)): Traverse to the node *before* the desired position. Update pointers.
• Deletion:
  • At Beginning (O(1)): Store head in a temp node. Update head = head.next. Free the temp node.
  • At End (O(n)): Traverse to the *second-to-last* node. Set its next to NULL. Free the last node.
  • At Middle (O(n)): Traverse to the node *before* the one to be deleted. Update pointers to "skip" the deleted node.

Doubly Linked Lists

A doubly linked list (DLL) node contains two pointers in addition to the data:

1. Data: The value.
2. Next: Points to the next node (or NULL).
3. Prev: Points to the previous node (or NULL for the head).

Advantages over Singly Linked List:

• Can be traversed in both directions (forward and backward).
• Deletion is more efficient. If you are given a pointer to the node to be deleted, you don't need to traverse to find its previous node (unlike in a singly list). You can access it directly via node.prev.

Disadvantage:

• Requires extra memory for the prev pointer.
• Insertion and deletion operations are more complex as two pointers (next and prev) must be updated.

Circular Lists

A circular linked list is a list where the last node does not point to NULL. Instead, its next pointer points back to the head node, forming a circle.

Advantages:

• The entire list can be traversed starting from any node.
• Useful for applications that require round-robin processing (e.g., CPU scheduling).

A Circular Doubly Linked List also exists, where the head.prev points to the last node, and the last.next points to the head.

Array and Linked Representation

This refers to the comparison of implementing linear lists using arrays versus linked lists, as detailed in the table above.

Normal and Circular Representation of Stack in Lists

As discussed in Unit 1, the array implementation of a stack has a fixed-size limitation. A linked list is a perfect solution for this.

Normal Linked List Stack

A stack is implemented using a standard singly linked list. The LIFO behavior is achieved by performing push and pop operations at the beginning (head) of the list.

• The head pointer of the list acts as the top of the stack.
• push(value): Same as "Insert at Beginning" (O(1)).
• pop(): Same as "Delete at Beginning" (O(1)).

This implementation is very efficient and overcomes the overflow problem (it's only limited by the total system memory).

Circular List Stack

While possible, using a circular list to implement a stack is less common. One could maintain a single pointer last (pointing to the last node). The "top" of the stack would be last.next (the head). Pushing and popping would still happen at the "head" (last.next), which remains an O(1) operation.

Self Organizing Lists

A self-organizing list is a linked list that reorders its nodes based on access patterns to improve average search time. The goal is to keep frequently accessed elements near the front of the list.

Common heuristics:

1. Move-to-Front (MTF): When a node is accessed, it is moved to the very front (head) of the list.
2. Transpose (or Swap): When a node is accessed, it is swapped with the node immediately *before* it.

Skip Lists

A skip list is a probabilistic data structure that provides efficient search (average O(log n)) in a sorted list. It's essentially a linked list with "express lanes."

It's built in layers. The bottom layer (Level 0) is a regular sorted linked list. Each higher layer (Level 1, Level 2, ...) contains a subset of the nodes from the layer below. A node in Level i has a random probability of also appearing in Level i+1.

To search, you start at the highest layer. You traverse forward until you find a node greater than your target. You then drop down one layer and continue. This "skipping" allows you to bypass large portions of the list, achieving logarithmic time complexity, similar to a balanced binary search tree.

2. Queues

A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. This means the element added first is the first one to be removed. Think of it as a line of people waiting for a ticket.

The primary operations are:

• enqueue(element): Adds an element to the rear (end) of the queue.
• dequeue(): Removes and returns the element from the front (beginning) of the queue.
• peek() or front(): Returns the front element without removing it.
• isEmpty(): Checks if the queue is empty.

A queue is managed with two pointers: front (points to the first element) and rear (points to the last element).

Array Representation of Queue

A simple 1D array can be used, but it's inefficient. If you dequeue, the front pointer moves, and that space is "lost." You would have to shift all elements (O(n)), which is slow.

A much better solution is a Circular Array (or Circular Queue).

• Use an array queue[MAX_SIZE] and two indices, front and rear.
• Initialize front = -1 and rear = -1.
• Enqueue: Increment rear using modulo arithmetic: rear = (rear + 1) % MAX_SIZE. Then insert the element.
• Dequeue: Increment front using modulo arithmetic: front = (front + 1) % MAX_SIZE. Then return the element.
• Full Condition: (rear + 1) % MAX_SIZE == front
• Empty Condition: front == rear (or front == -1)

Linked Representation of Queue

This is a more flexible implementation that avoids the fixed-size limit. A singly linked list is used with two external pointers: front and rear.

• front points to the head of the list.
• rear points to the last node of the list.
• Enqueue (O(1)): Same as "Insert at End" in a linked list. Create a new node, point rear.next to it, and update rear.
• Dequeue (O(1)): Same as "Delete at Beginning" in a linked list. Get data from front, update front = front.next, and free the old front node.

De-queue (Deque)

A Deque (pronounced "deck"), or Double-Ended Queue, is a generalization of a queue that allows insertion and deletion from both ends (front and rear).

Operations:

• Insert at Front
• Delete at Front
• Insert at Rear
• Delete at Rear

It can be implemented using either a circular array or a doubly linked list.

Priority Queues

A Priority Queue is an abstract data type where each element has an associated priority. The operations are:

• Insert(element, priority): Adds an element.
• Extract-Max() (or Extract-Min()): Removes and returns the element with the highest (or lowest) priority.

This is different from a normal queue; the "first-in" element is not necessarily the "first-out."

Implementations:

• Unsorted Array/List: Insert is O(1). Extract-Max is O(n) (must search).
• Sorted Array/List: Insert is O(n) (must find spot). Extract-Max is O(1).
• Heap (Best): (See Unit 3). Both Insert and Extract-Max are O(log n). This is the most common implementation.