Skip to content

4.2   Linked List

Memory space is a shared resource for all programs. In a complex system runtime environment, available memory space may be scattered throughout the memory. We know that the memory space for storing an array must be contiguous, and when the array is very large, the memory may not be able to provide such a large contiguous space. This is where the flexibility advantage of linked lists becomes apparent.

A linked list is a linear data structure in which each element is a node object, and the nodes are connected through "references". A reference records the memory address of the next node, through which the next node can be accessed from the current node.

The design of linked lists allows nodes to be stored scattered throughout the memory, and their memory addresses do not need to be contiguous.

Linked list definition and storage method

Figure 4-5   Linked list definition and storage method

Observing Figure 4-5, the basic unit of a linked list is a node object. Each node contains two pieces of data: the node's "value" and a "reference" to the next node.

  • The first node of a linked list is called the "head node", and the last node is called the "tail node".
  • The tail node points to "null", which is denoted as null, nullptr, and None in Java, C++, and Python, respectively.
  • In languages that support pointers, such as C, C++, Go, and Rust, the aforementioned "reference" should be replaced with "pointer".

As shown in the following code, a linked list node ListNode contains not only a value but also an additional reference (pointer). Therefore, linked lists occupy more memory space than arrays when storing the same amount of data.

class ListNode:
    """Linked list node class"""
    def __init__(self, val: int):
        self.val: int = val               # Node value
        self.next: ListNode | None = None # Reference to the next node

/* Linked list node structure */
struct ListNode {
    int val;         // Node value
    ListNode *next;  // Pointer to the next node
    ListNode(int x) : val(x), next(nullptr) {}  // Constructor
};

/* Linked list node class */
class ListNode {
    int val;        // Node value
    ListNode next;  // Reference to the next node
    ListNode(int x) { val = x; }  // Constructor
}

/* Linked list node class */
class ListNode(int x) {  // Constructor
    int val = x;         // Node value
    ListNode? next;      // Reference to the next node
}

/* Linked list node structure */
type ListNode struct {
    Val  int       // Node value
    Next *ListNode // Pointer to the next node
}

// NewListNode Constructor, creates a new linked list
func NewListNode(val int) *ListNode {
    return &ListNode{
        Val:  val,
        Next: nil,
    }
}

/* Linked list node class */
class ListNode {
    var val: Int // Node value
    var next: ListNode? // Reference to the next node

    init(x: Int) { // Constructor
        val = x
    }
}

/* Linked list node class */
class ListNode {
    constructor(val, next) {
        this.val = (val === undefined ? 0 : val);       // Node value
        this.next = (next === undefined ? null : next); // Reference to the next node
    }
}

/* Linked list node class */
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;        // Node value
        this.next = next === undefined ? null : next;  // Reference to the next node
    }
}

/* Linked list node class */
class ListNode {
  int val; // Node value
  ListNode? next; // Reference to the next node
  ListNode(this.val, [this.next]); // Constructor
}

use std::rc::Rc;
use std::cell::RefCell;
/* Linked list node class */
#[derive(Debug)]
struct ListNode {
    val: i32, // Node value
    next: Option<Rc<RefCell<ListNode>>>, // Pointer to the next node
}

/* Linked list node structure */
typedef struct ListNode {
    int val;               // Node value
    struct ListNode *next; // Pointer to the next node
} ListNode;

/* Constructor */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

/* Linked list node class */
// Constructor
class ListNode(x: Int) {
    val _val: Int = x          // Node value
    val next: ListNode? = null // Reference to the next node
}

# Linked list node class
class ListNode
  attr_accessor :val  # Node value
  attr_accessor :next # Reference to the next node

  def initialize(val=0, next_node=nil)
    @val = val
    @next = next_node
  end
end

4.2.1   Common Linked List Operations

1.   Initializing a Linked List

Building a linked list involves two steps: first, initializing each node object; second, constructing the reference relationships between nodes. Once initialization is complete, we can traverse all nodes starting from the head node of the linked list through the reference next.

