4.2 Linked lists¶

Memory is a resource used by all programs, and in a complex system, free space may be scattered throughout it. An array requires contiguous storage, which may be unavailable for a very large array. This is where a linked list's flexibility helps.

A linked list is a linear data structure whose elements are node objects connected by references. Each reference stores the next node's memory address, allowing us to reach it from the current node.

This design lets nodes occupy scattered memory locations; their addresses need not be contiguous.

Linked list definition and storage layout

Figure 4-5 Linked list definition and storage layout

As shown above, the basic unit of a linked list is a node object. Each node holds a value and a reference to the next node.

The first node is called the head, and the last is called the tail.
The tail points to a null value: null in Java, nullptr in C++, and None in Python.
In languages supporting pointers, such as C, C++, Go, and Rust, these references are expressed as pointers.

As the code below shows, each ListNode stores a reference (pointer) in addition to its value. Thus, a linked list uses more memory than an array for the same amount of data.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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: create 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
    var 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 takes two steps: initialize the node objects, then connect them with references. Afterward, start at the head and follow next references to visit every node in order.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

linked_list.py

# Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4
# Initialize the nodes
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# Link the nodes with references
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

linked_list.cpp

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
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);
// Link the nodes with references
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

linked_list.java

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
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);
// Link the nodes with references
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.cs

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
ListNode n0 = new(1);
ListNode n1 = new(3);
ListNode n2 = new(2);
ListNode n3 = new(5);
ListNode n4 = new(4);
// Link the nodes with references
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.go

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// Link the nodes with references
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4

linked_list.swift

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
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)
// Link the nodes with references
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

linked_list.js

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
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);
// Link the nodes with references
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.ts

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
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);
// Link the nodes with references
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.dart

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */\
// Initialize the nodes
ListNode n0 = ListNode(1);
ListNode n1 = ListNode(3);
ListNode n2 = ListNode(2);
ListNode n3 = ListNode(5);
ListNode n4 = ListNode(4);
// Link the nodes with references
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.rs

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
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 }));

// Link the nodes with references
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 the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);
// Link the nodes with references
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

linked_list.kt

/* Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4 */
// Initialize the nodes
val n0 = ListNode(1)
val n1 = ListNode(3)
val n2 = ListNode(2)
val n3 = ListNode(5)
val n4 = ListNode(4)
// Link the nodes with references
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.rb

# Initialize the linked list 1 -> 3 -> 2 -> 5 -> 4
# Initialize the nodes
n0 = ListNode.new(1)
n1 = ListNode.new(3)
n2 = ListNode.new(2)
n3 = ListNode.new(5)
n4 = ListNode.new(4)
# Link the nodes with references
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

Visualize execution

View full screen >

An array is a single variable, such as nums, containing entries nums[0], nums[1], and so on. A linked list consists of separate node objects. We usually refer to the list by its head node; for example, the list above can be called n0.

2. Inserting a node¶

Inserting a node is straightforward. As shown in Figure 4-6, inserting a new node P between adjacent nodes n0 and n1 requires changing only two references (pointers), taking \(O(1)\) time.

In contrast, inserting an array element takes \(O(n)\) time and is slower for large datasets.

Inserting a node into a linked list

Figure 4-6 Inserting a node into a linked list

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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 the linked list ###
# In Ruby, `p` is a built-in method and `P` denotes a constant, so use `_p` instead
def insert(n0, _p)
  n1 = n0.next
  _p.next = n1
  n0.next = _p
end

Visualize execution

View full screen >

3. Removing a node¶

Removing a node is also straightforward: as shown in Figure 4-7, only one reference (pointer) needs to change.

Although P still points to n1 after removal, traversing the list can no longer reach P. It therefore no longer belongs to the list.

Removing a linked list node

Figure 4-7 Removing a linked list node

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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 already declares a function named remove
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

### Remove the first node after node n0 in the 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

Visualize execution

View full screen >

4. Accessing a node¶

Accessing a node in a linked list is relatively slow. An array provides access to any element in \(O(1)\) time, but a linked list must be traversed from its head until the desired node is reached. Accessing the \(i\)-th node requires \(i - 1\) iterations, giving \(O(n)\) time complexity.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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 the node at index `index` in the linked list ###
def access(head, index)
  for i in 0...index
    return nil if head.nil?
    head = head.next
  end

  head
