Unit 2: Linked lists

A linked list is a linear collection of nodes, where each node contains data and a pointer (link) to the next node. The first node is reached through a pointer called START (or HEAD); the last node's link is NULL.

cstruct node {
    int data;
    struct node *next;
};
struct node *start = NULL;

New nodes are created at run time with malloc(sizeof(struct node)) and released with free(). Free nodes can also be kept in an AVAIL list (free storage list).

• Traversal: start with ptr = start; while ptr != NULL, process ptr->data and move ptr = ptr->next.
• Search: traverse and compare each node's data with the item: O(n).

• Insert at end: traverse to the last node and set last->next = newnode, with newnode->next = NULL.
• Insert after a given node: newnode->next = loc->next; loc->next = newnode;
• Delete: make the previous node skip the deleted one: prev->next = loc->next; then free(loc). Deleting the first node changes START.

• Doubly linked list: each node has two pointers, prev and next, so it can be traversed in both directions and a node can be deleted without searching for its predecessor. It uses more memory.
• Circular linked list: the last node points back to the first instead of NULL, so the list can be traversed from any node. It is useful for round-robin scheduling.

• Implementing stacks and queues dynamically.
• Polynomial representation and addition: each node stores a coefficient and an exponent.
• Dynamic memory management (free lists).
• Undo/redo, browser back/forward history (doubly linked list) and music playlists (circular list).