linked_list.py
# Initialize linked list 1 -> 3 -> 2 -> 5 -> 4
# Initialize each node
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# Build references between nodes
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
linked_list.cpp
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// Build references between nodes
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
linked_list.java
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// Build references between nodes
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.cs
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
ListNode n0 = new(1);
ListNode n1 = new(3);
ListNode n2 = new(2);
ListNode n3 = new(5);
ListNode n4 = new(4);
// Build references between nodes
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.go
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// Build references between nodes
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4
linked_list.swift
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
let n0 = ListNode(x: 1)
let n1 = ListNode(x: 3)
let n2 = ListNode(x: 2)
let n3 = ListNode(x: 5)
let n4 = ListNode(x: 4)
// Build references between nodes
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
linked_list.js
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Build references between nodes
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.ts
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Build references between nodes
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.dart
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */\
// Initialize each node
ListNode n0 = ListNode(1);
ListNode n1 = ListNode(3);
ListNode n2 = ListNode(2);
ListNode n3 = ListNode(5);
ListNode n4 = ListNode(4);
// Build references between nodes
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.rs
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
let n0 = Rc::new(RefCell::new(ListNode { val: 1, next: None }));
let n1 = Rc::new(RefCell::new(ListNode { val: 3, next: None }));
let n2 = Rc::new(RefCell::new(ListNode { val: 2, next: None }));
let n3 = Rc::new(RefCell::new(ListNode { val: 5, next: None }));
let n4 = Rc::new(RefCell::new(ListNode { val: 4, next: None }));

// Build references between nodes
n0.borrow_mut().next = Some(n1.clone());
n1.borrow_mut().next = Some(n2.clone());
n2.borrow_mut().next = Some(n3.clone());
n3.borrow_mut().next = Some(n4.clone());
linked_list.c
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);
// Build references between nodes
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
linked_list.kt
/* Initialize linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize each node
val n0 = ListNode(1)
val n1 = ListNode(3)
val n2 = ListNode(2)
val n3 = ListNode(5)
val n4 = ListNode(4)
// Build references between nodes
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.rb
# Initialize linked list 1 -> 3 -> 2 -> 5 -> 4
# Initialize each node
n0 = ListNode.new(1)
n1 = ListNode.new(3)
n2 = ListNode.new(2)
n3 = ListNode.new(5)
n4 = ListNode.new(4)
# Build references between nodes
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
Code Visualization

An array is a single variable; for example, an array nums contains elements nums[0], nums[1], etc. A linked list, however, is composed of multiple independent node objects. We typically use the head node as the reference to the linked list; for example, the linked list in the above code can be referred to as linked list n0.

2.   Inserting a Node

Inserting a node in a linked list is very easy. As shown in Figure 4-6, suppose we want to insert a new node P between two adjacent nodes n0 and n1. We only need to change two node references (pointers), with a time complexity of \(O(1)\).

In contrast, the time complexity of inserting an element in an array is \(O(n)\), which is inefficient when dealing with large amounts of data.

Example of inserting a node into a linked list

Figure 4-6   Example of inserting a node into a linked list

linked_list.py
def insert(n0: ListNode, P: ListNode):
    """Insert node P after node n0 in the linked list"""
    n1 = n0.next
    P.next = n1
    n0.next = P
linked_list.cpp
/* Insert node P after node n0 in the linked list */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}
linked_list.java
/* Insert node P after node n0 in the linked list */
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next;
    P.next = n1;
    n0.next = P;
}
linked_list.cs
/* Insert node P after node n0 in the linked list */
void Insert(ListNode n0, ListNode P) {
    ListNode? n1 = n0.next;
    P.next = n1;
    n0.next = P;
}
linked_list.go
/* Insert node P after node n0 in the linked list */
func insertNode(n0 *ListNode, P *ListNode) {
    n1 := n0.Next
    P.Next = n1
    n0.Next = P
}
linked_list.swift
/* Insert node P after node n0 in the linked list */
func insert(n0: ListNode, P: ListNode) {
    let n1 = n0.next
    P.next = n1
    n0.next = P
}
linked_list.js
/* Insert node P after node n0 in the linked list */
function insert(n0, P) {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}
linked_list.ts
/* Insert node P after node n0 in the linked list */
function insert(n0: ListNode, P: ListNode): void {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}
linked_list.dart
/* Insert node P after node n0 in the linked list */
void insert(ListNode n0, ListNode P) {
  ListNode? n1 = n0.next;
  P.next = n1;
  n0.next = P;
}
linked_list.rs
/* Insert node P after node n0 in the linked list */
#[allow(non_snake_case)]
pub fn insert<T>(n0: &Rc<RefCell<ListNode<T>>>, P: Rc<RefCell<ListNode<T>>>) {
    let n1 = n0.borrow_mut().next.take();
    P.borrow_mut().next = n1;
    n0.borrow_mut().next = Some(P);
}
linked_list.c
/* Insert node P after node n0 in the linked list */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}
linked_list.kt
/* Insert node P after node n0 in the linked list */
fun insert(n0: ListNode?, p: ListNode?) {
    val n1 = n0?.next
    p?.next = n1
    n0?.next = p
}
linked_list.rb
### Insert node _p after node n0 in linked list ###
# Ruby's `p` is a built-in function, `P` is a constant, so use `_p` instead
def insert(n0, _p)
  n1 = n0.next
  _p.next = n1
  n0.next = _p
