Unit 3: Introduction to Linked Lists

I. Orientation — Dynamic, Link-Based Data Organization

A linked list is a dynamic linear data structure whose elements, called nodes, are connected through links rather than stored in consecutive memory locations. Its structure depends on references or pointers that preserve the logical order of nodes.

Defining characteristics:

• Node-based storage: Each node contains data and at least one link to another node.
• Non-contiguous allocation: Nodes may occupy unrelated memory locations.
• Dynamic size: Nodes can be allocated and released while a program runs.
• Sequential access: Reaching a node normally requires following links from the first node.
• Pointer-dependent structure: Incorrect pointer updates can lose nodes or break the list.

A. Definition of linked list

A linked list is an ordered collection of nodes in which links establish the position of each element.

• Node: A self-referential structure containing:
  • Data field: Stores a value such as 25.
  • Link field: Stores the address of another node.
• Head pointer: head stores the address of the first node; head = NULL represents an empty list.
• Final node: Its link contains NULL, marking the end.
• Logical arrangement: A list containing 10, 20, and 30 is represented as:

head → [10 | next] → [20 | next] → [30 | NULL]

• Array contrast: An array supports direct indexing, whereas a linked list generally requires sequential traversal but permits insertion without shifting later elements.

II. Singly Linked Lists — One-Way Node Connections

A singly linked list gives each node one link, pointing to its immediate successor. Movement therefore proceeds from the head toward the final node only.

A. Implementation of singly linked list

A singly linked list is implemented using a node type and a pointer identifying its first node.

• Node declaration: In C-like notation, each node stores an integer and a pointer to the same structure type.

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

struct Node *head = NULL;

• Field meanings:
  • data is the value stored in the node.
  • next is the address of the succeeding node.
  • head is the entry point to the complete list.
• Dynamic allocation: A new node is commonly obtained from heap memory, its data initialized, and its next field connected before head or another link is changed.
• Invariant: Every reachable node except the last points to another valid node; the last points to NULL.

B. Singly linked list traversal

Traversal visits nodes sequentially by following each next pointer until NULL is reached.

• Procedure: Use a temporary pointer so that head remains unchanged.

current ← head
while current ≠ NULL
    process current.data
    current ← current.next

• Symbols: current is the node being visited; process may display, count, search, or modify its data.
• Complexity: Visiting all n nodes takes O(n) time and O(1) auxiliary space.
• Empty case: If head = NULL, the loop performs no iterations.

C. Singly linked list insertion

Insertion creates a node and reconnects links so that the new node becomes reachable without losing the existing list.

• At the beginning: Connect the new node to the old first node, then update head.

new.next ← head
head ← new

This operation takes O(1) time.

• After a known node: If position identifies the preceding node:

new.next ← position.next
position.next ← new

The order is essential: replacing position.next first would lose the remainder of the list.

• At the end: Set new.next ← NULL, traverse to the last node, and set last.next ← new. This takes O(n) without a tail pointer but O(1) when a maintained tail is available.
• Empty list: For the first node, both head and, when used, tail point to new.

D. Singly linked list deletion

Deletion disconnects a target node, preserves the surrounding links, and releases the removed node’s memory.

• From the beginning: Save the first node, advance head, and deallocate the saved node.

target ← head
head ← head.next
free target

• After a known predecessor: If previous.next is the target:

target ← previous.next
previous.next ← target.next
free target

• By value: Search while maintaining both current and previous; deleting current then requires linking previous.next to current.next.
• Last-node update: If a tail pointer is maintained and the last node is removed, tail must become its predecessor. If the only node is removed, set both head and tail to NULL.
• Complexity: Unlinking a known node is O(1), but locating a value or predecessor may require O(n) time.

E. Linked list underflow and overflow conditions

Underflow and overflow describe unsuccessful deletion and insertion conditions respectively.

1. Underflow: Deletion is impossible when the list is empty.

   • Concrete condition: head = NULL.
   • Required response: Report the condition or return safely without dereferencing head.

2. Overflow: Insertion fails when memory for a new node cannot be allocated.

   • Concrete condition: An allocation operation returns NULL.
   • Required response: Do not alter any existing links; report allocation failure.
   • Distinction from arrays: A linked list has no fixed capacity, so overflow depends on available memory rather than a predetermined number of positions.

III. Trees — Hierarchical Data Structures

Trees organize data hierarchically rather than linearly. Their nodes are connected by edges, beginning from a distinguished root and branching into zero or more descendants.

A. Introduction to trees

A tree is a connected, acyclic structure in which every node except the root has exactly one parent.

