Linked List

Lineær

En sekvens af nodes hvor hvert element peger til det næste element i kæden via en pointer.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(n)`
Search	`O(n)`
Insertion	`O(1)`
Deletion	`O(1)`

Beskrivelse

En Linked List er en dynamisk datastruktur hvor hvert element (node) indeholder data og en reference (pointer) til næste node i sekvensen. I modsætning til arrays, behøver linked lists ikke sammenhængende hukommelse, hvilket gør dem fleksible til dynamiske operationer. Der findes flere varianter: singly linked lists (én retning), doubly linked lists (begge retninger) og circular linked lists (slutter ved starten). Linked lists er særligt effektive til at indsætte og slette elementer, da dette kun kræver opdatering af pointere. Dog er adgang til elementer langsommere end arrays, da man skal traversere listen fra start til ønsket position. De bruges ofte som fundamental byggesten til mere avancerede datastrukturer som stacks, queues og graphs.

Kode Eksempel

// JavaScript Linked List implementation
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

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

  // Tilføj i starten
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // Tilføj i slutningen
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }

  // Søg efter element
  find(data) {
    let current = this.head;
    while (current) {
      if (current.data === data) return current;
      current = current.next;
    }
    return null;
  }

  // Fjern element
  remove(data) {
    if (!this.head) return;
    if (this.head.data === data) {
      this.head = this.head.next;
      this.size--;
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next;
        this.size--;
        return;
      }
      current = current.next;
    }
  }
}

Anvendelsesområder

•Implementation af stacks og queues
•Undo/redo funktionalitet i applikationer
•Memory management (free list allocation)
•Hash table collision handling (chaining)
•Musikafspillere med playlists

Fordele

✓Dynamisk størrelse uden reallokering
✓Effektiv indsættelse og sletning O(1)
✓Ingen hukommelsesspild fra ubrugt kapacitet
✓Let at implementere stacks og queues
✓God til hyppige modificeringer

Ulemper

✗Langsom adgang til elementer O(n)
✗Ekstra hukommelse til pointere
✗Ikke cache-venlig (spredt i hukommelsen)
✗Ingen random access som arrays
✗Mere kompleks at implementere

Eksempler fra den virkelige verden

•Browser historik (frem/tilbage navigation)
•Billedgalleri navigation
•Train carriages (togvogne i række)
•GPS navigation med waypoints
•Blockchain transaktioner

Relaterede strukturer

Doubly Linked ListCircular Linked ListSkip ListXOR Linked List