Fundamental Data Structures: Memory Layout, Linear Structures & Amortization

Data structures organize, store, and manipulate data in memory. Choosing the appropriate data structure dictates asymptotic time complexity, hardware cache efficiency, and space overhead across applications. This guide covers contiguous arrays, dynamic arrays with amortized analysis, linked lists, stacks, queues, and hardware memory layout.

⚡ Quick Dive

Core Linear Data Structures Complexity Matrix

Data Structure Access (Index) Search (Value) Insertion (Head) Insertion (Tail) Insertion (Middle) Deletion (Head) Deletion (Tail) Space Overhead
Static Array $O(1)$ $O(n)$ N/A N/A N/A N/A N/A $O(1)$ (Zero pointer overhead)
Dynamic Array $O(1)$ $O(n)$ $O(n)$ $O(1)^*$ (Amortized) $O(n)$ $O(n)$ $O(1)$ Capacity padding
Singly Linked List $O(n)$ $O(n)$ $O(1)$ $O(1)$ (with tail) $O(1)^*$ (given node) $O(1)$ $O(n)$ 1 pointer / node
Doubly Linked List $O(n)$ $O(n)$ $O(1)$ $O(1)$ $O(1)^*$ (given node) $O(1)$ $O(1)$ 2 pointers / node
Stack (LIFO) $O(n)$ $O(n)$ $O(1)$ (Push) N/A N/A $O(1)$ (Pop) N/A Minimal
Queue (FIFO) $O(n)$ $O(n)$ N/A $O(1)$ (Enqueue) N/A $O(1)$ (Dequeue) N/A Minimal
Circular Deque $O(1)$ $O(n)$ $O(1)$ $O(1)$ $O(n)$ $O(1)$ $O(1)$ Fixed ring capacity

📖 Extended Guide

1. Memory Layout: Contiguous vs. Node-Based

Understanding CPU memory hierarchy explains why arrays outperform linked lists in real-world benchmarks despite having identical theoretical $O(n)$ search complexities:

Contiguous Array in RAM (High Cache Locality):
[ Element 0 ][ Element 1 ][ Element 2 ][ Element 3 ]  ◄── Fetched in single 64-byte Cache Line

Scattered Linked List Nodes (Pointer Chasing / Cache Misses):
[ Node A | Next* ] ───► [ Node B | Next* ] ───► [ Node C | Next* ]
 (Address 0x10A0)        (Address 0x8F40)        (Address 0x22C0)
  • Spatial Locality: Reading array[i] automatically loads subsequent elements into L1/L2 CPU cache lines (typically 64 bytes).
  • Pointer Overhead: On 64-bit systems, each node pointer consumes 8 bytes of RAM. A doubly linked list storing 4-byte integers consumes $4 + 8 + 8 = 20$ bytes per node (500% memory overhead).

2. Dynamic Array Growth & Amortized Analysis

Dynamic arrays (e.g., Go slices, Python list, Java ArrayList) allocate a fixed contiguous buffer and geometrically resize when full:

Growth Steps:
1. Buffer: [ A | B ] (Capacity: 2, Size: 2)
2. Append 'C' -> Allocate Capacity 4 -> Copy [ A | B ] -> Insert 'C': [ A | B | C | _ ]
3. Append 'D' -> Insert 'D': [ A | B | C | D ]
4. Append 'E' -> Allocate Capacity 8 -> Copy [ A | B | C | D ] -> Insert 'E': [ A | B | C | D | E | _ | _ | _ ]

Amortized Cost Proof (Aggregate Method):

  • Resizing from size $N$ requires allocating $2N$ slots and copying $N$ elements (Cost = $N$).
  • Doubling occurs at insertions $1, 2, 4, 8, 16, \dots, N$.
  • Total copy cost for $N$ insertions $= 1 + 2 + 4 + \dots + N = 2N - 1 < 2N$.
  • Amortized cost per append: $$\text{Cost} = \frac{N \text{ (regular inserts)} + 2N \text{ (copying)}}{N} = 3 = O(1)$$

3. Linked Lists: Sentinels and Doubly Linked Structures

Using dummy sentinel nodes at the head and tail completely eliminates edge-case nil/NULL pointer checks during insertion and deletion.

Doubly Linked List with Dummy Sentinels:
[ Head Sentinel ] <===> [ Node 1 (Val: 10) ] <===> [ Node 2 (Val: 20) ] <===> [ Tail Sentinel ]

Complete Go Implementation: Doubly Linked List with Sentinels

package main

import "fmt"

type Node struct {
	Value int
	Prev  *Node
	Next  *Node
}

type DoublyLinkedList struct {
	head *Node // Dummy head sentinel
	tail *Node // Dummy tail sentinel
	size int
}

func NewDoublyLinkedList() *DoublyLinkedList {
	head := &Node{}
	tail := &Node{}
	head.Next = tail
	tail.Prev = head
	return &DoublyLinkedList{head: head, tail: tail, size: 0}
}

// PushFront inserts a value at the beginning in O(1) time.
func (list *DoublyLinkedList) PushFront(val int) {
	newNode := &Node{Value: val, Prev: list.head, Next: list.head.Next}
	list.head.Next.Prev = newNode
	list.head.Next = newNode
	list.size++
}

// PushBack inserts a value at the end in O(1) time.
func (list *DoublyLinkedList) PushBack(val int) {
	newNode := &Node{Value: val, Prev: list.tail.Prev, Next: list.tail}
	list.tail.Prev.Next = newNode
	list.tail.Prev = newNode
	list.size++
}

// Remove deletes a specific node in O(1) time.
func (list *DoublyLinkedList) Remove(node *Node) {
	if node == list.head || node == list.tail {
		return
	}
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
	list.size--
}

func (list *DoublyLinkedList) Display() {
	curr := list.head.Next
	for curr != list.tail {
		fmt.Printf("%d <-> ", curr.Value)
		curr = curr.Next
	}
	fmt.Println("nil")
}

func main() {
	dll := NewDoublyLinkedList()
	dll.PushBack(10)
	dll.PushBack(20)
	dll.PushFront(5)
	dll.Display() // 5 <-> 10 <-> 20 <-> nil
}

4. Stacks, Queues, and Circular Buffers

Circular Queue (Ring Buffer)

A fixed-size array avoiding $O(n)$ shifts on dequeue by maintaining head and tail indices modulo capacity:

type CircularQueue struct {
	buffer   []int
	head     int
	tail     int
	size     int
	capacity int
}

func NewCircularQueue(k int) *CircularQueue {
	return &CircularQueue{
		buffer:   make([]int, k),
		capacity: k,
	}
}

func (q *CircularQueue) Enqueue(val int) bool {
	if q.size == q.capacity {
		return false // Queue is full
	}
	q.buffer[q.tail] = val
	q.tail = (q.tail + 1) % q.capacity
	q.size++
	return true
}

func (q *CircularQueue) Dequeue() (int, bool) {
	if q.size == 0 {
		return 0, false // Queue is empty
	}
	val := q.buffer[q.head]
	q.head = (q.head + 1) % q.capacity
	q.size--
	return val, true
}
⌂ All Guides