• Hierarchy: Trees represent relationships such as file directories, organization charts, and expression structures.
• Connectivity: Every node is reachable from the root through a unique path.
• Acyclic property: No route can begin at a node, follow distinct edges, and return to that node.
• Size relationship: A non-empty tree with n nodes has exactly n − 1 edges.
• Recursive structure: Each child and its descendants form a smaller tree called a subtree.

B. Tree terminology: root, edge, parent, child, siblings, leaf, degree, level, height, depth, path and subtree

Tree terminology precisely describes the position and relationship of nodes.

• Root: The unique topmost node; it has no parent.
• Edge: A connection between two directly related nodes, such as (A, B).
• Parent and child: If an edge leads downward from A to B, then A is B’s parent and B is A’s child.
• Siblings: Nodes sharing the same parent; for example, B and C are siblings if both are children of A.
• Leaf: A node with no children; its degree is 0.
• Degree:
  • Node degree: Number of children of that node.
  • Tree degree: Maximum node degree anywhere in the tree.
• Depth: Number of edges from the root to a node; the root has depth 0.
• Level: Commonly depth + 1, making the root level 1; some conventions instead use level 0, so the convention must remain consistent.
• Height: Number of edges on the longest downward path from a node to a leaf. A leaf has height 0; tree height is the root’s height.
• Path: A sequence of connected nodes, such as A → B → D; its length is the number of edges, here 2.
• Subtree: A node together with all its descendants, preserving their original edges.

IV. Binary Trees — Restricted Branching

A binary tree is a tree in which each node has at most two children, conventionally distinguished as left and right.

A. Conceptual understanding of binary trees

Binary trees use ordered child positions, so left and right children are structurally different even when only one child exists.

• Maximum degree: Every node has degree 0, 1, or 2.
• Maximum nodes at depth d: At most 2^d nodes can occur, where root depth is 0.
• Maximum nodes by height h: A binary tree of height h contains at most 2^(h+1) − 1 nodes.
• Common forms:
  • Full binary tree: Every node has either zero or two children.
  • Complete binary tree: All levels except possibly the last are full, and the final level fills left to right.
  • Perfect binary tree: Every internal node has two children and all leaves have equal depth.
• Use: Binary trees support hierarchical searching, expression evaluation, priority structures, and traversal algorithms.

V. Binary Search Trees — Ordered Binary Trees

A binary search tree (BST) is a binary tree whose node keys satisfy an ordering rule that guides searching.

A. Conceptual understanding of binary search trees

For each node with key k, keys in its left subtree are less than k, while keys in its right subtree are greater than k, assuming duplicates are disallowed.

• Search process: Compare the target with the current key:
  • Move left when the target is smaller.
  • Move right when the target is larger.
  • Stop when equal or when a NULL link is reached.
• Insertion: Follow the same comparisons until a NULL child position is found, then attach the new node there.
• Example: Inserting 50, 30, 70, 40 makes 50 the root, 30 its left child, 70 its right child, and 40 the right child of 30.
• Efficiency: Search and insertion take O(h), where h is tree height—approximately O(log n) in a balanced BST but O(n) in a skewed tree.
• Ordering benefit: Inorder traversal of a BST produces keys in ascending order.

VI. Depth-First Tree Traversals — Systematic Node Visiting

Depth-first traversals visit every node once but differ in whether the root is processed before, between, or after its subtrees.

A. Preorder traversal

Preorder processes the root before recursively visiting the left and right subtrees.

• Order: Root → Left → Right.

PREORDER(node)
    if node ≠ NULL
        visit node
        PREORDER(node.left)
        PREORDER(node.right)

• Use: Suitable for copying a tree or producing prefix notation from an expression tree.
• Example: For root A with children B and C, the order is A, B, C.

B. Inorder traversal

Inorder visits the left subtree, processes the root, and then visits the right subtree.

• Order: Left → Root → Right.

INORDER(node)
    if node ≠ NULL
        INORDER(node.left)
        visit node
        INORDER(node.right)

• Use: Produces ascending keys when applied to a BST.
• Example: For BST root 20 with children 10 and 30, the order is 10, 20, 30.

C. Postorder traversal

Postorder processes the root only after visiting both subtrees.

• Order: Left → Right → Root.

POSTORDER(node)
    if node ≠ NULL
        POSTORDER(node.left)
        POSTORDER(node.right)
        visit node

• Use: Appropriate for deleting a tree because children are processed before their parent.
• Complexity: Preorder, inorder, and postorder each take O(n) time and use O(h) recursive stack space for n nodes and height h.