Codex @codex  0

A data structure storing entries at numbered positions, usually starting at index zero. The fixed-capacity representation considered here puts equal-sized slots consecutively in computer memory. The number $n$ of occupied slots can be smaller than the capacity; unused slots provide room for later entries. An array of references stores consecutive references, while the objects they identify can be elsewhere. ^[ref]

Let the first slot have abstract address $b$ and each slot occupy $s$ address units. Then indexed access computesFor toy values $b=100$, $s=4$, the slots for $A,B,C$ start at $100,104,108$; index $2$ goes directly to $C$ through $100+2\cdot 4=108$. These are illustrative slot addresses, not observed allocation addresses. Under the word-RAM (random-access machine) model for time complexity, word-sized arithmetic operations and any addressed computer memory access have constant cost, and the addresses and entries fit in words. Thus one array access takes $O(1)$ time in Big O notation, independently of the index. This is the access assumption needed by binary search. ^[ref]

Inserting $X$ after $B$ in an array holding $A,B,C$ with one unused slot produces $A,B,X,C$: first copy $C$ from slot $2$ to slot $3$, then write $X$ into slot $2$. Writing $X$ first would lose $C$ unless it had been saved separately. More generally, insert at index $i$ by copying occupied slots from right to left, then fill the gap; with spare capacity this moves $n-i$ entries and takes $O(1+n-i)$ time in Big O notation, so insertion near the middle has $O(n)$ time complexity. Removing an entry closes the gap by shifting later entries left. ^[ref]

A fixed-capacity array cannot accept another entry when full. A resizable representation can allocate a larger array and copy the entries. Doubling capacity when full gives $O(1)$ append cost by amortized analysis over a sequence starting empty, but a single append that copies $n$ entries still has $O(n)$ worst-case time complexity. The outline is a geometric series: copied capacities $1,2,4,\dots ,2^k$ sum to $2^{k+1}-1$, less than twice the number of appends that triggered the last copy. Middle insertion still pays for its shifts. ^[ref]

A binary search tree stores key-value entries in a binary tree, with distinct keys drawn from a total order. At every vertex, all keys in its left subtree must be smaller than its own key, and all keys in its right subtree must be larger. Thus the entries represent a partial function from keys to values: a key has at most one associated value and may be absent. ^[ref]

Lookup starts at the root of a tree. Compare the target with the current key: equality returns its value, a smaller target continues into the left subtree, and a larger target continues into the right subtree. Reaching an empty subtree reports absence. The ordering rule justifies discarding the other subtree at every step; this is the algorithm correctness argument for lookup. It applies to the entire subtree, even if that subtree contains many vertices. ^[ref]

In the seven-key example, search for $5$. At $4$, the comparison $5>4$ selects the right subtree; at $6$, $5<6$ selects the left subtree; at $5$, equality ends the search. The visited keys are $4\to 6\to 5$, three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of $5$ visits $1\to 2\to 3\to 4\to 5$, five comparisons. Searching for absent key $8$ visits $4,6,7$ in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.

For a nonempty binary search tree of height of a binary tree $h$, lookup inspects at most $h+1$ vertices. Under constant-cost key comparisons and child-reference access, its time complexity is $O(h+1)$ in Big O notation, usually written $O(h)$ for $h\ge 1$. With $n$ entries, $h\le n-1$, giving $O(n)$ worst-case lookup. If the shape is kept balanced so that $h=O(\log n)$, lookup takes $O(\log n)$ for $n\ge 2$. The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. ^[ref]

In a shape with every level full, there are $1+2+\cdots +2^h=2^{h+1}-1$ vertices, a geometric series. This explains how a small height of a binary tree can accommodate many entries. The binary search tree ordering rule alone does not guarantee this shape or logarithmic time complexity. Breadth-first search also gains no logarithmic key-lookup guarantee merely from having a binary tree: in the displayed balanced example, its left-to-right level order is $4,2,6,1,3,5,7$, so it inspects six keys before finding $5$, and an absent target requires all seven. Directed lookup uses the total order to choose one branch.

The ordering requirement includes every ancestor on the graph path from the root of a tree. Consider the smaller binary tree with root key $4$, left child $2$, right child $6$, and right child $3$ under $2$. Key $3$ must satisfy both $2<3$, from its immediate parent in a rooted tree, and $3<4$, from its position in the root's left subtree. Replacing $3$ by $5$ preserves all immediate parent-child comparisons, including $2<5$, but violates $5<4$. Lookup for $5$ would incorrectly go from $4$ to $6$ and then to an empty left subtree, overlooking the stored key.

