Unit 2: Linked Lists

I. Orientation

A linked list is a dynamic linear data structure made of nodes whose logical order is established by links rather than by consecutive memory addresses. Each node stores data and one or more references to other nodes, allowing the structure to grow, shrink, and reorganize during execution.

A. Defining Characteristics

The following properties govern all linked-list forms and operations in this unit.

• Node structure: A node contains a data field and at least one link field; a singly linked node is represented as (INFO, LINK).
• Logical order: If node A links to node B, then B logically follows A, even when their physical memory addresses are far apart.
• Access point: A pointer such as START, HEAD, or FIRST identifies the beginning of the list.
• Termination convention: A grounded list ends with NULL; a circular list ends by linking back to its header or first node.
• Dynamic size: Nodes are allocated and released at runtime, so list capacity is limited mainly by available memory.
• Sequential access: Reaching the node at position i requires following links from an access point, giving O(i) access time.
• Pointer discipline: Links must be updated in the correct order; losing the only pointer to a node can make that node inaccessible.

II. Singly Linked Lists — Structure and Fundamental Algorithms

A singly linked list consists of nodes with one directional link each. For a node p, INFO[p] stores its value and LINK[p] identifies its successor.

A. Introduction to linked lists

A singly linked list represents a sequence by connecting each node to the next node.

• Abstract form: A list containing 10, 20, and 30 is represented as START -> 10 -> 20 -> 30 -> NULL.
• Empty list: START = NULL indicates that no data node exists.
• First node: START stores the address of the node containing the first element.
• Last node: The final node is identified by LINK[last] = NULL.
• Array contrast:
  1. Array: Elements occupy contiguous memory and support O(1) indexed access, but resizing or middle insertion may be costly.
  2. Linked list: Nodes may occupy noncontiguous memory; access is sequential, but insertion after a known node is O(1).
• Common uses: Linked lists support stacks, queues, adjacency lists, polynomial representation, sparse structures, and free-memory lists.
• Main cost: Every node requires extra storage for its link, and pointer traversal usually has poorer cache locality than array traversal.

B. Memory representation

Memory representation separates the physical placement of nodes from their logical sequence.

• Node layout: A conceptual singly linked node may be declared as:

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

• Concrete example: Suppose nodes are stored at addresses 1200, 3050, and 2140.

• Interpretation: With START = 1200, following next produces 10, 20, 30; address order does not determine list order.
• Link value: A link stores an address or reference, not the successor’s data value.
• Self-referential type: struct Node *next points to another object of the same node type.
• Representation overhead: If data needs d bytes and a pointer needs p bytes, each node requires approximately d + p bytes, excluding padding and allocator metadata.

C. Memory allocation

Memory allocation obtains storage for new nodes and returns deleted nodes to the available-memory pool.

• Dynamic allocation: In C, malloc(sizeof(struct Node)) requests one node during execution.
• Allocation check: A NULL result means that allocation failed and must be handled before fields are accessed.
• Initialization: Both fields should be assigned before the node becomes reachable.

struct Node *new_node = malloc(sizeof *new_node);
if (new_node != NULL) {
    new_node->data = value;
    new_node->next = NULL;
}

• Deallocation: free(p) returns the node addressed by p; p must not be dereferenced afterward.
• Free-list model: In an array-based representation, AVAIL may point to the first unused node, while each free node links to the next available location.
• Memory leak: Removing a node’s links without releasing or retaining its address leaves allocated memory unusable.
• Dangling pointer: A pointer that still refers to released storage is invalid and can cause undefined behavior if accessed.

D. Traversal

Traversal visits nodes in logical order by repeatedly following their links.

• Algorithm: Start at START, process the current node, and advance until the pointer becomes NULL.

p <- START
while p != NULL do
    VISIT(INFO[p])
    p <- LINK[p]
end while

• Symbols: p is the current-node pointer; INFO[p] is its data; LINK[p] is its successor; VISIT performs the required action.
• Invariant: At the beginning of each iteration, p identifies the next unprocessed node.
• Complexity: Visiting all n nodes takes O(n) time and O(1) auxiliary space.
• Searching: A linear search stops when INFO[p] = key or p = NULL; its worst-case time is O(n).
• Safety condition: The program must test p != NULL before reading INFO[p] or LINK[p].

E. Insertion

Insertion creates a node and changes links so that the node occupies the required logical position.

• At the beginning: The new node points to the old first node, after which START is redirected.

LINK[new] <- START
START <- new

• After a known node: For predecessor loc, preserve its old successor before replacing the link.

LINK[new] <- LINK[loc]
LINK[loc] <- new