end

3.   Removing a Node

As shown in Figure 4-7, removing a node in a linked list is also very convenient. We only need to change one node's reference (pointer).

Note that although node P still points to n1 after the deletion operation is complete, the linked list can no longer access P when traversing, which means P no longer belongs to this linked list.

Removing a node from a linked list

Figure 4-7   Removing a node from a linked list

linked_list.py
def remove(n0: ListNode):
    """Remove the first node after node n0 in the linked list"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1
linked_list.cpp
/* Remove the first node after node n0 in the linked list */
void remove(ListNode *n0) {
    if (n0->next == nullptr)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // Free memory
    delete P;
}
linked_list.java
/* Remove the first node after node n0 in the linked list */
void remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;
}
linked_list.cs
/* Remove the first node after node n0 in the linked list */
void Remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode? n1 = P.next;
    n0.next = n1;
}
linked_list.go
/* Remove the first node after node n0 in the linked list */
func removeItem(n0 *ListNode) {
    if n0.Next == nil {
        return
    }
    // n0 -> P -> n1
    P := n0.Next
    n1 := P.Next
    n0.Next = n1
}
linked_list.swift
/* Remove the first node after node n0 in the linked list */
func remove(n0: ListNode) {
    if n0.next == nil {
        return
    }
    // n0 -> P -> n1
    let P = n0.next
    let n1 = P?.next
    n0.next = n1
}
linked_list.js
/* Remove the first node after node n0 in the linked list */
function remove(n0) {
    if (!n0.next) return;
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}
linked_list.ts
/* Remove the first node after node n0 in the linked list */
function remove(n0: ListNode): void {
    if (!n0.next) {
        return;
    }
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}
linked_list.dart
/* Remove the first node after node n0 in the linked list */
void remove(ListNode n0) {
  if (n0.next == null) return;
  // n0 -> P -> n1
  ListNode P = n0.next!;
  ListNode? n1 = P.next;
  n0.next = n1;
}
linked_list.rs
/* Remove the first node after node n0 in the linked list */
#[allow(non_snake_case)]
pub fn remove<T>(n0: &Rc<RefCell<ListNode<T>>>) {
    // n0 -> P -> n1
    let P = n0.borrow_mut().next.take();
    if let Some(node) = P {
        let n1 = node.borrow_mut().next.take();
        n0.borrow_mut().next = n1;
    }
}
linked_list.c
/* Remove the first node after node n0 in the linked list */
// Note: stdio.h occupies the remove keyword
void removeItem(ListNode *n0) {
    if (!n0->next)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // Free memory
    free(P);
}
linked_list.kt
/* Remove the first node after node n0 in the linked list */
fun remove(n0: ListNode?) {
    if (n0?.next == null)
        return
    // n0 -> P -> n1
    val p = n0.next
    val n1 = p?.next
    n0.next = n1
}
linked_list.rb
### Delete first node after node n0 in linked list ###
def remove(n0)
  return if n0.next.nil?

  # n0 -> remove_node -> n1
  remove_node = n0.next
  n1 = remove_node.next
  n0.next = n1
end

4.   Accessing a Node

Accessing nodes in a linked list is less efficient. As mentioned in the previous section, we can access any element in an array in \(O(1)\) time. This is not the case with linked lists. The program needs to start from the head node and traverse backward one by one until the target node is found. That is, accessing the \(i\)-th node in a linked list requires \(i - 1\) iterations, with a time complexity of \(O(n)\).

linked_list.py
def access(head: ListNode, index: int) -> ListNode | None:
    """Access the node at index index in the linked list"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head
