Chapter 10: Elementary Data Structures: Arrays, Linked Lists, and Trees

Arrays provide contiguous memory storage with constant-time random access but are inflexible for dynamic resizing, and two-dimensional matrices extend this with row-major or column-major layouts. Built atop arrays, stacks implement last-in-first-out (LIFO) behavior through PUSH and POP in O(1) time, while queues implement first-in-first-out (FIFO) behavior through ENQUEUE and DEQUEUE using wrap-around indexing — both requiring careful handling of overflow and underflow conditions. Linked lists offer greater flexibility, with singly linked lists connecting nodes via a next pointer, doubly linked lists adding a prev pointer for O(1) insertion and deletion at known positions, and circular lists connecting the tail back to the head; sentinel dummy nodes simplify boundary cases in doubly linked lists by eliminating special-case logic in LIST-INSERT, LIST-DELETE, and LIST-SEARCH, though searching still requires Θ(n) time in the absence of auxiliary structures. Stacks and queues can equally be implemented with linked lists, gaining dynamic sizing at the cost of pointer overhead. For tree structures, binary trees are represented with per-node parent, left, and right pointers — the root's parent being NIL and missing children indicated by NIL pointers — while general trees with a variable number of children are efficiently handled through the left-child, right-sibling representation, where each node stores a pointer to its first child and a pointer to its next sibling at the same level, consuming only O(n) space and appearing naturally in compiler syntax trees and expression parsers.