Linked List - PCCST303

Picture a treasure hunt: each clue tells you where to find the next one. You don't need to know the location of every clue in advance, you just need to be holding the current one, since it always tells you where to go next. A linked list stores data the same way: each piece of data comes with directions to the next piece.

Node and self-referential structure

Definition

A linked list is a collection of nodes where each node stores data and a link (pointer) to the next node. The nodes do not need to occupy consecutive memory locations, the links alone maintain the logical order.

A single node holds a value and a pointer to the next node. A complete list, three nodes long:

HEAD

↓

NULL

datanext

HEAD points to the first node. The last node's link is NULL, marking the end of the list. In C, a node is written as:

struct node {
    int data;
    struct node *next;
};

KTU PYQ

KTU PYQ, November 2025, 3 marks: "What is a self-referential structure? Give an example."

This is called a self-referential structure, because next is a pointer to another object of the same structure type, a struct node pointing to another struct node.

A self-referential structure is a structure that contains a pointer referring to another object of the same structure type:

struct node {
    int data;
    struct node *next;
};

Here, next can point to another struct node.

Nodes are typically created dynamically:

struct node *newNode;
newNode = (struct node *) malloc(sizeof(struct node));
newNode->data = 10;
newNode->next = NULL;

malloc() obtains memory for the new node at runtime; free() releases a node's memory once it's no longer needed.

Why not just use an array?

Suppose a sorted array holds 10, 20, 30, 40 and a new value, 15, needs to go between 10 and 20. Every element from 20 onward has to shift one position to the right to make room. Deleting an element requires the same kind of shift, in reverse, to close the gap.

A linked list avoids this. To insert between two nodes, only two links change, nothing else in the list moves:

Before: [10] → [20] → [30] → [40]
 
Insert 15 between 10 and 20:
 
10->next = 15
15->next = 20
 
After:  [10] → [15] → [20] → [30] → [40]

That flexibility comes at a cost: an array offers direct indexed access (arr[i] in constant time), but a linked list has no indices. Reaching the fifth node means following four links from the head, one at a time.

Feature	Array	Linked List
Storage	Usually contiguous	Nodes may be anywhere in memory
Direct access	O(1)	O(n)
Size	Usually fixed for a basic array	Grows or shrinks dynamically
Insertion / deletion	May require shifting elements	Only pointer changes, once the position is found
Extra memory	No link field	One or more pointer fields per node

Key Idea

A linked list trades away direct indexed access in exchange for cheap insertion and deletion anywhere in the structure, useful whenever the size is unpredictable or elements are added/removed frequently.

Applications

Dynamic collections: any structure whose size isn't known in advance, and that grows or shrinks often, benefits from a linked list's ability to allocate nodes on demand rather than reserving a fixed block up front.
Building blocks for other structures: stacks and queues can both be implemented on top of a linked list instead of an array, avoiding a fixed capacity limit, covered next in this module.
Sparse data: representations that only need to store the non-zero or "present" elements of a larger conceptual sequence, such as a polynomial's non-zero terms, can use one node per meaningful entry instead of reserving space for every possible position.

Quick recall

A linked list stores data as nodes, each holding a value and a pointer to the next node; nodes need not be contiguous in memory.
A self-referential structure is a structure containing a pointer to another object of the same structure type, exactly what a node's next field is.
Compared to an array, a linked list gives up O(1) indexed access in exchange for O(1) insertion/deletion once the position is known, no shifting required.