linked_list.cpp
/* Access the node at index index in the linked list */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == nullptr)
            return nullptr;
        head = head->next;
    }
    return head;
}
linked_list.java
/* Access the node at index index in the linked list */
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}
linked_list.cs
/* Access the node at index index in the linked list */
ListNode? Access(ListNode? head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}
linked_list.go
/* Access the node at index index in the linked list */
func access(head *ListNode, index int) *ListNode {
    for i := 0; i < index; i++ {
        if head == nil {
            return nil
        }
        head = head.Next
    }
    return head
}
linked_list.swift
/* Access the node at index index in the linked list */
func access(head: ListNode, index: Int) -> ListNode? {
    var head: ListNode? = head
    for _ in 0 ..< index {
        if head == nil {
            return nil
        }
        head = head?.next
    }
    return head
}
linked_list.js
/* Access the node at index index in the linked list */
function access(head, index) {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}
linked_list.ts
/* Access the node at index index in the linked list */
function access(head: ListNode | null, index: number): ListNode | null {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}
linked_list.dart
/* Access the node at index index in the linked list */
ListNode? access(ListNode? head, int index) {
  for (var i = 0; i < index; i++) {
    if (head == null) return null;
    head = head.next;
  }
  return head;
}
linked_list.rs
/* Access the node at index index in the linked list */
pub fn access<T>(head: Rc<RefCell<ListNode<T>>>, index: i32) -> Option<Rc<RefCell<ListNode<T>>>> {
    fn dfs<T>(
        head: Option<&Rc<RefCell<ListNode<T>>>>,
        index: i32,
    ) -> Option<Rc<RefCell<ListNode<T>>>> {
        if index <= 0 {
            return head.cloned();
        }

        if let Some(node) = head {
            dfs(node.borrow().next.as_ref(), index - 1)
        } else {
            None
        }
    }

    dfs(Some(head).as_ref(), index)
}
linked_list.c
/* Access the node at index index in the linked list */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == NULL)
            return NULL;
        head = head->next;
    }
    return head;
}
linked_list.kt
/* Access the node at index index in the linked list */
fun access(head: ListNode?, index: Int): ListNode? {
    var h = head
    for (i in 0..<index) {
        if (h == null)
            return null
        h = h.next
    }
    return h
}
linked_list.rb
### Access node at index in linked list ###
def access(head, index)
  for i in 0...index
    return nil if head.nil?
    head = head.next
  end

  head
end

5.   Finding a Node

Traverse the linked list to find a node with value target, and output the index of that node in the linked list. This process is also a linear search. The code is shown below:

linked_list.py
def find(head: ListNode, target: int) -> int:
    """Find the first node with value target in the linked list"""
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1
linked_list.cpp
/* Find the first node with value target in the linked list */
int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}
linked_list.java
/* Find the first node with value target in the linked list */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}
linked_list.cs
/* Find the first node with value target in the linked list */
int Find(ListNode? head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}
linked_list.go
/* Find the first node with value target in the linked list */
func findNode(head *ListNode, target int) int {
    index := 0
    for head != nil {
        if head.Val == target {
            return index
        }
        head = head.Next
        index++
    }
    return -1
}
linked_list.swift
/* Find the first node with value target in the linked list */
func find(head: ListNode, target: Int) -> Int {
    var head: ListNode? = head
    var index = 0
    while head != nil {
        if head?.val == target {
            return index
        }
        head = head?.next
        index += 1
    }
    return -1
}
linked_list.js
/* Find the first node with value target in the linked list */
function find(head, target) {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}
linked_list.ts
/* Find the first node with value target in the linked list */
function find(head: ListNode | null, target: number): number {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}
linked_list.dart
/* Find the first node with value target in the linked list */
int find(ListNode? head, int target) {
  int index = 0;
  while (head != null) {
    if (head.val == target) {
      return index;
    }
    head = head.next;
    index++;
  }
  return -1;
}
linked_list.rs
/* Find the first node with value target in the linked list */
pub fn find<T: PartialEq>(head: Rc<RefCell<ListNode<T>>>, target: T) -> i32 {
    fn find<T: PartialEq>(head: Option<&Rc<RefCell<ListNode<T>>>>, target: T, idx: i32) -> i32 {
        if let Some(node) = head {
            if node.borrow().val == target {
                return idx;
            }
            return find(node.borrow().next.as_ref(), target, idx + 1);
        } else {
            -1
        }
    }

    find(Some(head).as_ref(), target, 0)
}
linked_list.c
/* Find the first node with value target in the linked list */
int find(ListNode *head, int target) {
    int index = 0;
    while (head) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}
