Linked Lists

A linked list is a dynamic data structure built from small units called nodes. Each node holds two things: a piece of data and a pointer (a reference) to the next node in the chain. Unlike an array, the nodes need not sit next to one another in memory; the pointers are what hold the list together. This lets a linked list grow and shrink freely, one node at a time, which is its central advantage over the fixed-size array.

Nodes and pointers

A node is usually described as a small record with two fields:

NODE
    DATA        // the value stored, e.g. a number or name
    NEXT        // a pointer to the following node, or NULL if none

A special pointer called head refers to the first node. The last node's NEXT pointer holds the value NULL (sometimes written null or nil), signaling the end of