An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is $2,3,4,6$; on the invalid example it is $2,5,4,6$, exposing the descent from $5$ to $4$. Both seven-key binary search trees yield $1,2,3,4,5,6,7$. The theorem is that an inorder traversal of a finite binary search tree with distinct keys lists every key once in strictly increasing total order. For a short proof outline, use mathematical induction on the number of vertices: each smaller subtree produces its own sorted list, and the full ordering rule places every left key before the current key and every right key after it. Concatenating these three parts preserves strict order. Sedgewick and Wayne's keys method uses this left-current-right order. ^[ref]

This combination is useful and attractive: one data structure supports directed lookup and ordered enumeration. An inorder traversal costs $O(n)$ time complexity for $n$ entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.

// Destination: computer-science.bigb

A binary tree, in the data structure convention used here, is a rooted tree in which each vertex has zero, one or two children in a rooted tree, occupying distinct left and right positions. A single left child and a single right child give different binary trees. A vertex with no children in a rooted tree is called a leaf. An empty binary tree has no root of a tree and is also allowed as a storage case. ^[ref]

For example, give the root of a tree label $4$, its left child label $2$ and its right child label $6$. Attach $1,3$ as the left and right children in a rooted tree of $2$, and $5,7$ as those of $6$. This binary tree has seven vertices, six edges, and height of a binary tree $2$: a longest downward graph path contains two edges. The first diagram below shows this shape alongside the binary tree consisting only of successive right children $1,2,\dots ,7$, whose height of a binary tree is $6$.

Left and right positions specify an ordered shape, not a numerical total order on stored labels. Swapping labels $1$ and $7$ in the first example still gives a binary tree, but destroys the binary search tree property. Nor must a binary tree be balanced: the right-child chain is just as valid. The same shape convention supports a binary heap, a Huffman code, or a binary search tree, each with its own additional rules. The useful idea is to describe two smaller subtrees at each vertex, making structural recursion natural.

Computer science studies how information can be represented and transformed by algorithms, and what those transformations can achieve. Its central questions connect mathematics to practical design: what answer should a procedure produce, why is it correct, and how much work does it require as its input grows? Computability theory asks which tasks can be solved at all; computational complexity theory asks what resources a solution needs.

The beauty is that choosing a representation can change what is feasible. Finding a name among a million entries sounds like a million checks. Store the entries in a sorted array, and binary search needs at most twenty middle-entry comparisons. The order makes each unsuccessful comparison eliminate a whole region of possibilities. A data structure supplies useful organization; an algorithm exploits it; time complexity explains the resulting savings.

Algorithm correctness covers every permitted input, including absent names and empty collections. Time complexity predicts scaling; statistical program profiling investigates a particular implementation.

A data structure organizes stored information together with operations for accessing and changing it. Choosing a data structure means choosing which questions should be cheap to answer: an array supports access by numbered position, a hash table supports lookup by key, and a priority queue supports selecting an item by priority. The operations and their time complexity matter as much as the stored values.

Suppose three requests arrive as $(5,\mathrm{Ada}),(2,\mathrm{Bo}),(4,\mathrm{Cy})$, where the number is a priority and smaller numbers are more urgent. A FIFO queue removes Ada first because she arrived first. A minimum-oriented priority queue removes Bo first because $2$ is the least priority. An array can store the same three records in arrival order, but finding the least priority by scanning this representation takes three key inspections. A binary heap organizes these records so the least priority is immediately available. The information is the same; the representation changes the work needed to use it.

This is a useful design principle: preserve just enough organization for the operations the application needs. Maintaining a sorted array gives the whole order, but moving entries to insert a new key can be expensive. A binary heap keeps a weaker heap order that supports fast repeated selection without maintaining a sorted array. A good data structure makes an algorithm's next step easy.

Encapsulation bundles related program state and operations or hides implementation details behind an interface. Encapsulation in object-oriented programming realizes this through objects and their permitted operations; encapsulation also applies to modules outside object-oriented programs.

The useful boundary is a promise: clients request operations through an API, and the implementation maintains a representation invariant. Instead of proving that every client updates several storage fields consistently, prove that the permitted operations preserve the representation invariant. Information hiding also leaves room to replace the data structure while keeping the client-facing behavior, a property called representation independence.

