The Pointer and Object Model

Overview

Data structures are built from objects (records, structs) connected by pointers. The pointer-and-object model provides an abstract cost model for analysing data structure operations, independent of hardware details like cache hierarchies or page tables.

Objects, Fields, and Pointers

An object is a block of memory with named fields (attributes). Fields contain either primitive values (integers, booleans) or pointers to other objects. A pointer is the memory address of an object; it can be stored in a field, a variable, or passed as an argument.

• NIL is a reserved pointer value meaning “points to nothing”.
• An object’s fields are accessed with dot notation: x.key, x.next.

The Cost Model

The following operations each take $\Theta(1)$ time in this model:

Operation	Description
Following a pointer	Reading a pointer field and accessing the target object
Reading/writing a field	Setting or getting a primitive field value
Allocating an object	new — obtaining a fresh block of memory
Arithmetic	Addition, subtraction, multiplication, division
Comparisons	Equality, less-than, etc.

Arrays are a special case: an array of length $n$ can be allocated in $\Theta(n)$ time, and indexing A[i] is $\Theta(1)$ (random access).

Linked Structures

Objects connected by pointers form linked structures:

• Singly linked: each node has a next pointer. Traversal is forward-only. Space: 1 pointer per node.
• Doubly linked: each node has next and prev pointers. Traversal in both directions. Space: 2 pointers per node. Deletion of a node given a pointer to it is $\Theta(1)$ (versus $\Theta(n)$ for singly linked).
• Circular: the last node points back to the first (or to a sentinel). Useful for round-robin scheduling, circular buffers.
• Sentinel nodes: a dummy node that simplifies edge cases (e.g. empty-list checks). The sentinel is never removed and its data field is irrelevant.

Trees and Graphs

Trees and graphs are built using the same pointer-and-object model:

• A binary tree node: key, left, right, and optionally parent.
• A general tree node: key, parent, and a list of children (using linked-list pointers or an array of child pointers).
• A graph: vertices with adjacency lists (linked lists or arrays of edge pointers).

Memory Allocation

Memory management is a practical concern. In pseudocode we assume an infinite supply of memory; in reality, allocators like malloc manage a heap, tracking free and busy chunks (see Doug Lea’s allocator for a real-world use of doubly linked lists). Deallocation (free) returns memory to the free pool. Garbage collection automates deallocation by tracing reachable objects from root pointers and freeing unreachable ones.

Why This Model Matters

The model abstracts away machine-level complexity whilst remaining precise enough for asymptotic analysis. All data structure running times in the course are expressed in terms of this cost model. Real-world performance may differ due to constant factors (cache misses, memory bandwidth), but the asymptotic conclusions hold.

Summary

Concept	Meaning
Object	Memory block with named fields
Pointer	Address of an object (or NIL)
Field access / pointer follow / arithmetic	$\Theta(1)$ each
Array indexing	$\Theta(1)$ random access
Singly vs. doubly linked	1 vs. 2 pointers per node; forward-only vs. bidirectional
Sentinel	Dummy node simplifying boundary conditions