Linked List

Lineær

En sekvens af noder 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: enkeltlænkede lister (én retning), dobbeltlænkede lister (begge retninger) og cirkulære lister (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 stakke, køer og grafer.

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

•Implementering af stakke og køer
•Fortryd/gentag-funktionalitet i applikationer
•Hukommelsesstyring (free list allocation)
•Håndtering af kollisioner i hash-tabeller (chaining)
•Musikafspillere med playlister

Fordele

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

Ulemper

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

Eksempler fra den virkelige verden

•Browserhistorik (frem/tilbage navigation)
•Billedgalleri-navigation
•Togvogne i række
•GPS-navigation med waypoints
•Blockchain-transaktioner

Relaterede strukturer

Doubly Linked ListCircular Linked ListSkip ListXOR Linked List