Bundling state and operations alone does not establish that promise. Representation exposure can let clients bypass the API. A private annotation alone is not a security guarantee: it does not establish correctness of operations, isolation from hostile code or safe handling of shared mutable storage. The examples below concern sequential calls with no concurrent access and no client access to internal storage; they do not claim protection against arbitrary memory modification.

A FIFO queue is a data structure with first-in, first-out behavior: enqueue inserts at the rear, dequeue removes and returns the front, and peek inspects the front without removing it. Removal and inspection require a nonempty FIFO queue, or an explicitly defined empty-case result. Enqueue $A,B,C$ in that order, dequeue $A$, then enqueue $D$: the remaining sequence is $B,C,D$, with $B$ next. A LIFO stack would remove the most recently inserted item instead. A FIFO queue models arrival-order service and supplies the next vertex for breadth-first search; a stochastic service model belongs to queueing theory. ^[ref]

The FIFO queue interface specifies removal order, not time complexity. A linked list with both front and rear pointers supports enqueue, dequeue and peek in $O(1)$ worst-case time under constant-cost pointer operations and allocation, as in Sedgewick and Wayne's implementation. A plain array that deletes its first entry by shifting the remaining $n-1$ entries takes $O(n)$ time per such removal. An array with advancing front and rear indices can avoid these shifts; storage and resizing policies still need analysis. The two-list functional queue gives a different implementation with constant amortized analysis cost along a single sequence of uses. These representation choices matter when deriving the linear time complexity of breadth-first search in Big O notation.

// Destination: computer-science.bigb

A data structure using a bit per allocation unit to mark whether it is available. Its agreement with ownership references is a file-system crash consistency requirement; changing just this structure does not install the owner's update.

A hash function is a function assigning each key in an input set $U$ a value in an output set $B$. Usually $B$ is much smaller: a long name or large integer becomes a small bucket index. Equal keys must receive equal values from the same hash function; different keys may also receive equal values. Such a hash collision means "look in the same place", and does not establish key equality. If $|U|>|B|$, the pigeonhole principle makes some collisions unavoidable.

For example, modular arithmetic gives the hash function $h(k)=k\mathrm{mod}7$, with seven bucket indices $0,\dots ,6$. Store the seven keys $0,2,3,10,11,17,24$: their values are respectively $0,2,3,3,4,3,3$. In particular, $h(3)=h(10)=3$ although $3\ne 10$. A hash table is a data structure that uses these indices to locate records. With separate chaining, each bucket holds a linked list of records, so bucket $3$ retains all four keys $3,10,17,24$. Inserting $10$ must not overwrite $3$ merely because their hash function values agree.

Searching for $10$ computes bucket $3$, then compares the actual keys until it reaches $10$. Searching for absent key $31$ reaches that same bucket and must reject every stored key. This data structure trades a search through all records for a search through one short chain, provided the hash function distributes keys adequately. A fixed hash function can perform poorly on patterned keys: $3,10,17,24$ already demonstrate the problem. A universal hash family introduces controlled randomness to limit the expected value of this extra work. Neither indexing nor a small collision probability inherently supplies encryption or message authentication; a cryptographic hash function has additional requirements such as collision resistance.

An inode is a data structure describing an object in an inode-based file system. For an ordinary file, it records file metadata such as type, owner, access permissions, size and hard link count, together with information locating the contents. In the direct-reference toy layout, inode 42 points to file data blocks 7 and 9; its two names a and b live in directory entries. Other file systems can locate contents differently, so the diagram is a model of the separation rather than a universal storage layout. ^[ref]

An inode number is unique only within its file system among allocated objects. Two different file systems can each have inode 42, referring to unrelated files. POSIX exposes the file system's device identity as st_dev and the file's serial number as st_ino; the pair identifies a file within a running system. Neither the bare inode number nor that pair is a permanent historical identifier: after reclamation, a later file can reuse the number. In particular, comparing an old saved number with a new one does not establish continuity of the file. ^[ref]

The design's appeal is that one inode unifies the file metadata and contents reached through several directory entries. Ritchie and Thompson's original 1974 account explicitly describes a directory entry as a name and an i-number, with the corresponding inode holding ownership, protection, size, content addresses and the hard link count. It gives a concrete early explanation of how names and file identity can evolve separately. ^[ref]

// Target: computer-science.bigb

A data structure representing a sequence through linked list nodes and links between them. In the singly linked representation used here, each linked list node holds an item and a next reference to its successor. head identifies the first linked list node; the final next is null, meaning no successor. An empty linked list has head = null. Sedgewick and Wayne use this representation to implement both a stack and a FIFO queue. ^[ref]

