Linked List

A linked list is a linear data structure where elements are not stored in contiguous memory locations, but are linked together through pointers. Each element (called a node) contains data and a pointer to the next node.

Basic Concepts

Node Structure

┌─────────────┐    ┌─────────────┐    ┌─────────────┐
│ data | next │───▶│ data | next │───▶│ data | null │
└─────────────┘    └─────────────┘    └─────────────┘
     Node 1             Node 2             Node 3

Each node contains:

• Data field (data): Stores the actual data
• Pointer field (next): Points to the next node

Linked List vs Array

Linked List Types

Singly Linked List

• Singly Linked List Details
• Each node has only one pointer to the next node
• Can only traverse from head to tail in one direction

Doubly Linked List

• Doubly Linked List Details
• Each node has two pointers: prev and next
• Can traverse in both directions

Circular Linked List

• The last node points to the first node
• Forms a circular structure

Basic Operations

Create Node

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

Traverse Linked List

function traverse(head) {
  let current = head;
  while (current !== null) {
    console.log(current.data);
    current = current.next;
  }
}

Search Element

function search(head, target) {
  let current = head;
  let index = 0;

  while (current !== null) {
    if (current.data === target) {
      return index;
    }
    current = current.next;
    index++;
  }

  return -1; // Not found
}

Time Complexity Analysis

Advantages and Disadvantages

Advantages

1. Dynamic Size: Can dynamically grow and shrink at runtime
2. Efficient Insert/Delete: Insert/delete at known position is O(1)
3. Memory Efficiency: Only allocate memory when needed
4. Flexibility: Can implement complex data structures

Disadvantages

1. Extra Memory Overhead: Each node needs to store pointers
2. No Random Access: Cannot directly access the i-th element
3. Poor Cache Performance: Nodes are not contiguous in memory
4. Pointer Management: Prone to memory leaks or dangling pointers

Application Scenarios

Suitable Cases

• Frequent Insert/Delete: Especially in the middle of the list
• Unknown Size: Data volume changes greatly at runtime
• Implement Other Structures: Such as stacks, queues, adjacency lists for graphs
• Undo Operations: Editor's undo functionality

Unsuitable Cases

• Need Random Access: Frequently access elements by index
• Memory Sensitive: Strict memory usage requirements
• Cache Sensitive: Need high-performance sequential access

Practical Application Examples

1. Music Playlist

class Song {
  constructor(title, artist) {
    this.title = title;
    this.artist = artist;
    this.next = null;
  }
}

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

  addSong(title, artist) {
    const newSong = new Song(title, artist);
    if (!this.head) {
      this.head = newSong;
      this.current = newSong;
    } else {
      let last = this.head;
      while (last.next) {
        last = last.next;
      }
      last.next = newSong;
    }
  }

  nextSong() {
    if (this.current && this.current.next) {
      this.current = this.current.next;
      return this.current;
    }
    return null;
  }
}

2. Browser History

class HistoryEntry {
  constructor(url, title) {
    this.url = url;
    this.title = title;
    this.next = null;
  }
}

class BrowserHistory {
  constructor() {
    this.head = null;
    this.maxSize = 100;
    this.size = 0;
  }

  visit(url, title) {
    const entry = new HistoryEntry(url, title);
    entry.next = this.head;
    this.head = entry;
    this.size++;

    // Limit history size
    if (this.size > this.maxSize) {
      this.removeLast();
    }
  }

  getHistory() {
    const history = [];
    let current = this.head;
    while (current) {
      history.push({
        url: current.url,
        title: current.title,
      });
      current = current.next;
    }
    return history;
  }
}

Learning Suggestions

1. Start from Basics: First master the basic operations of singly linked lists
2. Visualize with Diagrams: Use diagrams to understand pointer changes
3. Watch Edge Cases: Special handling for empty lists, single nodes, head/tail nodes
4. Practice Pointer Operations: Master pointer CRUD operations
5. Comparative Learning: Compare with arrays to understand each other's use cases

Next Steps

We recommend learning in the following order:

1. Singly Linked List - Master basic concepts and operations
2. Doubly Linked List - Understand the advantages of bidirectional pointers
3. Circular Linked List - Learn about special linked list variants
4. Advanced Linked List Applications - Such as LRU cache, skip lists, etc.

Mastering linked lists is essential for understanding more complex data structures (like trees and graphs)!