Linked List
Open in the Padhaiko app4.1 Definition of list and its operations
List Abstract Data Type (ADT)
A list is an ordered, linear sequence of zero or more elements of homogeneous type, represented mathematically as , where denotes the length (or size) of the list. If , the list is said to be empty.
In a list, elements possess an explicit linear order: for each element (), is its predecessor and is its successor. Unlike stacks and queues, list operations are not restricted to the boundary endpoints; elements can be inserted, inspected, or removed at any arbitrary position.
Core Operations of List ADT
| Operation | Function Signature | Description |
|---|---|---|
createList() | List* createList() | Initializes an empty list structure |
isEmpty(L) | int isEmpty(List *L) | Returns 1 if length is 0, else returns 0 |
length(L) | int length(List *L) | Returns the total count of elements in the list |
get(L, i) | Element get(List *L, int i) | Retrieves the element at index position () |
insert(L, i, x) | void insert(List *L, int i, Element x) | Inserts new element at index , shifting subsequent items |
delete(L, i) | Element delete(List *L, int i) | Removes and returns the element at index , shifting subsequent items |
search(L, x) | int search(List *L, Element x) | Returns index of the first occurrence of , or if absent |
traverse(L) | void traverse(List *L) | Visits and displays every element from index to |
4.2 Array implementation of list ADT
In a sequential (array-based) implementation, elements of the list are stored in contiguous memory cells of a fixed-size one-dimensional array.
#include <stdio.h>
#define MAX 100
typedef struct {
int items[MAX];
int size;
} ArrayList;
void initList(ArrayList *l) {
l->size = 0;
}
int insertAt(ArrayList *l, int index, int value) {
if (l->size == MAX) {
printf("List Overflow!\n");
return 0;
}
if (index < 0 || index > l->size) {
printf("Invalid insertion index!\n");
return 0;
}
// Shift elements to the right from index up to size-1
for (int i = l->size - 1; i >= index; i--) {
l->items[i + 1] = l->items[i];
}
l->items[index] = value;
l->size++;
return 1;
}
int deleteAt(ArrayList *l, int index) {
if (l->size == 0) {
printf("List Underflow!\n");
return -1;
}
if (index < 0 || index >= l->size) {
printf("Invalid deletion index!\n");
return -1;
}
int removed = l->items[index];
// Shift elements to the left from index+1 up to size-1
for (int i = index; i < l->size - 1; i++) {
l->items[i] = l->items[i + 1];
}
l->size--;
return removed;
}Operational Complexity of Array Lists
- Direct Indexing: Accessing
items[i]takes time because address calculation is direct: . - Insertion at index : Requires shifting elements to the right. Worst case (insert at index 0): shifts.
- Deletion at index : Requires shifting elements to the left. Worst case (delete index 0): shifts.
4.3 Static list and its limitations
A static list relies on compile-time memory allocation with a fixed upper bound (MAX). While simple to declare, it suffers from several severe practical drawbacks:
- Fixed Memory Size:
- The developer must estimate the maximum possible number of elements ahead of execution.
- If the actual number of elements exceeds
MAX, the system triggers List Overflow, crashing or refusing new data.
- Memory Inefficiency (Wastage):
- If an array is sized for elements but holds only , the remaining slots remain allocated and wasted in RAM.
- Expensive Data Shifting:
- Inserting or removing an element anywhere except the tail requires shifting on average items. For large lists, this continuous memory movement degrades throughput.
- Contiguous Allocation Requirement:
- Arrays mandate a single uninterrupted block of contiguous physical memory. If available free memory is fragmented into smaller chunks, an array allocation of large size will fail even though total free memory is ample.
4.4 Linked list: Definition and its operations
Linked List
A linked list is a dynamic linear data structure composed of self-referential structures called nodes. Each node contains two essential parts:
- Data field: stores the actual user information.
- Link / Pointer field: stores the memory address of the next node in the linear sequence.
The entire list is accessed via an external pointer called head, and the terminal node's link field is set to NULL.
head
|
v
+------+------+ +------+------+ +------+------+
| Data | Next |---->| Data | Next |---->| Data | NULL |
+------+------+ +------+------+ +------+------+
Node 1 Node 2 Node 3 (Tail)| Aspect | Array List (Static) | Linked List (Dynamic) |
|---|---|---|
| Memory Allocation | Static (compile time) in contiguous memory blocks | Dynamic (runtime via malloc) in scattered heap blocks |
| Size Flexibility | Fixed maximum capacity; susceptible to overflow | Grows and shrinks dynamically; limited only by heap RAM |
| Element Access | Direct / Random access: via index | Sequential access: traversal from head |
| Insert / Delete at Head | Expensive due to element shifting | Fast by manipulating pointer references |
| Insert / Delete at Middle | shifting overhead | traversal, but pointer rewiring once node is located |
| Memory Overhead | Zero extra pointer storage | Extra memory per node for pointer references (4 or 8 bytes) |
Node Structure in C
typedef struct Node {
int data;
struct Node *next;
} Node;
4.5 Types of linked list: Singly, doubly, circular
Linked lists are classified into three major architectural configurations according to link structure and circularity.
4.5.1 Singly Linked List
In a singly linked list (SLL), each node contains a single pointer pointing exclusively forward to its immediate successor. Traversal is strictly unidirectional from head to tail.
| Operation | Algorithmic Steps | Time Complexity |
|---|---|---|
| Insert at Beginning | newNode->next = head; head = newNode; | |
| Insert at End | Traverse until temp->next == NULL; set temp->next = newNode; newNode->next = NULL; | (or with tail pointer) |
| Insert at Position | Traverse to node at position ; newNode->next = temp->next; temp->next = newNode; | |
| Delete from Beginning | temp = head; head = head->next; free(temp); | |
| Delete from End | Traverse to second-to-last node; free(temp->next); temp->next = NULL; | |
| Delete at Position | Traverse to node at ; target = temp->next; temp->next = target->next; free(target); |
4.5.2 Doubly Linked List
Doubly Linked List (DLL)
A doubly linked list is a two-way linked data structure in which every node contains two pointers:
prev: points to the preceding node in the list (head->prev = NULL).next: points to the succeeding node in the list (tail->next = NULL).
head
|
v
NULL <---+----+----+----+ +----+----+----+ +----+----+----+
|Prev|Data|Next| <---> |Prev|Data|Next| <---> |Prev|Data|Next| ---> NULL
+----+----+----+ +----+----+----+ +----+----+----+Advantages and Disadvantages of DLL
- Advantages:
- Bidirectional traversal: Can be traversed forward from
headand backward fromtail. - Efficient deletion: Given a pointer to target node
ptr, deletion takes time without requiring prior traversal to find the predecessor:if (ptr->prev != NULL) ptr->prev->next = ptr->next; if (ptr->next != NULL) ptr->next->prev = ptr->prev; free(ptr);
- Bidirectional traversal: Can be traversed forward from
- Disadvantages:
- Extra memory overhead for an additional pointer per node.
- More pointer updates required during insertion and deletion (4 pointers to rewire).
4.5.3 Circular Linked List
Circular Linked List
A circular linked list is a linked list in which the last node does not point to NULL; instead, its next pointer references back to the head node, forming an endless closed ring.
Variants of Circular Linked Lists
- Circular Singly Linked List (CSLL):
- The
nextpointer of the last node points back tohead. - Traversal terminates when a pointer returns to
head(curr->next == head).
- The
- Circular Doubly Linked List (CDLL):
lastNode->next = headandhead->prev = lastNode.- Allows seamless circular traversal in both clockwise and counter-clockwise directions.
- Primary Applications: CPU Round-Robin scheduling (cycles through processes endlessly), audio playlist cycling, and resource-sharing token passing in networking (Token Ring).
4.6 Application of linked list
Linked lists are foundational building blocks used to implement other dynamic data structures and perform symbolic algebraic computations.
4.6.1 Linked list implementation of stack and queue ADT
1. Linked Stack
A stack can be implemented using a singly linked list where top points to the head node:
- Push operation: Insert at the beginning: Time complexity: .
newNode->data = item; newNode->next = top; top = newNode; - Pop operation: Delete from the beginning: Time complexity: .
temp = top; item = top->data; top = top->next; free(temp); return item; - Advantage: Eliminates the static array stack overflow constraint; the stack grows dynamically up to available heap memory.
2. Linked Queue
A queue requires two external pointers: front (pointing to the head node for deletions) and rear (pointing to the tail node for insertions):
- Enqueue operation: Insert at the rear: Time complexity: .
newNode->data = item; newNode->next = NULL; if (rear == NULL) { front = rear = newNode; } else { rear->next = newNode; rear = newNode; } - Dequeue operation: Delete from the front: Time complexity: .
temp = front; item = front->data; front = front->next; if (front == NULL) rear = NULL; // Queue is now empty free(temp); return item; - Advantage: Completely solves the false overflow and capacity limits of linear array queues without requiring circular index wrapping.
4.6.2 Solving polynomial equations using linked list
A single-variable polynomial can be represented as an ordered linked list where each node encapsulates a single non-zero term:
typedef struct PolyNode {
int coeff; // Coefficient of the term
int expo; // Exponent of the variable
struct PolyNode *next; // Pointer to next lower-degree term
} PolyNode;
Terms are maintained in strictly descending order of exponents ().
Polynomial Addition Algorithm
To add two polynomials and , we initialize pointers p1 and p2 at their respective heads and traverse them concurrently:
- Equal Exponents (
p1->expo == p2->expo):- Compute
sumCoeff = p1->coeff + p2->coeff. - If
sumCoeff != 0, insert term(sumCoeff, p1->expo)into the result polynomial. - Advance both
p1 = p1->nextandp2 = p2->next.
- Compute
- First Exponent Greater (
p1->expo > p2->expo):- Insert term
(p1->coeff, p1->expo)into the result. - Advance
p1 = p1->next.
- Insert term
- Second Exponent Greater (
p2->expo > p1->expo):- Insert term
(p2->coeff, p2->expo)into the result. - Advance
p2 = p2->next.
- Insert term
- Append Remaining Terms: When one list reaches
NULL, copy all remaining nodes of the other list directly to the result.
Time complexity: , where and are the number of non-zero terms in and .
Worked Examples
1
Trace the step-by-step pointer manipulation required to insert a new node with data 25 at position (1-based index) into an existing singly linked list containing elements [10, 20, 30, 40].
Locating the insertion site: To insert at position , we must insert between node 1 (value 10) and node 2 (value 20). Traverse curr from head until curr points to position :
currpoints to node with value10.curr->nextpoints to node with value20.
Rewiring pointers: Allocate newNode with newNode->data = 25.
- Connect
newNode->nextto the successor node:
- Connect predecessor to
newNode:
The resulting list is 10 -> 25 -> 20 -> 30 -> 40 -> NULL. The insertion rewired exactly two pointers without shifting any existing nodes in memory.
2
Trace the pointer adjustments for deleting an interior node with key value 30 in a doubly linked list containing: head <-> [10] <-> [20] <-> [30] <-> [40] <-> NULL. Show how prev and next pointers are updated and how memory is freed.
Locating target node target ():
- Predecessor node:
target->prevpoints to node[20]. - Successor node:
target->nextpoints to node[40].
Bypassing target in both directions:
- Update predecessor's forward link:
- Update successor's backward link:
- Release memory:
After deletion, the doubly linked list becomes [10] <-> [20] <-> [40] <-> NULL. Node [30] is cleanly detached and its allocated memory freed in pointer operations.
3
Add the following two polynomials using the linked list polynomial addition algorithm:
Show the term-by-term comparison and evaluate the resultant polynomial at .
Term-by-term comparison trace: Scan pointers p1 and p2 across decreasing exponents:
| Step | Term | Term | Exponent Comparison | Resulting Term Added |
|---|---|---|---|---|
| 1 | ||||
| 2 | (Zero coefficient, term omitted) | |||
| 3 | ||||
| 4 |
Resultant polynomial: .
Evaluating at :
Verifying directly from inputs:
The resulting sum polynomial is . At , the polynomial evaluates to .
4
Trace the pointers front and rear for a linked queue under the sequence: enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), dequeue(). Show the linked nodes after each step.
Tracing linked queue operations:
- Initial:
front = NULL, rear = NULL. enqueue(10): Allocate node[10].front = [10], rear = [10]. List:10 -> NULL.enqueue(20): Allocate node[20].rear->next = [20]; rear = [20]. List:10 -> 20 -> NULL.enqueue(30): Allocate node[30].rear->next = [30]; rear = [30]. List:10 -> 20 -> 30 -> NULL.dequeue(): Savetemp = front(10).front = front->next(20).free(temp). List:20 -> 30 -> NULL. Returns10.enqueue(40): Allocate node[40].rear->next = [40]; rear = [40]. List:20 -> 30 -> 40 -> NULL.dequeue(): Savetemp = front(20).front = front->next(30).free(temp). List:30 -> 40 -> NULL. Returns20.
After all operations, the queue contains 30 -> 40 -> NULL with front pointing to [30] and rear pointing to [40]. The dequeued values in order were 10 and 20.
Exercises
Exercise Questions: Linked List
Compare and contrast array and linked list implementations of the List ADT with respect to:
- Memory allocation and storage layout
- Access time for arbitrary elements
- Time complexity of insertion and deletion operations
Comparing Architectural Properties:
| Parameter | Array (Sequential List) | Linked List (Dynamic List) |
|---|---|---|
| Allocation Mechanism | Static/contiguous block allocated at compile time (or fixed heap chunk via calloc) | Dynamic non-contiguous nodes allocated individually on demand at runtime |
| Memory Utilization | Potential unused capacity or overflow; no pointer overhead | Exactly matches required nodes; stores extra link pointers per node |
| Direct Access Time | Instantaneous via formula | Linear sequential pointer traversal from head |
| Insert / Delete at Ends | at end (if not full); at front due to full array shift | at front; at end with tail pointer; zero data shifting |
| Insert / Delete in Middle | required to shift remaining elements | search time, but link rewiring once position is reached |
Arrays offer random access but require fixed contiguous memory and suffer element shifts during insertions/deletions. Linked lists offer dynamic sizing and head insertions/deletions without element shifting, but require sequential access and incur pointer memory overhead.
Write an efficient iterative C function to reverse a singly linked list in-place by manipulating node pointers. What is its time and auxiliary space complexity?
Algorithm Principle: Maintain three pointers during traversal:
prev: points to the reversed prefix list (initiallyNULL).curr: points to the node currently being processed (initiallyhead).next: temporarily holds the forward pointercurr->next.
C Implementation:
typedef struct Node {
int data;
struct Node *next;
} Node;
Node* reverseList(Node *head) {
Node *prev = NULL;
Node *curr = head;
Node *next = NULL;
while (curr != NULL) {
next = curr->next; // 1. Store next node
curr->next = prev; // 2. Reverse current node's pointer
prev = curr; // 3. Advance prev
curr = next; // 4. Advance curr
}
return prev; // prev is the new head of reversed list
}The iterative reversal function traverses the list in a single pass with time complexity and auxiliary space complexity, returning prev as the new head pointer.
Write complete C algorithms/functions to implement push and pop operations for a stack using a singly linked list. Explain how this eliminates the stack overflow limitation.
Stack Implementation via Linked List: The top pointer points to the first node of the list. All insertions (push) and deletions (pop) take place strictly at the head node.
C Code for Push and Pop:
#include <stdio.h>
#include <stdlib.h>
typedef struct StackNode {
int data;
struct StackNode *next;
} StackNode;
void push(StackNode **top, int val) {
StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
if (newNode == NULL) {
printf("Heap Memory Exhausted (Stack Overflow)!\n");
return;
}
newNode->data = val;
newNode->next = *top;
*top = newNode;
}
int pop(StackNode **top) {
if (*top == NULL) {
printf("Stack Underflow! Stack is empty\n");
return -1;
}
StackNode *temp = *top;
int poppedVal = temp->data;
*top = (*top)->next;
free(temp);
return poppedVal;
}Eliminating Stack Overflow: Unlike array stacks constrained by a fixed compile-time capacity MAX, the linked stack allocates memory nodes dynamically from the runtime heap. Overflow can only occur in the rare physical event that the operating system runs out of virtual memory.
In a linked stack, push inserts a new node at the head and pop removes the node from the head, both executing in time. This eliminates compile-time array overflow because memory is allocated dynamically from heap space as needed.
Perform linked list addition of the following two single-variable polynomials:
State the resulting polynomial and evaluate its value at .
Matching terms by descending exponent:
- Exponent 4:
- Exponent 3: No term in , term in
- Exponent 2:
- Exponent 1: No term in , term in
- Exponent 0:
Sum polynomial:
Evaluating at :
Checking with direct inputs:
The sum polynomial is . Evaluating at yields .
Describe the pointer manipulations required to delete a node at position in a doubly linked list. What boundary conditions must be handled?
Boundary Conditions to Handle:
- Empty list: If
head == NULL, deletion is impossible (underflow). - Deleting head node ():
- Advance
head = head->next. - If new
head != NULL, sethead->prev = NULL. - Free the original head node.
- Advance
- Deleting tail node:
- Predecessor node becomes new tail:
prevNode->next = NULL. - Free tail node.
- Predecessor node becomes new tail:
- Deleting middle node:
- Both forward and backward links must bridge across the target node.
Algorithmic Steps for Middle Node Deletion: Given curr is the node at position :
curr->prev->next = curr->next;
if (curr->next != NULL) {
curr->next->prev = curr->prev;
}
free(curr);Deleting a node in a doubly linked list requires updating curr->prev->next = curr->next and curr->next->prev = curr->prev before freeing curr. Special checks must handle deleting the head node (head = head->next), deleting the tail node (next is NULL), and attempting deletion from an empty list.
What is a circular singly linked list? Write a C algorithm to count and return the total number of nodes in a circular singly linked list.
Definition of Circular Singly Linked List: A circular singly linked list is a linked list where the final node's next pointer points back to the head node rather than NULL. As a result, every node has a non-null successor, and the list can be traversed infinitely in a cycle.
Node Counting Algorithm in C:
int countNodes(Node *head) {
if (head == NULL) {
return 0;
}
int count = 0;
Node *curr = head;
do {
count++;
curr = curr->next;
} while (curr != head);
return count;
}A circular singly linked list has its last node's next pointer referring to the head node. The counting algorithm traverses using a do-while loop starting at head and increments a counter until curr circles back to head, running in time.