Ph.D. Qual Study Assistant: Linked List

Data Structure Prompt

"Describe and prototype a fundamental data structure for storing a collection of elements. Unlike an array, this structure should not store elements in contiguous memory locations. Instead, each element should be a separate object that holds the data itself and also contains a reference to the next element in the sequence. What are the performance characteristics of inserting an element at the beginning of this structure versus accessing an element by its position?"

The Linked List

The professor's clues point directly to the Linked List. It is a linear data structure where elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.

Core Components

Node: The basic building block. Each node contains the actual data and a pointer to the next node in the list.
Head: A pointer that always points to the first node in the list.
Next: The pointer within a node that references the subsequent node. The last node's `next` pointer is typically `null`.

Comparison to Arrays

Memory: Arrays use contiguous memory blocks. Linked Lists can be scattered throughout memory.
Size: Arrays have a fixed size (or require costly resizing). Linked Lists are dynamic and can grow or shrink easily.
Insertion/Deletion: Fast in Linked Lists (O(1)) if at the head. Slow in arrays (O(n)) as elements must be shifted.
Access: Fast in arrays (O(1)) by index. Slow in Linked Lists (O(n)) as you must traverse from the head.

Visual Representation

From-Scratch Prototype (JavaScript)

Here is a simple implementation showing the `Node` and `LinkedList` classes. This demonstrates the core logic of creating nodes and linking them together.

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  // Insert at the beginning (O(1))
  prepend(data) {
    this.head = new Node(data, this.head);
  }

  // Insert at the end (O(n))
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // Print all values (O(n))
  print() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}