Lists

The counter answered the “how many” question with a single number. The library’s second question cannot be answered with a number: who is waiting for a popular book, and in what order. In a waiting list, the order itself is part of the information; if the store is to preserve it, it has to hold every member individually, together with their position.

A list is a single structure with two distinct uses. A queue appears when items are added at one end and removed from the other: the waiting list works this way, first come, first served. A stack appears when items are added and removed from the same end: a clerk undoing their last action works this way. From the store’s point of view, the difference is not in the structure, it is in which end is chosen. The real question is this: what does constant-step access from both ends cost in memory.

The Same Workload, Three Implementations

DS1: 20,000 requests are added to the waiting list from the back, a front pickup happens after every fourth request (5,000 removals), and a priority request is moved to the front every fortieth request (500 insertions); 25,500 operations total. DS2: an array slot is 8 bytes, a linked node’s extra cost is 24 bytes (previous and next pointers plus the node header), overhead per structure is 56 bytes. DS3: the ring buffer starts with 1,024 slots and doubles its capacity once full; copy steps are counted.

// memory/list.mjs — the same waiting-list workload in three implementations. Step and
// byte counters live inside the structure itself; the workload is deterministic.
const OVERHEAD = 56, SLOT = 8, NODE_OVERHEAD = 24;   // DS2

