PadhaikoAll subjects

Linked List

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

4.1 Definition of list and its operations

Definition

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

Fundamental Operations on List ADT
OperationFunction SignatureDescription
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.

Array Implementation of List ADT in CC
#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


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:

  1. 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.
  2. Memory Inefficiency (Wastage):
    • If an array is sized for elements but holds only , the remaining slots remain allocated and wasted in RAM.
  3. 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.
  4. 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

Definition

Linked List

A linked list is a dynamic linear data structure composed of self-referential structures called nodes. Each node contains two essential parts:

  1. Data field: stores the actual user information.
  2. 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.

Conceptual Anatomy of a Linked ListText
   head
    |
    v
  +------+------+     +------+------+     +------+------+
  | Data | Next |---->| Data | Next |---->| Data | NULL |
  +------+------+     +------+------+     +------+------+
     Node 1              Node 2              Node 3 (Tail)
AspectArray List (Static)Linked List (Dynamic)
Memory AllocationStatic (compile time) in contiguous memory blocksDynamic (runtime via malloc) in scattered heap blocks
Size FlexibilityFixed maximum capacity; susceptible to overflowGrows and shrinks dynamically; limited only by heap RAM
Element AccessDirect / Random access: via indexSequential access: traversal from head
Insert / Delete at HeadExpensive due to element shiftingFast by manipulating pointer references
Insert / Delete at Middle shifting overhead traversal, but pointer rewiring once node is located
Memory OverheadZero extra pointer storageExtra 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.

Singly Linked List Operation Algorithms
OperationAlgorithmic StepsTime Complexity
Insert at BeginningnewNode->next = head; head = newNode;
Insert at EndTraverse 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 Beginningtemp = head; head = head->next; free(temp);
Delete from EndTraverse 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

Definition

Doubly Linked List (DLL)

A doubly linked list is a two-way linked data structure in which every node contains two pointers:

  1. prev: points to the preceding node in the list (head->prev = NULL).
  2. next: points to the succeeding node in the list (tail->next = NULL).
Doubly Linked List StructureText
            head
             |
             v
  NULL <---+----+----+----+      +----+----+----+      +----+----+----+
           |Prev|Data|Next| <---> |Prev|Data|Next| <---> |Prev|Data|Next| ---> NULL
           +----+----+----+      +----+----+----+      +----+----+----+

Advantages and Disadvantages of DLL

4.5.3 Circular Linked List

Definition

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

  1. Circular Singly Linked List (CSLL):
    • The next pointer of the last node points back to head.
    • Traversal terminates when a pointer returns to head (curr->next == head).
  2. Circular Doubly Linked List (CDLL):
    • lastNode->next = head and head->prev = lastNode.
    • Allows seamless circular traversal in both clockwise and counter-clockwise directions.

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:

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):

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:

  1. 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->next and p2 = p2->next.
  2. First Exponent Greater (p1->expo > p2->expo):
    • Insert term (p1->coeff, p1->expo) into the result.
    • Advance p1 = p1->next.
  3. Second Exponent Greater (p2->expo > p1->expo):
    • Insert term (p2->coeff, p2->expo) into the result.
    • Advance p2 = p2->next.
  4. 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

Example 1

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 :

  • curr points to node with value 10.
  • curr->next points to node with value 20.

Rewiring pointers: Allocate newNode with newNode->data = 25.

  1. Connect newNode->next to the successor node:
  1. Connect predecessor to newNode:
Answer:

The resulting list is 10 -> 25 -> 20 -> 30 -> 40 -> NULL. The insertion rewired exactly two pointers without shifting any existing nodes in memory.

Example 2

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->prev points to node [20].
  • Successor node: target->next points to node [40].

Bypassing target in both directions:

  1. Update predecessor's forward link:
  1. Update successor's backward link:
  1. Release memory:
Answer:

After deletion, the doubly linked list becomes [10] <-> [20] <-> [40] <-> NULL. Node [30] is cleanly detached and its allocated memory freed in pointer operations.

Example 3

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:

Polynomial Addition Step-by-Step Trace
StepTerm Term Exponent ComparisonResulting Term Added
1
2(Zero coefficient, term omitted)
3
4

Resultant polynomial: .

Evaluating at :

Verifying directly from inputs:

Answer:

The resulting sum polynomial is . At , the polynomial evaluates to .

Example 4

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(): Save temp = front (10). front = front->next (20). free(temp). List: 20 -> 30 -> NULL. Returns 10.
  • enqueue(40): Allocate node [40]. rear->next = [40]; rear = [40]. List: 20 -> 30 -> 40 -> NULL.
  • dequeue(): Save temp = front (20). front = front->next (30). free(temp). List: 30 -> 40 -> NULL. Returns 20.
Answer:

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

Question 1

Compare and contrast array and linked list implementations of the List ADT with respect to:

  1. Memory allocation and storage layout
  2. Access time for arbitrary elements
  3. Time complexity of insertion and deletion operations

Comparing Architectural Properties:

Array vs Linked List Detailed Comparison
ParameterArray (Sequential List)Linked List (Dynamic List)
Allocation MechanismStatic/contiguous block allocated at compile time (or fixed heap chunk via calloc)Dynamic non-contiguous nodes allocated individually on demand at runtime
Memory UtilizationPotential unused capacity or overflow; no pointer overheadExactly matches required nodes; stores extra link pointers per node
Direct Access TimeInstantaneous 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
Answer:

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.

Question 2

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 (initially NULL).
  • curr: points to the node currently being processed (initially head).
  • next: temporarily holds the forward pointer curr->next.

C Implementation:

Iterative In-Place Reversal of Singly Linked ListC
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
}
Answer:

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.

Question 3

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:

Linked Stack in CC
#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.

Answer:

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.

Question 4

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:

Answer:

The sum polynomial is . Evaluating at yields .

Question 5

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:

  1. Empty list: If head == NULL, deletion is impossible (underflow).
  2. Deleting head node ():
    • Advance head = head->next.
    • If new head != NULL, set head->prev = NULL.
    • Free the original head node.
  3. Deleting tail node:
    • Predecessor node becomes new tail: prevNode->next = NULL.
    • Free tail node.
  4. 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);
Answer:

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.

Question 6

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:

Count Nodes in Circular Singly Linked ListC
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;
}
Answer:

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.

Past exam questions for Data Structure and Algorithms

← QueuesDefinition and tree terminologies · Binary trees · Binary search tree →