• At the end: Traverse to the node whose link is NULL, then set that link to new; set LINK[new] <- NULL.
• Empty-list case: When START = NULL, both beginning and end insertion set START <- new.
• Ordering requirement: Assigning LINK[loc] <- new before saving the old successor can disconnect the remainder of the list.
• Complexity: Insertion at the front or after a known node is O(1); finding a position or tail may require O(n) time.

F. Deletion

Deletion disconnects a target node while preserving the links among all remaining nodes.

• Delete the first node: Save its address, advance START, and release the saved node.

temp <- START
START <- LINK[START]
RELEASE(temp)

• Delete after a known predecessor: If target <- LINK[prev], bypass it with LINK[prev] <- LINK[target], then release target.
• Delete by key: Traverse with prev and curr until INFO[curr] = key; the first node requires separate handling because it has no predecessor.
• Empty-list condition: If START = NULL, deletion cannot proceed and should report underflow or “not found.”
• Last-node result: Deleting the only node changes START to NULL.
• Complexity: Deleting after a known predecessor is O(1); locating a key is O(n).
• Critical rule: Read the target’s successor before releasing the target, because released storage must not be accessed.

III. Header Linked Lists — Sentinel-Based Organization

A header linked list begins with a special header node that is always present. The header usually does not represent an ordinary list element; it may store metadata such as node count or may act only as a sentinel.

A. Grounded header linked lists

A grounded header linked list has a permanent header node and terminates with a NULL link.

• Representation: HEAD -> data₁ -> data₂ -> ... -> dataₙ -> NULL.
• Empty condition: LINK[HEAD] = NULL; HEAD itself still exists.
• Simplified insertion: Every data node has a predecessor, so inserting before the first data node is performed after HEAD.
• Simplified deletion: Deleting the first data node uses the same bypass operation as other deletions:

target <- LINK[HEAD]
LINK[HEAD] <- LINK[target]
RELEASE(target)

• Metadata option: INFO[HEAD] may store the number of data nodes n, updated after every successful insertion or deletion.
• Trade-off: One extra node is required, but boundary cases become more uniform.

B. Circular header linked lists

A circular header linked list connects the final data node back to the header instead of using NULL.

• Representation: HEAD -> data₁ -> ... -> dataₙ -> HEAD.
• Empty condition: LINK[HEAD] = HEAD, making the header a self-loop.
• Traversal boundary: Processing starts at LINK[HEAD] and stops when the current pointer again equals HEAD.

p <- LINK[HEAD]
while p != HEAD do
    VISIT(INFO[p])
    p <- LINK[p]
end while

• Circular benefit: Starting from any node, repeated link-following eventually returns to that node or the header; this suits cyclic scheduling and round-robin processing.
• Termination risk: Testing p != NULL is incorrect because a properly formed circular list contains no null terminal link.
• Tail insertion: With a maintained TAIL pointer, insertion at the end is O(1) by linking TAIL to new, new to HEAD, and updating TAIL.

IV. Doubly Linked Lists — Bidirectional Navigation

A doubly, or two-way, linked list gives each node links to both its predecessor and successor. A node is represented as (PREV, INFO, NEXT), enabling movement in either direction.

A. Two-way lists

A two-way list maintains reciprocal links between each adjacent pair of nodes.

• Node declaration:

struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
};

• Bidirectional invariant: If x->next = y, then y->prev = x; both relations must be updated together.
• Boundaries: In a grounded form, FIRST->prev = NULL and LAST->next = NULL.
• Forward traversal: Begin at FIRST and repeatedly follow next.
• Backward traversal: Begin at LAST and repeatedly follow prev.
• Advantages: Given a target node, deletion needs no search for its predecessor; reverse traversal is direct.
• Costs: Each node stores two pointers, and insertion or deletion requires more pointer assignments than in a singly linked list.

B. Operations on two-way linked lists

Operations on two-way linked lists must preserve both forward and backward connectivity.

• Insertion after node p: Let q = p->next; connect new between p and q.

new.prev <- p
new.next <- q
p.next <- new
if q != NULL then
    q.prev <- new
else
    LAST <- new
end if

• Insertion before node p: Let q = p->prev; set new->next = p, new->prev = q, and p->prev = new; update q->next or FIRST.
• Deletion of node p:
  1. Left side: If p->prev exists, set its next to p->next; otherwise set FIRST = p->next.
  2. Right side: If p->next exists, set its prev to p->prev; otherwise set LAST = p->prev.
• Release step: Deallocate p only after neighboring links and boundary pointers have been updated.
• Traversal cost: Full forward or reverse traversal is O(n); movement from a known node to either neighbor is O(1).
• Insertion and deletion cost: Given the relevant node address, structural updates are O(1); searching for that node remains O(n).
• Consistency check: After every operation, FIRST = NULL should imply LAST = NULL; otherwise, the list’s boundary state is corrupted.