end

Visualize execution

View full screen >

5. Finding a node¶

Traverse the list to find a node with value target, then return its index. This is also linear search. The code is as follows:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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 the first node with value target in the linked list ###
def find(head, target)
  index = 0
  while head
    return index if head.val == target
    head = head.next
    index += 1
  end

  -1
end

Visualize execution

View full screen >

4.2.2 Arrays versus linked lists¶

Table 4-1 compares their properties and operation costs. Their contrasting storage strategies give them contrasting strengths.

Table 4-1 Comparing array and linked list efficiency

	Array	Linked list
Storage	Contiguous memory	Scattered memory
Expansion	Fixed length	Flexible expansion
Memory efficiency	Less memory per element, but may waste space	More memory per element
Access an element	\(O(1)\)	\(O(n)\)
Add an element	\(O(n)\)	\(O(1)\)
Remove an element	\(O(n)\)	\(O(1)\)

4.2.3 Common types of linked lists¶

Figure 4-8 shows three common types.

Singly linked list: The ordinary linked list introduced above. Each node stores a value and a reference to the next node. The first and last nodes are the head and tail, and the tail points to None.
Circular linked list: Connecting a singly linked list's tail to its head forms a circular list. Any node can then be treated as the head.
Doubly linked list: Each node stores references (pointers) in both directions, to its successor and predecessor. This makes it more flexible and allows traversal in either direction, at the cost of additional memory.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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
        self.prev: ListNode | None = None  # Reference to the predecessor

/* Doubly linked list node structure */
struct ListNode {
    int val;         // Node value
    ListNode *next;  // Pointer to the successor
    ListNode *prev;  // Pointer to the predecessor
    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
    ListNode prev;  // Reference to the predecessor
    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
    ListNode prev;  // Reference to the predecessor
}

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

// Initialize a node with NewDoublyListNode
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
    var prev: ListNode? // Reference to the predecessor

    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
        this.prev = prev  ===  undefined ? null : prev;  // Reference to the predecessor
    }
}

/* 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
        this.prev = prev  ===  undefined ? null : prev;  // Reference to the predecessor
    }
}

/* Doubly linked list node class */
class ListNode {
    int val;        // Node value
    ListNode? next;  // Reference to the successor
    ListNode? prev;  // Reference to the predecessor
    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
    prev: Option<Rc<RefCell<ListNode>>>, // Pointer to the predecessor
}

/* 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
    struct ListNode *prev; // Pointer to the predecessor
} 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
    var next: ListNode? = null  // Reference to the successor
    var prev: ListNode? = null  // Reference to the predecessor
}

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

  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 commonly implement stacks, queues, hash tables, and graphs.

Stacks and queues: Inserting and removing at the same end gives last-in, first-out behavior, forming a stack. Inserting at one end and removing at the other gives first-in, first-out behavior, forming a queue.
Hash tables: Separate chaining is a common collision-handling strategy that places colliding elements in a linked list.
Graphs: An adjacency list associates each vertex with a linked list whose elements represent the other vertices connected to it.

Doubly linked lists are useful when both the previous and next elements must be found quickly.

Advanced data structures: In structures such as red-black trees and B-trees, a node may need access to its parent. Storing a parent reference is similar to the backward link in a doubly linked list.
Browser history: The forward and back buttons require access to the next and previous visited pages. A doubly linked list makes this straightforward.
LRU caching: Least recently used eviction needs fast access to the least recently used data and efficient insertion and removal, making doubly linked lists a good fit.

Circular linked lists suit cyclic operations, such as operating-system resource scheduling.

Round-robin scheduling: This common CPU scheduling algorithm cycles through processes, giving each a time slice before moving to the next. A circular linked list can implement this cycle.
Data buffers: Some buffers use circular linked lists. Audio and video players, for example, may divide a stream into buffer blocks arranged in a circular list for seamless playback.

4.2 Linked lists¶

4.2.1 Common linked list operations¶

1. Initializing a linked list¶

2. Inserting a node¶

3. Removing a node¶

4. Accessing a node¶

5. Finding a node¶

4.2.2 Arrays versus linked lists¶

4.2.3 Common types of linked lists¶

4.2.4 Typical applications of linked lists¶

Share your insights, questions, or suggestions in the comments