Linked Lists

Linked Lists

A linked list is a linear data structure where elements (nodes) are stored in sequence but not in contiguous memory. Each node contains data and a pointer to the next node.

Structure

graph LR
    A[Head] --> B["Data + Next"]
    B --> C["Data + Next"]
    C --> D["Data + Next"]
    D --> E["Data + Next"]
    E --> F[null]

    style A fill:#e1f5fe
    style F fill:#ffebee

Key Characteristics

Advantages:

• Dynamic size (grows/shrinks at runtime)
• O(1) insertion/deletion at head
• No memory waste (allocates only what's needed)

Disadvantages:

• O(n) random access (must traverse from head)
• Extra memory for pointers
• Poor cache locality

Operations

Operation	Complexity	Notes
Prepend	O(1)	Insert at head
Append	O(1) with tail pointer	O(n) without tail
Insert after node	O(1)	Need node reference
Delete node	O(1)	Need previous node reference
Search	O(n)	Linear traversal
Access by index	O(n)	Count from head

Built-in Implementations

Most languages provide optimized linked list implementations. Choose based on your access patterns:

JavaKotlinTypeScriptDartSwiftPython

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.addFirst("first");        // O(1)
list.addLast("last");          // O(1)
list.add(1, "middle");         // O(n)
boolean found = list.contains("item"); // O(n)

import java.util.LinkedList

val list = LinkedList<String>()
list.addFirst("first")         // O(1)
list.addLast("last")           // O(1)
list.add(1, "middle")          // O(n)
val found = list.contains("item") // O(n)

// npm install @datastructures-js/linked-list
import { LinkedList } from '@datastructures-js/linked-list';

const list = new LinkedList<string>();
list.insertFirst("first");     // O(1)
list.insertLast("last");       // O(1)
list.insertAt(1, "middle");    // O(n)
const found = list.find(node => node === "item"); // O(n)

// Deque implements a doubly-linked list
import 'package:collection/collection.dart';

final deque = DoubleLinkedQueue<String>();
deque.addFirst("first");       // O(1)
deque.addLast("last");         // O(1)
bool found = deque.contains("item"); // O(n)

// Swift does not have a built-in linked list
// Use Swift Collections: https://github.com/apple/swift-collections
// Add to Package.swift: .package(url: "https://github.com/apple/swift-collections", from: "1.0.0")

import Collections

var deque = Deque<String>()
deque.prepend("first")         // O(1)
deque.append("last")           // O(1)
deque.insert("middle", at: 1)  // O(n)
let found = deque.contains("item") // O(n)

# deque is a doubly-linked list
from collections import deque

linked_list = deque()
linked_list.appendleft("first") # O(1)
linked_list.append("last")      # O(1)
found = "item" in linked_list   # O(n)

Doubly Linked Lists

Each node has two pointers: next and previous. Enables O(1) deletion and bidirectional traversal.

Structure

graph LR
    A[Head] --> B["Prev + Data + Next"]
    B --> C["Prev + Data + Next"]
    C --> D["Prev + Data + Next"]
    D --> E["Prev + Data + Next"]
    E --> F[null]

    B -.-> A
    C -.-> B
    D -.-> C
    E -.-> D

    style A fill:#e1f5fe
    style F fill:#ffebee

Key Benefits

• O(1) deletion: Delete any node without finding previous
• Bidirectional traversal: Move forwards or backwards
• Better middle operations: Choose shorter path

Trade-offs

• Extra memory: Two pointers per node
• Complex operations: Maintain both links

Operations

Operation	Complexity	Notes
Prepend/Append	O(1)	Direct head/tail access
Delete with node ref	O(1)	No need to find previous
Search	O(n)	Still requires traversal
Access by index	O(n)	Can optimize direction

When to Choose

Use when:

• Frequent insertions/deletions at head/middle
• Queue/stack operations (O(1) at both ends)
• Unknown/variable size
• Memory fragmentation acceptable

Avoid when:

• Frequent random access by index
• Memory usage critical
• Cache performance matters
• Small, static collections

Applications

Music Playlist: A perfect real-world example where linked lists excel. You can easily add songs, skip to next/previous, and remove songs without affecting other tracks.

Music Playlist Implementation

graph LR
    A[Playlist] --> B["Song 1"]
    B --> C["Song 2"]
    C --> D["Song 3"]
    D --> E["Song 4"]
    E --> F[null]

    B -.-> A
    C -.-> B
    D -.-> C
    E -.-> D

    style A fill:#e1f5fe
    style F fill:#ffebee

Key Operations:

• Add Song: O(1) - add to end or beginning
• Skip Next/Previous: O(1) - move to next/previous node
• Remove Song: O(1) - remove current song
• Play Current: O(1) - access current song data

JavaKotlinTypeScriptDartSwiftPython

import java.util.LinkedList;

class Song {
    String title, artist;

    Song(String title, String artist) {
        this.title = title;
        this.artist = artist;
    }

    @Override
    public String toString() {
        return title + " - " + artist;
    }
}

class Playlist {
    private LinkedList<Song> songs = new LinkedList<>();
    private int currentIndex = -1;

    public void addSong(String title, String artist) {
        Song newSong = new Song(title, artist);
        songs.addLast(newSong);  // O(1) - append to end
        if (currentIndex == -1) {
            currentIndex = 0;
        }
    }

    public void next() {
        if (currentIndex < songs.size() - 1) {
            currentIndex++;
        }
    }

    public void previous() {
        if (currentIndex > 0) {
            currentIndex--;
        }
    }

    public void removeCurrent() {
        if (currentIndex >= 0 && currentIndex < songs.size()) {
            songs.remove(currentIndex);  // O(n) - requires traversal
            if (songs.isEmpty()) {
                currentIndex = -1;
            } else if (currentIndex >= songs.size()) {
                currentIndex = songs.size() - 1;
            }
        }
    }

    public String getCurrentSong() {
        if (currentIndex >= 0 && currentIndex < songs.size()) {
            return songs.get(currentIndex).toString();
        }
        return "No song";
    }
}

import java.util.LinkedList

data class Song(
    val title: String,
    val artist: String
) {
    override fun toString() = "$title - $artist"
}

class Playlist {
    private val songs = LinkedList<Song>()
    private var currentIndex = -1

    fun addSong(title: String, artist: String) {
        val newSong = Song(title, artist)
        songs.addLast(newSong)  // O(1) - append to end
        if (currentIndex == -1) {
            currentIndex = 0
        }
    }

    fun next() {
        if (currentIndex < songs.size - 1) {
            currentIndex++
        }
    }

    fun previous() {
        if (currentIndex > 0) {
            currentIndex--
        }
    }

    fun removeCurrent() {
        if (currentIndex in songs.indices) {
            songs.removeAt(currentIndex)  // O(n) - requires traversal
            when {
                songs.isEmpty() -> currentIndex = -1
                currentIndex >= songs.size -> currentIndex = songs.size - 1
            }
        }
    }

    fun getCurrentSong(): String {
        return if (currentIndex in songs.indices) {
            songs[currentIndex].toString()
        } else {
            "No song"
        }
    }
}

// npm install @datastructures-js/linked-list
import { DoublyLinkedList, DoublyLinkedListNode } from '@datastructures-js/linked-list';

class Song {
    title: string;
    artist: string;

    constructor(title: string, artist: string) {
        this.title = title;
        this.artist = artist;
    }

    toString(): string {
        return `${this.title} - ${this.artist}`;
    }
}

class Playlist {
    private songs = new DoublyLinkedList<Song>();
    private current: DoublyLinkedListNode<Song> | null = null;

    addSong(title: string, artist: string): void {
        const newSong = new Song(title, artist);
        this.songs.insertLast(newSong);
        if (!this.current) {
            this.current = this.songs.head();
        }
    }

    next(): void {
        if (this.current && this.current.getNext()) {
            this.current = this.current.getNext();
        }
    }

    previous(): void {
        if (this.current && this.current.getPrev()) {
            this.current = this.current.getPrev();
        }
    }

    removeCurrent(): void {
        if (!this.current) return;

        const nextNode = this.current.getNext() || this.current.getPrev();
        this.songs.removeNode(this.current);
        this.current = nextNode;
    }

    getCurrentSong(): string {
        return this.current?.getValue().toString() ?? "No song";
    }
}

import 'package:collection/collection.dart';

class Song {
  final String title;
  final String artist;

  Song(this.title, this.artist);

  @override
  String toString() => "$title - $artist";
}

class Playlist {
  final DoubleLinkedQueue<Song> _songs = DoubleLinkedQueue<Song>();
  int _currentIndex = -1;

  void addSong(String title, String artist) {
    final newSong = Song(title, artist);
    _songs.addLast(newSong);  // O(1) - append to end
    if (_currentIndex == -1) {
      _currentIndex = 0;
    }
  }

  void next() {
    if (_currentIndex < _songs.length - 1) {
      _currentIndex++;
    }
  }

  void previous() {
    if (_currentIndex > 0) {
      _currentIndex--;
    }
  }

  void removeCurrent() {
    if (_currentIndex >= 0 && _currentIndex < _songs.length) {
      // Convert Deque to List for indexed removal (O(n))
      final songsList = _songs.toList();
      songsList.removeAt(_currentIndex);
      _songs.clear();
      _songs.addAll(songsList);

      if (_songs.isEmpty) {
        _currentIndex = -1;
      } else if (_currentIndex >= _songs.length) {
        _currentIndex = _songs.length - 1;
      }
    }
  }

  String getCurrentSong() {
    if (_currentIndex >= 0 && _currentIndex < _songs.length) {
      return _songs.elementAt(_currentIndex).toString();
    }
    return "No song";
  }
}

import Collections

struct Song {
    let title: String
    let artist: String
}

class Playlist {
    private var songs = Deque<Song>()
    private var currentIndex = -1

    func addSong(_ title: String, _ artist: String) {
        let newSong = Song(title: title, artist: artist)
        songs.append(newSong)
        if currentIndex == -1 {
            currentIndex = 0
        }
    }

    func next() {
        if currentIndex < songs.count - 1 {
            currentIndex += 1
        }
    }

    func previous() {
        if currentIndex > 0 {
            currentIndex -= 1
        }
    }

    func removeCurrent() {
        guard currentIndex >= 0 && currentIndex < songs.count else { return }

        songs.remove(at: currentIndex)
        if songs.isEmpty {
            currentIndex = -1
        } else if currentIndex >= songs.count {
            currentIndex = songs.count - 1
        }
    }

    func getCurrentSong() -> String {
        guard currentIndex >= 0 && currentIndex < songs.count else {
            return "No song"
        }
        let song = songs[currentIndex]
        return "\(song.title) - \(song.artist)"
    }
}

from collections import deque

class Song:
    def __init__(self, title: str, artist: str):
        self.title = title
        self.artist = artist

    def __str__(self) -> str:
        return f"{self.title} - {self.artist}"

class Playlist:
    def __init__(self):
        self._songs: deque[Song] = deque()
        self._current_index = -1

    def add_song(self, title: str, artist: str) -> None:
        new_song = Song(title, artist)
        self._songs.append(new_song)  # O(1) - append to end
        if self._current_index == -1:
            self._current_index = 0

    def next(self) -> None:
        if self._current_index < len(self._songs) - 1:
            self._current_index += 1

    def previous(self) -> None:
        if self._current_index > 0:
            self._current_index -= 1

    def remove_current(self) -> None:
        if 0 <= self._current_index < len(self._songs):
            # Convert to list for indexed deletion (O(n))
            songs_list = list(self._songs)
            del songs_list[self._current_index]
            self._songs = deque(songs_list)

            if not self._songs:
                self._current_index = -1
            elif self._current_index >= len(self._songs):
                self._current_index = len(self._songs) - 1

    def get_current_song(self) -> str:
        if 0 <= self._current_index < len(self._songs):
            return str(self._songs[self._current_index])
        return "No song"