linked_list.kt
/* Find the first node with value target in the linked list */
fun find(head: ListNode?, target: Int): Int {
    var index = 0
    var h = head
    while (h != null) {
        if (h._val == target)
            return index
        h = h.next
        index++
    }
    return -1
}
linked_list.rb
### Find first node with value target in linked list ###
def find(head, target)
  index = 0
  while head
    return index if head.val == target
    head = head.next
    index += 1
  end

  -1
end

4.2.2   Arrays vs. Linked Lists

Table 4-1 summarizes the characteristics of arrays and linked lists and compares their operational efficiencies. Since they employ two opposite storage strategies, their various properties and operational efficiencies also exhibit contrasting characteristics.

Table 4-1   Comparison of array and linked list efficiencies

Array Linked List
Storage method Contiguous memory space Scattered memory space
Capacity expansion Immutable length Flexible expansion
Memory efficiency Elements occupy less memory, but space may be wasted Elements occupy more memory
Accessing an element \(O(1)\) \(O(n)\)
Adding an element \(O(n)\) \(O(1)\)
Removing an element \(O(n)\) \(O(1)\)

4.2.3   Common Types of Linked Lists

As shown in Figure 4-8, there are three common types of linked lists:

  • Singly linked list: This is the ordinary linked list introduced earlier. The nodes of a singly linked list contain a value and a reference to the next node. We call the first node the head node and the last node the tail node, which points to null None.
  • Circular linked list: If we make the tail node of a singly linked list point to the head node (connecting the tail to the head), we get a circular linked list. In a circular linked list, any node can be viewed as the head node.
  • Doubly linked list: Compared to a singly linked list, a doubly linked list records references in both directions. The node definition of a doubly linked list includes references to both the successor node (next node) and the predecessor node (previous node). Compared to a singly linked list, a doubly linked list is more flexible and can traverse the linked list in both directions, but it also requires more memory space.
class ListNode:
    """Doubly linked list node class"""
    def __init__(self, val: int):
        self.val: int = val                # Node value
        self.next: ListNode | None = None  # Reference to the successor node
        self.prev: ListNode | None = None  # Reference to the predecessor node

/* Doubly linked list node structure */
struct ListNode {
    int val;         // Node value
    ListNode *next;  // Pointer to the successor node
    ListNode *prev;  // Pointer to the predecessor node
    ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // Constructor
};

/* Doubly linked list node class */
class ListNode {
    int val;        // Node value
    ListNode next;  // Reference to the successor node
    ListNode prev;  // Reference to the predecessor node
    ListNode(int x) { val = x; }  // Constructor
}

/* Doubly linked list node class */
class ListNode(int x) {  // Constructor
    int val = x;    // Node value
    ListNode next;  // Reference to the successor node
    ListNode prev;  // Reference to the predecessor node
}

/* Doubly linked list node structure */
type DoublyListNode struct {
    Val  int             // Node value
    Next *DoublyListNode // Pointer to the successor node
    Prev *DoublyListNode // Pointer to the predecessor node
}

// NewDoublyListNode Initialization
func NewDoublyListNode(val int) *DoublyListNode {
    return &DoublyListNode{
        Val:  val,
        Next: nil,
        Prev: nil,
    }
}

/* Doubly linked list node class */
class ListNode {
    var val: Int // Node value
    var next: ListNode? // Reference to the successor node
    var prev: ListNode? // Reference to the predecessor node

    init(x: Int) { // Constructor
        val = x
    }
}

