4.2 Linked Lists¶

Memory space is a common resource for all programs. In a complex system environment, free memory space can be scattered throughout memory. We know that the memory space for storing an array must be contiguous, and when the array is very large, it may not be possible 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 where each element is a node object, and the nodes are connected via "references". A reference records the memory address of the next node, allowing access to the next node from the current one.

The design of a linked list allows its nodes to be scattered throughout memory, with no need for contiguous memory addresses.

Figure 4-5 Linked List Definition and Storage Method

Observing the image above, the fundamental unit of a linked list is the "node" object. Each node contains two pieces of data: the "value" of the node and the "reference" to the next node.

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

As shown in the following code, a linked list node ListNode, apart from containing a value, also needs to store a reference (pointer). Therefore, a linked list consumes more memory space than an array for the same amount of data.

PythonC++JavaC#GoSwiftJSTSDartRustCZig

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
    }
}

/* 链表节点类 */
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
pub fn ListNode(comptime T: type) type {
    return struct {
        const Self = @This();

        val: T = 0, // Node value
        next: ?*Self = null, // Pointer to the next node

        // Constructor
        pub fn init(self: *Self, x: i32) void {
            self.val = x;
            self.next = null;
        }
    };
}

4.2.1 Common Operations on Linked Lists¶

1. Initializing a Linked List¶

Building a linked list involves two steps: initializing each node object and then establishing the references between nodes. Once initialized, we can access all nodes sequentially from the head node via the next reference.

PythonC++JavaC#GoSwiftJSTSDartRustCZig

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.zig

// Initialize linked list
// Initialize each node
var n0 = inc.ListNode(i32){.val = 1};
var n1 = inc.ListNode(i32){.val = 3};
var n2 = inc.ListNode(i32){.val = 2};
var n3 = inc.ListNode(i32){.val = 5};
var n4 = inc.ListNode(i32){.val = 4};
// Build references between nodes
n0.next = &n1;
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;

An array is a single variable, such as the array nums containing elements nums[0], nums[1], etc., while a linked list is composed of multiple independent node objects. We usually refer to the linked list by its head node, as in the linked list n0 in the above code.

2. Inserting a Node¶

Inserting a node in a linked list is very easy. As shown in the image below, suppose we want to insert a new node P between two adjacent nodes n0 and n1. This requires changing only 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 less efficient with large data volumes.

Figure 4-6 Linked List Node Insertion Example

PythonC++JavaC#GoSwiftJSTSDartRustCZig

linked_list.py

def insert(n0: ListNode, P: ListNode):
    """在链表的节点 n0 之后插入节点 P"""
    n1 = n0.next
    P.next = n1
    n0.next = P

linked_list.cpp

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

linked_list.java

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.cs