class ArrayList {                              // contiguous array: a front operation shifts everything
  #items = []; steps = 0;
  pushBack(v) { this.steps += 1; this.#items.push(v); }
  pushFront(v) { this.steps += this.#items.length + 1; this.#items.unshift(v); }
  popFront() { this.steps += this.#items.length; return this.#items.shift(); }
  get length() { return this.#items.length; }
  get bytes() { return OVERHEAD + this.#items.reduce((t, v) => t + Buffer.byteLength(v) + SLOT, 0); }
  rank(v) { let n = 0; for (const x of this.#items) { n += 1; if (x === v) return n; } return -1; }
}

class LinkedList {                             // constant single step from both ends; extra pointer per node
  #head = null; #tail = null; #n = 0; #b = 0; steps = 0;
  #node(v) { this.#n += 1; this.#b += Buffer.byteLength(v) + SLOT + NODE_OVERHEAD; return { v, prev: null, next: null }; }
  pushBack(v) { this.steps += 1; const node = this.#node(v);
    node.prev = this.#tail; if (this.#tail) this.#tail.next = node; else this.#head = node; this.#tail = node; }
  pushFront(v) { this.steps += 1; const node = this.#node(v);
    node.next = this.#head; if (this.#head) this.#head.prev = node; else this.#tail = node; this.#head = node; }
  popFront() { this.steps += 1; const node = this.#head; if (!node) return undefined;
    this.#head = node.next; if (this.#head) this.#head.prev = null; else this.#tail = null;
    this.#n -= 1; this.#b -= Buffer.byteLength(node.v) + SLOT + NODE_OVERHEAD; return node.v; }
  get length() { return this.#n; }
  get bytes() { return OVERHEAD + this.#b; }
  rank(v) { let n = 0; for (let node = this.#head; node; node = node.next) { n += 1; if (node.v === v) return n; } return -1; }
}

class RingBuffer {                             // fixed slots; capacity doubles once full
  #slots; #head = 0; #n = 0; steps = 0; copies = 0; growths = 0;
  constructor(capacity) { this.#slots = new Array(capacity); }
  #grow() { if (this.#n < this.#slots.length) return;
    const grown = new Array(this.#slots.length * 2);
    for (let i = 0; i < this.#n; i += 1) grown[i] = this.#slots[(this.#head + i) % this.#slots.length];
    this.steps += this.#n; this.copies += this.#n; this.growths += 1; this.#slots = grown; this.#head = 0; }
  pushBack(v) { this.#grow(); this.steps += 1; this.#slots[(this.#head + this.#n) % this.#slots.length] = v; this.#n += 1; }
  pushFront(v) { this.#grow(); this.steps += 1;
    this.#head = (this.#head - 1 + this.#slots.length) % this.#slots.length; this.#slots[this.#head] = v; this.#n += 1; }
  popFront() { this.steps += 1; if (this.#n === 0) return undefined;
    const v = this.#slots[this.#head]; this.#slots[this.#head] = undefined;
    this.#head = (this.#head + 1) % this.#slots.length; this.#n -= 1; return v; }
  get length() { return this.#n; }
  get capacity() { return this.#slots.length; }
  get bytes() { let d = 0;
    for (let i = 0; i < this.#n; i += 1) d += Buffer.byteLength(this.#slots[(this.#head + i) % this.#slots.length]);
    return OVERHEAD + this.#slots.length * SLOT + d; }
  rank(v) { for (let i = 0; i < this.#n; i += 1) if (this.#slots[(this.#head + i) % this.#slots.length] === v) return i + 1; return -1; }
}

// --- workload: 20,000 requests to the back, 1 front pop every 4 requests, 1 priority push to the front every 40 requests
const REQUESTS = 20_000;
const value = (i) => `${10_000 + i}:${40_000 + i * 2}`;
const operations = [];
for (let i = 1; i <= REQUESTS; i += 1) {
  operations.push(["back", value(i)]);
  if (i % 4 === 0) operations.push(["pop", null]);
  if (i % 40 === 0) operations.push(["front", `9${value(i)}`]);
}
const run = (list) => { for (const [op, v] of operations) {
  if (op === "back") list.pushBack(v); else if (op === "front") list.pushFront(v); else list.popFront(); } return list; };

const ring = new RingBuffer(1024);
const structures = [["contiguous array", run(new ArrayList())], ["linked node", run(new LinkedList())],
  ["ring buffer", run(ring)]];
console.log(`${operations.length} operations (${REQUESTS} to the back, ${REQUESTS / 4} pops from the front, ${REQUESTS / 40} to the front)`);
console.log(`${"structure".padEnd(15)}${"length".padStart(9)}${"bytes held".padStart(14)}` +
  `${"per entry".padStart(13)}${"total steps".padStart(13)}${"per operation".padStart(14)}`);
for (const [name, list] of structures)
  console.log(name.padEnd(15) + String(list.length).padStart(9) + String(list.bytes).padStart(14) +
    (list.bytes / list.length).toFixed(1).padStart(13) + String(list.steps).padStart(13) +
    (list.steps / operations.length).toFixed(1).padStart(14));
console.log(`ring buffer: ${ring.growths} growths, ${ring.copies} copy steps, capacity ${ring.capacity}, ` +
  `empty slots ${ring.capacity - ring.length}`);

const target = value(19_000);
console.log(`\n"${target}" ranked at: ` + structures.map(([name, list]) => `${name} -> rank ${list.rank(target)}`).join(", "));

25500 operations (20000 to the back, 5000 pops from the front, 500 to the front)
structure         length    bytes held    per entry  total steps per operation
contiguous array    15500        294557         19.0     42662750        1673.0
linked node        15500        666557         43.0        25500           1.0
ring buffer        15500        301629         19.5        40860           1.6
ring buffer: 4 growths, 15360 copy steps, capacity 16384, empty slots 884

"29000:78000" ranked at: contiguous array -> rank 14500, linked node -> rank 14500, ring buffer -> rank 14500

All three structures carry the same 15,500-person waiting list; the bytes they hold and the steps they spend are far apart. The contiguous array is the cheapest at 19.0 bytes per entry, but because every front operation shifts every remaining entry, it spends 1,673 steps per operation; the total for 25,500 operations is 42.7 million steps. Calling one person off the waiting list means moving everyone else’s position.

The linked node reverses this: every operation is exactly 1 step, 25,500 total. Its price is 43.0 bytes per entry — 2.26 times the array’s cost. The difference is purely pointer overhead: every entry carries an extra 24 bytes for two neighbor pointers and the node header. A member identifier itself is 11 bytes, while binding it into the sequence costs 24 — as much space as the data itself goes toward describing the data’s position.

The ring buffer shows the third path, and it is the best purchase for this workload: 19.5 bytes per entry — only 0.5 bytes more than the array — and 1.6 steps per operation. Keeping a head pointer turns removal from the front from a shift into a constant step. Its price is capacity management: starting with 1,024 slots, it has grown four times, spent 15,360 copy steps, and ends up holding 884 empty slots. The only thing the linked node buys over the ring buffer is those 15,360 steps, and its price is 364,928 bytes: 23.8 bytes per step. That is a poor purchase for a waiting list; the decision is set by this ratio, not by the structure’s name.

The last line shows a limit common to all three. A given member’s rank is 14,500 in all three structures, and finding it means walking 14,500 entries. The list holds order but does not provide lookup by order; going from membership to position is a scan in every case.

The Price of Trimming

The second use is the recent-activity list: every loan, return, renewal, and reservation is written to the end of the list, and the clerk panel asks for the “last m events.” If this list is never trimmed, it grows all day. DS4: the day is 43,200 seconds and produces 60,000 events; an entry averages 25.7 bytes. DS5: 2,000 queries arrive, the requested m is skewed toward small values with a visible seed, and a trimmed list is counted at ring-buffer cost.

// memory/trim.mjs — the recent-activity list: holding it unbounded vs. trimming it to
// a fixed length. A trimmed list is counted at ring-buffer cost: 56 + capacity*8 + live value bytes.
const OVERHEAD = 56, SLOT = 8, DAY = 43_200, EVENTS = 60_000, QUERIES = 2_000, SEED = 20240115;
let state = SEED;
const rand = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648;

const KIND = ["loan", "return", "renewal", "reservation"];
const events = Array.from({ length: EVENTS }, (_, i) =>
  `${Math.floor(i * DAY / EVENTS)}|${10_000 + (i * 7919) % 20_000}|${KIND[i % 4]}|${100_000 + (i * 4241) % 200_000}`);
const valueBytes = events.map((e) => Buffer.byteLength(e));
const totalBytes = valueBytes.reduce((t, x) => t + x, 0);

// query: "last m events" — skewed toward small m, seeded
const queries = Array.from({ length: QUERIES }, () => 1 + Math.floor(3_000 * rand() ** 2));

console.log(`${EVENTS} events / ${DAY} s, sample "${events[41]}" (${valueBytes[41]} bytes), ` +
  `average ${(totalBytes / EVENTS).toFixed(1)} bytes`);
console.log(`${QUERIES} queries, largest m ${Math.max(...queries)}, median m ${[...queries].sort((a, b) => a - b)[QUERIES / 2]}`);
console.log(`\n${"limit".padStart(9)}${"bytes held".padStart(14)}${"dropped".padStart(11)}` +
  `${"covered s".padStart(13)}${"queries satisfied".padStart(19)}${"rate".padStart(8)}`);
for (const k of [100, 1_000, 10_000, EVENTS]) {
  const live = events.slice(EVENTS - k);
  const bytes = OVERHEAD + k * SLOT + valueBytes.slice(EVENTS - k).reduce((t, x) => t + x, 0);
  const span = Number(live.at(-1).split("|")[0]) - Number(live[0].split("|")[0]);
  const satisfied = queries.filter((m) => m <= k).length;
  console.log(String(k === EVENTS ? "unbounded" : k).padStart(9) + String(bytes).padStart(14) +
    String(EVENTS - k).padStart(11) + String(span).padStart(13) +
    String(satisfied).padStart(19) + `%${(100 * satisfied / QUERIES).toFixed(1)}`.padStart(8));
}

60000 events / 43200 s, sample "29|14679|return|273881" (22 bytes), average 25.7 bytes
2000 queries, largest m 2999, median m 752

    limit    bytes held    dropped    covered s  queries satisfied    rate
      100          3456      59900           71                368   %18.4
     1000         34056      59000          719               1167   %58.4
    10000        340056      50000         7199               2000  %100.0
unbounded       2024625          0        43199               2000  %100.0

The unbounded list closes out the day at 2,024,625 bytes and keeps growing at the same rate the next day; a list has no natural stopping point. The 10,000-entry trim satisfies all 2,000 of the same queries, and it does so with 16.8 percent of the unbounded list’s memory: the 1.7 MB saved costs nothing on the query side.

The covered s column tells us where the cost is. The 10,000-entry list only covers the last 7,199 seconds, that is, two hours; the unbounded list covers twelve hours. Because nobody in this workload asks further back than two hours, the loss is invisible — but invisible does not mean it does not exist. When the limit drops to 1,000, memory falls to 34,056 bytes and the list covers only 719 seconds, twelve minutes; 41.6 percent of queries get an incomplete answer. At the 100 limit, coverage drops to 71 seconds and the satisfied rate falls to 18.4 percent.

The real warning here is not in the numbers themselves, it is in the shape of the error. A trimmed list does not say “I do not have it”; it gives whatever it has. A query asking for 2,400 events gets 1,000 records back from a 1,000-entry list and uses the answer without knowing it is incomplete. The limit is chosen where the memory budget and the query distribution intersect, and once the distribution shifts, it silently starts producing wrong answers.

Summary

• A queue and a stack are not separate structures; they are which end of the same list items are added to and removed from. The waiting list is a queue, the clerk’s undo sequence is a stack.
• Across the same 25,500 operations, the contiguous array holds 19.0 bytes per entry but spends 1,673 steps per operation; the linked node drops to 1 step per operation and demands 43.0 bytes per entry (2.26 times).
• The ring buffer closes the gap between the two: 19.5 bytes and 1.6 steps. The 15,360 steps the linked node buys over it are priced at 364,928 bytes — 23.8 bytes per step.
• Rank lookup is a scan in all three structures: the target entry ranks 14,500th and finding it takes 14,500 steps. The list holds order but does not provide lookup by order.
• The recent-activity list closes out the day at 2,024,625 bytes when it is never trimmed, and it has no stopping point. A 10,000-entry limit cuts memory to 16.8 percent and satisfies all 2,000 queries in this workload.
• The real price of trimming is the covered time window: 10,000 entries cover two hours, 1,000 entries cover twelve minutes. A trimmed list does not report that its answer is incomplete; it gives whatever it has.

Next Step

Everything placed in the store up to this point has been a single-piece value: a session record is a whole, a counter is a number, a list entry is a string. The library’s actual record is not like that. A book has a title, an author, a shelf code, a status, and a loan count; status changes several times an hour while the title never changes. Holding the whole record as a single value means writing the whole record to update a single field. The next lesson builds this record in two more shapes and measures three things: the bytes written on a single-field update, the bytes read on a single-field read, and the overhead share that managing fields separately asks back.