/* Doubly linked list node class */
class ListNode {
    constructor(val, next, prev) {
        this.val = val  ===  undefined ? 0 : val;        // Node value
        this.next = next  ===  undefined ? null : next;  // Reference to the successor node
        this.prev = prev  ===  undefined ? null : prev;  // Reference to the predecessor node
    }
}

/* Doubly linked list node class */
class ListNode {
    val: number;
    next: ListNode | null;
    prev: ListNode | null;
    constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {
        this.val = val  ===  undefined ? 0 : val;        // Node value
        this.next = next  ===  undefined ? null : next;  // Reference to the successor node
        this.prev = prev  ===  undefined ? null : prev;  // Reference to the predecessor node
    }
}

/* Doubly linked list node class */
class ListNode {
    int val;        // Node value
    ListNode? next;  // Reference to the successor node
    ListNode? prev;  // Reference to the predecessor node
    ListNode(this.val, [this.next, this.prev]);  // Constructor
}

use std::rc::Rc;
use std::cell::RefCell;

/* Doubly linked list node type */
#[derive(Debug)]
struct ListNode {
    val: i32, // Node value
    next: Option<Rc<RefCell<ListNode>>>, // Pointer to the successor node
    prev: Option<Rc<RefCell<ListNode>>>, // Pointer to the predecessor node
}

/* Constructor */
impl ListNode {
    fn new(val: i32) -> Self {
        ListNode {
            val,
            next: None,
            prev: None,
        }
    }
}

/* Doubly linked list node structure */
typedef struct ListNode {
    int val;               // Node value
    struct ListNode *next; // Pointer to the successor node
    struct ListNode *prev; // Pointer to the predecessor node
} ListNode;

/* Constructor */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

/* Doubly linked list node class */
// Constructor
class ListNode(x: Int) {
    val _val: Int = x           // Node value
    val next: ListNode? = null  // Reference to the successor node
    val prev: ListNode? = null  // Reference to the predecessor node
}

# Doubly linked list node class
class ListNode
  attr_accessor :val    # Node value
  attr_accessor :next   # Reference to the successor node
  attr_accessor :prev   # Reference to the predecessor node

  def initialize(val=0, next_node=nil, prev_node=nil)
    @val = val
    @next = next_node
    @prev = prev_node
  end
end

Common types of linked lists

Figure 4-8   Common types of linked lists

4.2.4   Typical Applications of Linked Lists

Singly linked lists are commonly used to implement stacks, queues, hash tables, and graphs.

  • Stacks and queues: When insertion and deletion operations both occur at one end of the linked list, it exhibits last-in-first-out characteristics, corresponding to a stack. When insertion operations occur at one end of the linked list and deletion operations occur at the other end, it exhibits first-in-first-out characteristics, corresponding to a queue.
  • Hash tables: Separate chaining is one of the mainstream solutions for resolving hash collisions. In this approach, all colliding elements are placed in a linked list.
  • Graphs: An adjacency list is a common way to represent a graph, where each vertex in the graph is associated with a linked list, and each element in the linked list represents another vertex connected to that vertex.

Doubly linked lists are commonly used in scenarios where quick access to the previous and next elements is needed.

  • Advanced data structures: For example, in red-black trees and B-trees, we need to access the parent node of a node, which can be achieved by saving a reference to the parent node in the node, similar to a doubly linked list.
  • Browser history: In web browsers, when a user clicks the forward or backward button, the browser needs to know the previous and next web pages the user visited. The characteristics of doubly linked lists make this operation simple.
  • LRU algorithm: In cache eviction (LRU) algorithms, we need to quickly find the least recently used data and support quick addition and deletion of nodes. Using a doubly linked list is very suitable for this.

Circular linked lists are commonly used in scenarios that require periodic operations, such as operating system resource scheduling.

  • Round-robin scheduling algorithm: In operating systems, round-robin scheduling is a common CPU scheduling algorithm that needs to cycle through a set of processes. Each process is assigned a time slice, and when the time slice expires, the CPU switches to the next process. This cyclic operation can be implemented using a circular linked list.
  • Data buffers: In some data buffer implementations, circular linked lists may also be used. For example, in audio and video players, the data stream may be divided into multiple buffer blocks and placed in a circular linked list to achieve seamless playback.
Feel free to drop your insights, questions or suggestions