/* 在链表的节点 n0 之后插入节点 P */
void Insert(ListNode n0, ListNode P) {
    ListNode? n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.go

/* 在链表的节点 n0 之后插入节点 P */
func insertNode(n0 *ListNode, P *ListNode) {
    n1 := n0.Next
    P.Next = n1
    n0.Next = P
}

linked_list.swift

/* 在链表的节点 n0 之后插入节点 P */
func insert(n0: ListNode, P: ListNode) {
    let n1 = n0.next
    P.next = n1
    n0.next = P
}

linked_list.js

/* 在链表的节点 n0 之后插入节点 P */
function insert(n0, P) {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.ts

/* 在链表的节点 n0 之后插入节点 P */
function insert(n0: ListNode, P: ListNode): void {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.dart

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode n0, ListNode P) {
  ListNode? n1 = n0.next;
  P.next = n1;
  n0.next = P;
}

linked_list.rs

/* 在链表的节点 n0 之后插入节点 P */
#[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

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

linked_list.zig

// 在链表的节点 n0 之后插入节点 P
fn insert(n0: ?*inc.ListNode(i32), P: ?*inc.ListNode(i32)) void {
    var n1 = n0.?.next;
    P.?.next = n1;
    n0.?.next = P;
}

3. Deleting a Node¶

As shown below, deleting a node in a linked list is also very convenient, requiring only the change of one node's reference (pointer).

Note that although node P still points to n1 after the deletion operation is completed, it is no longer accessible when traversing the list, meaning P is no longer part of the list.

Figure 4-7 Linked List Node Deletion

PythonC++JavaC#GoSwiftJSTSDartRustCZig

linked_list.py

def remove(n0: ListNode):
    """删除链表的节点 n0 之后的首个节点"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1

linked_list.cpp

/* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode *n0) {
    if (n0->next == nullptr)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 释放内存
    delete P;
}

linked_list.java

/* 删除链表的节点 n0 之后的首个节点 */
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

/* 删除链表的节点 n0 之后的首个节点 */
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

/* 删除链表的节点 n0 之后的首个节点 */
func removeItem(n0 *ListNode) {
    if n0.Next == nil {
        return
    }
    // n0 -> P -> n1
    P := n0.Next
    n1 := P.Next
    n0.Next = n1
}

linked_list.swift

/* 删除链表的节点 n0 之后的首个节点 */
func remove(n0: ListNode) {
    if n0.next == nil {
        return
    }
    // n0 -> P -> n1
    let P = n0.next
    let n1 = P?.next
    n0.next = n1
    P?.next = nil
}

linked_list.js

/* 删除链表的节点 n0 之后的首个节点 */
function remove(n0) {
    if (!n0.next) return;
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

linked_list.ts

/* 删除链表的节点 n0 之后的首个节点 */
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

/* 删除链表的节点 n0 之后的首个节点 */
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

/* 删除链表的节点 n0 之后的首个节点 */
#[allow(non_snake_case)]
pub fn remove<T>(n0: &Rc<RefCell<ListNode<T>>>) {
    if n0.borrow().next.is_none() {return};
    // 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

/* 删除链表的节点 n0 之后的首个节点 */
// 注意：stdio.h 占用了 remove 关键词
void removeItem(ListNode *n0) {
    if (!n0->next)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 释放内存
    free(P);
}

linked_list.zig

// 删除链表的节点 n0 之后的首个节点
fn remove(n0: ?*inc.ListNode(i32)) void {
    if (n0.?.next == null) return;
    // n0 -> P -> n1
    var P = n0.?.next;
    var n1 = P.?.next;
    n0.?.next = n1;
}

4. Accessing Nodes¶

Accessing nodes in a linked list is less efficient. As mentioned earlier, any element in an array can be accessed in \(O(1)\) time. However, in a linked list, the program needs to start from the head node and traverse each node sequentially until it finds the target node. That is, accessing the \(i\)-th node of a linked list requires \(i - 1\) iterations, with a time complexity of \(O(n)\).

PythonC++JavaC#GoSwiftJSTSDartRustCZig

linked_list.py

def access(head: ListNode, index: int) -> ListNode | None:
    """访问链表中索引为 index 的节点"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head

linked_list.cpp

/* 访问链表中索引为 index 的节点 */
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

/* 访问链表中索引为 index 的节点 */
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

/* 访问链表中索引为 index 的节点 */
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

/* 访问链表中索引为 index 的节点 */
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

/* 访问链表中索引为 index 的节点 */
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

/* 访问链表中索引为 index 的节点 */
function access(head, index) {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

linked_list.ts

/* 访问链表中索引为 index 的节点 */
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

/* 访问链表中索引为 index 的节点 */
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

/* 访问链表中索引为 index 的节点 */
pub fn access<T>(head: Rc<RefCell<ListNode<T>>>, index: i32) -> Rc<RefCell<ListNode<T>>> {
    if index <= 0 {return head};
    if let Some(node) = &head.borrow_mut().next {
        return access(node.clone(), index - 1);
    }
    return head;
}

linked_list.c

/* 访问链表中索引为 index 的节点 */
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.zig

// 访问链表中索引为 index 的节点
fn access(node: ?*inc.ListNode(i32), index: i32) ?*inc.ListNode(i32) {
    var head = node;
    var i: i32 = 0;
    while (i < index) : (i += 1) {
        head = head.?.next;
        if (head == null) return null;
    }
    return head;
}

5. Finding Nodes¶

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

PythonC++JavaC#GoSwiftJSTSDartRustCZig

linked_list.py

def find(head: ListNode, target: int) -> int:
    """在链表中查找值为 target 的首个节点"""
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1

linked_list.cpp

/* 在链表中查找值为 target 的首个节点 */
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

/* 在链表中查找值为 target 的首个节点 */
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

/* 在链表中查找值为 target 的首个节点 */
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

/* 在链表中查找值为 target 的首个节点 */
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

/* 在链表中查找值为 target 的首个节点 */
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

/* 在链表中查找值为 target 的首个节点 */
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

/* 在链表中查找值为 target 的首个节点 */
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

/* 在链表中查找值为 target 的首个节点 */
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

/* 在链表中查找值为 target 的首个节点 */
pub fn find<T: PartialEq>(head: Rc<RefCell<ListNode<T>>>, target: T, index: i32) -> i32 {
    if head.borrow().val == target {return index};
    if let Some(node) = &head.borrow_mut().next {
        return find(node.clone(), target, index + 1);
    }
    return -1;
}

linked_list.c

/* 在链表中查找值为 target 的首个节点 */
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.zig

// 在链表中查找值为 target 的首个节点
fn find(node: ?*inc.ListNode(i32), target: i32) i32 {
    var head = node;
    var index: i32 = 0;
    while (head != null) {
        if (head.?.val == target) return index;
        head = head.?.next;
        index += 1;
    }
    return -1;
}

4.2.2 Arrays vs. Linked Lists¶

The following table summarizes the characteristics of arrays and linked lists and compares their operational efficiencies. Since they employ two opposite storage strategies, their properties and operational efficiencies also show contrasting features.

Table 4-1 Efficiency Comparison of Arrays and Linked Lists

	Arrays	Linked Lists
Storage	Contiguous Memory Space	Dispersed Memory Space
Capacity Expansion	Fixed Length	Flexible Expansion
Memory Efficiency	Less Memory per Element, Potential Space Wastage	More Memory per Element
Accessing Elements	\(O(1)\)	\(O(n)\)
Adding Elements	\(O(n)\)	\(O(1)\)
Deleting Elements	\(O(n)\)	\(O(1)\)

4.2.3 Common Types of Linked Lists¶

As shown in the following image, there are three common types of linked lists.

Singly Linked List: This is the regular linked list introduced earlier. The nodes of a singly linked list contain the value and a reference to the next node. The first node is called the head node, and the last node, pointing to null (None), is the tail node.
Circular Linked List: If the tail node of a singly linked list points back to the head node (forming a loop), it becomes a circular linked list. In a circular linked list, any node can be considered the head node.
Doubly Linked List: Compared to a singly linked list, a doubly linked list stores references in two directions. Its nodes contain references to both the next (successor) and the previous (predecessor) nodes. Doubly linked lists are more flexible as they allow traversal in both directions but require more memory space.

PythonC++JavaC#GoSwiftJSTSDartRustCZig

class ListNode:
    """Bidirectional 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 a predecessor node

/* Bidirectional 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
};

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

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

/* Bidirectional 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,
    }
}

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

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

/* Bidirectional 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
    }
}

/* Bidirectional 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
    }
}

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

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

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

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

/* Bidirectional 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;

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

// Bidirectional linked list node class
pub fn ListNode(comptime T: type) type {
    return struct {
        const Self = @This();

        val: T = 0, // Node value
        next: ?*Self = null, // Pointer to the successor node
        prev: ?*Self = null, // Pointer to the predecessor node

        // Constructor
        pub fn init(self: *Self, x: i32) void {
            self.val = x;
            self.next = null;
            self.prev = null;
        }
    };
}

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 are performed at one end of the linked list, it exhibits last-in-first-out characteristics, corresponding to a stack. When insertion is at one end and deletion is at the other, it shows first-in-first-out characteristics, corresponding to a queue.
Hash Tables: Chaining is one of the mainstream solutions to hash collisions, where all colliding elements are placed in a linked list.
Graphs: Adjacency lists are a common way to represent graphs, where each vertex is associated with a linked list. Each element in the list represents other vertices connected to that vertex.

Doubly linked lists are commonly used in scenarios that require quick access to the previous and next elements.

Advanced Data Structures: For example, in red-black trees and B-trees, we need to access a node's parent, which can be achieved by storing a reference to the parent node in each 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 previously and next visited web pages. The properties of a doubly linked list make this operation simple.
LRU Algorithm: In Least Recently Used (LRU) cache eviction algorithms, we need to quickly find the least recently used data and support rapid addition and deletion of nodes. Here, using a doubly linked list is very appropriate.

Circular linked lists are commonly used in scenarios requiring periodic operations, such as resource scheduling in operating systems.

Round-Robin Scheduling Algorithm: In operating systems, the round-robin scheduling algorithm is a common CPU scheduling algorithm that cycles through a group of processes. Each process is assigned a time slice, and when it expires, the CPU switches to the next process. This circular operation can be implemented using a circular linked list.
Data Buffers: Circular linked lists may also be used in some data buffer implementations. For instance, in audio and video players, the data stream might be divided into multiple buffer blocks placed in a circular linked list to achieve seamless playback.

4.2 Linked Lists¶

4.2.1 Common Operations on Linked Lists¶

1. Initializing a Linked List¶

2. Inserting a Node¶

3. Deleting a Node¶

4. Accessing Nodes¶

5. Finding Nodes¶

4.2.2 Arrays vs. Linked Lists¶

4.2.3 Common Types of Linked Lists¶

4.2.4 Typical Applications of Linked Lists¶

Feel free to drop your insights, questions or suggestions