For $A\to B\to C$, place the linked list nodes at conceptual computer memory positions $40,12,76$, respectively. These deliberately separated labels describe a toy layout, not actual pointer values. The sequence order comes from the links, not increasing positions. To read index $2$, begin at head and follow two next references. For index $i$, this takes $i$ link-following steps and $O(1+i)$ time complexity, hence $O(n)$ in the worst case for $n$ linked list nodes, under the constant-cost operations assumed for the array example. ^[ref]

Suppose a reference to the existing linked list node $B$ is already known. To insert a fresh linked list node $X$ after it, first set X.next = B.next, preserving the old successor $C$, and then set B.next = X. The result is $A\to B\to X\to C$; none of the old items moves. Reversing these assignments would read the newly changed B.next and set X.next = X, losing the route to $C$ from head. This is a two-update algorithm correctness argument, rather than a claim that finding the insertion location is free.

The two pointer updates take $O(1)$ time in Big O notation. The complete insertion has $O(1)$ time complexity if the predecessor is already known, allocating and initializing the fixed-size linked list node costs $O(1)$, and copying its item has constant cost. Finding $B$ from head can instead cost $O(n)$; a position described only by an index does not confer the constant-cost advantage. This makes a linked list useful when an algorithm already holds the needed linked list node, or repeatedly works at the front as a stack does.

Deletion similarly needs the incoming link: to remove $X$ after known $B$, set B.next = X.next. A reference to $X$ alone does not identify its predecessor in this singly linked representation. The head is a special case: after checking for a nonempty linked list, remove it with head = head.next. If a tail reference is also maintained, deleting the only linked list node must clear that reference too; a stored length must also be updated. Removing a linked list node from the sequence and reclaiming its storage are separate responsibilities. ^[ref]

There are practical costs beyond Big O notation. Each singly linked linked list node needs a successor reference in addition to its item; separate allocation may add further overhead, while an array can reserve unused capacity. Consecutive array slots can make a scan reuse nearby contents already brought into a memory cache; separated linked list nodes can make link following wait for successive computer memory fetches. These are layout-dependent effects, not a guarantee that every array operation beats every linked list operation on every machine. An array of references can still lead to scattered objects, and linked list nodes can be allocated close together. ^[ref]

A priority queue stores items with comparable priority keys and supports insertion, inspection of a best-priority item, and removal of a best-priority item. Here we use the minimum convention: keys have a total order, and smaller means earlier. The operation peek returns a stored item of minimum priority without removing it; extract-min removes and returns such an item. Both require a nonempty priority queue, or an explicitly specified empty-case result. A maximum-oriented priority queue reverses the choice.

For the requests $(5,\mathrm{Ada}),(2,\mathrm{Bo}),(4,\mathrm{Cy})$, peek returns Bo and leaves all three requests stored. extract-min returns Bo and leaves Ada and Cy; another peek returns Cy. Inserting $(1,\mathrm{Dee})$ now makes Dee the next request selected. This changing collection need not be a sorted array: only the next choice must be available.

Distinct items may share a priority. Inserting $(2,\mathrm{Eli})$ alongside $(2,\mathrm{Bo})$ permits either item to be removed first. A priority queue does not inherently promise arrival order on ties. If that policy matters, compare priority first and a unique increasing arrival number second; the resulting total order makes earlier arrivals win equal-priority ties. This is analogous to the motivation for stable sorting, but it is an extra policy for the priority queue.

The interface specifies behavior; the data structure determines costs. A binary heap implements a priority queue with constant-time peek and logarithmic-time insertion and extract-min, under the cost assumptions below. Scheduling by urgency or by the time of the next event needs exactly this repeated next-item selection. MIT's notes use these applications to motivate the priority queue interface.^[ref]

A stack is a data structure with last-in, first-out behavior: push adds an item at the top, pop removes and returns the top item, and peek inspects it without removal. Push $A,B,C$: successive removals return $C,B,A$. Inspection and removal require a nonempty stack, or a specified empty-case result. A linked list whose head is the top supports all three operations in $O(1)$ worst-case time under constant-cost pointer operations and allocation. The stack interface itself does not fix these costs. ^[ref]

A stack records work that must be resumed in reverse order: the most recent unfinished task is handled first. Depth-first search uses this discipline to finish a newly entered branch before resuming the older branch that led to it. Breadth-first search uses a FIFO queue to resume the oldest pending vertex instead. Both are small interfaces whose removal rule changes the shape of a graph search.