List ADT: Static vs Dynamic and Linked Nodes

Part of: Java for Beginners › The List ADT: Static, Dynamic, and Linked

1. What is an ADT? The Contract vs Physical Memory

An Abstract Data Type (ADT) specifies WHAT operations are allowed (logical contract), while a data structure determines HOW bytes are physically laid out in RAM (concrete storage).

Architectural Concept

Logical Contract: interface List<T>

Golden Rule: Programar contra la interfaz

// El cliente declara la interfaz TAD
List<String> lista = new ArrayList<>();
// O cambia la implementación física sin romper nada:
List<String> lista = new LinkedList<>();

2. Contiguous Memory vs Dispersed Nodes

In an array, cells are adjacent: jumping to index 3 is an instant O(1) pointer arithmetic. In a linked list, nodes are scattered across random Heap addresses: reaching index 3 requires traversing 3 pointers in O(N).

Access Simulator

Array (Direct Access): 1 salto en O(1)

List (Pointer Walk): 3 saltos en O(N)

// Array: Aritmética de memoria directa
array[3]; // base + 3 * sizeof(elem) -> O(1)

// Lista Enlazada: Desreferenciar punteros
cabeza.siguiente.siguiente.siguiente; // O(N)

3. Node Anatomy in Memory

A node is a self-referential class in the Heap with two fields: the payload data and the reference to the next node. The chain tail points to null (ground termination).

Self-Referential Struct

Pointer Type: Nodo<T> siguiente

Termination: siguiente == null

class Nodo<T> {
  T dato;
  Nodo<T> siguiente; // Puntero al mismo tipo

  public Nodo(T dato) {
    this.dato = dato;
    this.siguiente = null;
  }
}

4. Insert at Head: O(1) Pointer Dance

Inserting at head is instant: 1. Create new node, 2. Link nuevo.siguiente = cabeza, 3. Advance cabeza = nuevo. Reversing steps 2 and 3 loses the entire existing list to garbage collection!

Step Sequence

Current Step: 1. Instantiate new Node("X")

Java Statement: Nodo nuevo = new Nodo("X");

public void agregarAlInicio(T dato) {
  Nodo<T> nuevo = new Nodo<>(dato);
  nuevo.siguiente = cabeza; // PASO 1: Enlazar primero
  cabeza = nuevo;           // PASO 2: Mover cabeza
}

5. Insert at Tail and Traversal O(N)

Adding at tail without a tail pointer mandates traversing the full chain with a cursor while actual.siguiente != null. Time complexity is O(N) proportional to element count.

Cursor Stepper

Loop condition: while (actual.siguiente != null)

Cursor Position: actual = Nodo "A"

Nodo actual = cabeza;
while (actual.siguiente != null) {
  actual = actual.siguiente; // Avanza O(N)
}
actual.siguiente = nuevo;

6. Deleting a Middle Node: Pointer Bypass

To remove a middle node, the previous node bypasses it to link directly with the successor: anterior.siguiente = actual.siguiente. With no incoming references, the bypassed node is reclaimed by the Garbage Collector.

Bridge Action

Key Statement: anterior.siguiente = actual.siguiente;

Node 20 State: Enlazado en la cadena

anterior.siguiente = actual.siguiente;
actual.siguiente = null; // Limpieza defensiva
// El recolector de basura (GC) destruye el nodo huérfano

7. Variants: Doubly-Linked and Circular Lists

A doubly-linked list adds a `prev` pointer to each node for bidirectional traversal and O(1) node deletion. A circular list loops the last node back to head.

List Mode

Pointers per Node: anterior + siguiente (2 punteros)

Key Advantage: Recorrido bidireccional

class NodoDoble<T> {
  T dato;
  NodoDoble<T> anterior;
  NodoDoble<T> siguiente;
}

8. Big-O Matrix: Array vs Linked List

Choosing the right structure depends on the access pattern. For random index lookups, Array is superior. For continuous head insertions and removals, Linked List has no rival.

Design Verdict

Heavy Reads: Usar ArrayList

Heavy Head Inserts: Usar LinkedList / Deque

// El 95% de los casos en Java se resuelven con ArrayList
// debido a la localidad espacial y caché L1/L2.