Linked List (Chain Storage)

labuladongOriginalAbout 7551 words

Readers who have practiced on LeetCode are certainly very familiar with singly linked lists. The definition of a singly linked list node on LeetCode is as follows:

java 🟢

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

cpp 🤖

class ListNode {
    public:
        int val;
        ListNode *next; 
        ListNode(int x) : val(x), next(NULL) {}
};

python 🤖

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

go 🤖

type ListNode struct {
    Val  int
    Next *ListNode
}

javascript 🤖

function ListNode(val) {
    var val;
    var next;
    this.val = val;
    this.next = null;
}

This is just a simple singly linked list node, which is often used in algorithm problems on platforms like LeetCode. In actual programming languages, the linked list nodes we use can be a bit more complex, like this:

java 🟢

class Node<E> {
    E val;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.val = element;
        this.next = next;
        this.prev = prev;
    }
}

cpp 🤖

private:
    template <typename E>
    class Node {
    public:
        E val;
        Node* next;
        Node* prev;

        Node(Node* prev, E element, Node* next) {
            this->val = element;
            this->next = next;
            this->prev = prev;
        }
    };

python 🤖

class Node:
    def __init__(self, prev, element, next):
        self.val = element
        self.next = next
        self.prev = prev

go 🤖

type Node[T any] struct {
    val  T
    next *Node[T]
    prev *Node[T]
}

func NewNode[T any](prev *Node[T], element T, next *Node[T]) *Node[T] {
    return &Node[T]{
        val:  element,
        next: next,
        prev: prev,
    }
}

javascript 🤖

var Node = function(prev, element, next) {
    this.val = element;
    this.next = next;
    this.prev = prev;
};

There are two main differences:

Standard libraries in programming languages generally provide generics, meaning you can specify the val field to be of any type, whereas the val field in LeetCode's singly linked list nodes is only of type int.
Standard libraries typically use doubly linked lists rather than singly linked lists. A singly linked list node only has one next pointer pointing to the next node, while a doubly linked list node has two pointers: prev pointing to the previous node and next pointing to the next node.

With the prev pointer, the linked list supports bidirectional traversal. However, maintaining an additional pointer makes operations like insertion, deletion, and modification slightly more complex. We will introduce the implementation of doubly linked lists in detail later.

Why Do We Need Linked Lists

Previously, we introduced the underlying principles of arrays (sequential storage). To put it simply, an array is a block of continuous memory space. By knowing the starting address of this space, we can directly calculate the address of any element using its index.

Linked lists are different. A linked list does not need a contiguous block of memory to store its elements. The elements of a linked list can be scattered throughout memory. Using next and prev pointers in each node, these scattered memory blocks are linked together to form a chain-like structure.

The benefits of this approach are clear. Firstly, it improves memory utilization efficiency. The nodes of a linked list do not need to be adjacent. You can allocate memory for a node whenever you need it, and the operating system will find it easy to manage.

Another advantage is that nodes can be connected when needed and removed when not needed. You never have to worry about resizing or moving data. Theoretically, a linked list has no capacity limit (unless you fill up all available memory, which is unlikely).

Of course, there are limitations as well. The biggest advantage of arrays is the ability to quickly access elements via indices, which linked lists do not support.

This is easy to understand. Since elements are not adjacent, if you want to access the 3rd element in a linked list, you have to start at the head node and follow the next pointers until you reach the 3rd node.

This is a basic introduction to the linked list data structure. Next, we will implement some basic operations for singly and doubly linked lists with code examples.

Basic Operations of Singly Linked Lists

I will first write a utility function to create a singly linked list, which will be useful for the following explanations:

java 🟢

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// input an array, convert it to a singly linked list
ListNode createLinkedList(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    ListNode head = new ListNode(arr[0]);
    ListNode cur = head;
    for (int i = 1; i < arr.length; i++) {
        cur.next = new ListNode(arr[i]);
        cur = cur.next;
    }
    return head;
}

cpp 🤖

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// input an array, convert it into a singly linked list
ListNode* createLinkedList(std::vector<int> arr) {
    if (arr.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;
    for (int i = 1; i < arr.size(); i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return head;
}

python 🤖

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# input an array and convert it to a singly linked list
def createLinkedList(arr: 'List[int]') -> 'ListNode':
    if arr is None or len(arr) == 0:
        return None

    head = ListNode(arr[0])
    cur = head
    for i in range(1, len(arr)):
        cur.next = ListNode(arr[i])
        cur = cur.next

    return head

go 🤖

type ListNode struct {
    Val int
    Next *ListNode
}

// input an array and convert it to a singly linked list
func createLinkedList(arr []int) *ListNode {
    if arr == nil || len(arr) == 0 {
        return nil
    }
    head := &ListNode{Val: arr[0]}
    cur := head
    for i := 1; i < len(arr); i++ {
        cur.Next = &ListNode{Val: arr[i]}
        cur = cur.Next
    }
    return head
}

javascript 🤖

var ListNode = function(x) {
    this.val = x;
    this.next = null;
};

// input an array and convert it to a singly linked list
var createLinkedList = function(arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    var head = new ListNode(arr[0]);
    var cur = head;
    for (var i = 1; i < arr.length; i++) {
        cur.next = new ListNode(arr[i]);
        cur = cur.next;
    }
    return head;
}

Search/Modify

Traversing/Searching/Modifying a Singly Linked List

For example, if I want to access each node of a singly linked list and print its value, I can write it like this:

java 🟢

// create a single linked list
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// traverse the single linked list
for (ListNode p = head; p != null; p = p.next) {
    System.out.println(p.val);
}

cpp 🤖

// create a singly linked list
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// traverse the singly linked list
for (ListNode* p = head; p != nullptr; p = p->next) {
    std::cout << p->val << std::endl;
}

python 🤖

# create a singly linked list
head = createLinkedList([1, 2, 3, 4, 5])

# traverse the singly linked list
p = head
while p is not None:
    print(p.val)
    p = p.next

go 🤖

// create a singly linked list
head := createLinkedList([]int{1, 2, 3, 4, 5})

// traverse the singly linked list
for p := head; p != nil; p = p.Next {
    fmt.Println(p.Val)
}

javascript 🤖

// create a singly linked list
let head = createLinkedList([1, 2, 3, 4, 5]);

// traverse the singly linked list
for (let p = head; p != null; p = p.next) {
    console.log(p.val);
}

Similarly, if you need to access or modify a node in a linked list using an index, you can only use a for loop starting from the head node and search sequentially until you find the node corresponding to the index, then proceed with the access or modification.

Insertion

Inserting a New Element at the Head of a Singly Linked List

Let's look at the code directly, it's very simple:

java 🟢

// create a singly linked list
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// insert a new node 0 at the head of the singly linked list
ListNode newHead = new ListNode(0);
newHead.next = head;
head = newHead;
// now the linked list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

cpp 🤖

// create a singly linked list
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// insert a new node 0 at the head of the singly linked list
ListNode* newHead = new ListNode(0);
newHead->next = head;
head = newHead;
// now the linked list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

python 🤖

# create a singly linked list
head = createLinkedList([1, 2, 3, 4, 5])

# insert a new node with value 0 at the head of the list
newHead = ListNode(0)
newHead.next = head
head = newHead
# now the linked list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

go 🤖

// create a singly linked list
head := createLinkedList([]int{1, 2, 3, 4, 5})

// insert a new node 0 at the head of the singly linked list
newHead := &ListNode{Val: 0}
newHead.Next = head
head = newHead
// now the linked list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

javascript 🤖

// create a singly linked list
var head = createLinkedList([1, 2, 3, 4, 5]);

// insert a new node 0 at the head of the singly linked list
var newHead = new ListNode(0);
newHead.next = head;
head = newHead;
// now the linked list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

Inserting a New Element at the End of a Singly Linked List

This operation is slightly more complex because we need to start at the head node and traverse to the last node of the list before we can insert a new node after the last node:

java 🟢

// create a singly linked list
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// insert a new node with value 6 at the end of the linked list
ListNode p = head;
// first, go to the last node of the linked list
while (p.next != null) {
    p = p.next;
}
// now p is the last node of the linked list
// insert a new node after p
p.next = new ListNode(6);

// now the linked list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

cpp 🤖

// create a single linked list
ListNode* head = createLinkedList(std::vector<int>{1, 2, 3, 4, 5});

// insert a new node 6 at the end of the single linked list
ListNode* p = head;
// first move to the last node of the linked list
while (p->next != nullptr) {
    p = p->next;
}
// now p is the last node of the linked list
// insert a new node after p
p->next = new ListNode(6);

// now the linked list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

python 🤖

# create a singly linked list
head = createLinkedList([1, 2, 3, 4, 5])

# insert a new node 6 at the end of the singly linked list
p = head
# first, go to the last node of the linked list
while p.next is not None:
    p = p.next
# now p is the last node of the linked list
# insert a new node after p
p.next = ListNode(6)

# now the linked list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

go 🤖

// create a singly linked list
head := createLinkedList([]int{1, 2, 3, 4, 5})

// insert a new node with value 6 at the end of the singly linked list
p := head
// first, move to the last node of the linked list
for p.Next != nil {
    p = p.Next
}
// now p is the last node of the linked list
// insert a new node after p
p.Next = &ListNode{Val: 6}

// now the linked list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

javascript 🤖

// create a singly linked list
var head = createLinkedList([1, 2, 3, 4, 5]);

// insert a new node with value 6 at the end of the singly linked list
var p = head;
// first, go to the last node of the linked list
while (p.next !== null) {
    p = p.next;
}
// now p is the last node of the linked list
// insert a new node after p
p.next = new ListNode(6);

// now the linked list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

Certainly, if we have a reference to the last node of the linked list, inserting a new node at the end becomes very simple, as there's no need to traverse from the head each time. This optimization will be discussed in detail when implementing a doubly linked list later.

Inserting a New Element in the Middle of a Singly Linked List

This operation is slightly more complex. We first need to locate the predecessor node of the insertion position, then use this predecessor to insert the new node:

java 🟢

// create a singly linked list
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// insert a new node 66 after the 3rd node
// first, find the predecessor node, i.e., the 3rd node
ListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next;
}
// now p points to the 3rd node
// set the next pointer of the new node
ListNode newNode = new ListNode(66);
newNode.next = p.next;

// insert the new node
p.next = newNode;

// now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

cpp 🤖

// create a singly linked list
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// insert a new node 66 after the 3rd node
// first, find the predecessor node, which is the 3rd node
ListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}
// now p points to the 3rd node
// assemble the successor pointer of the new node
ListNode* newNode = new ListNode(66);
newNode->next = p->next;

// insert the new node
p->next = newNode;

// now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

python 🤖

# create a singly linked list
head = createLinkedList([1, 2, 3, 4, 5])

# insert a new node 66 after the 3rd node
# first find the predecessor node, which is the 3rd node
p = head
for _ in range(2):
    p = p.next
# at this point, p points to the 3rd node
# assemble the successor pointer of the new node
new_node = ListNode(66)
new_node.next = p.next

# insert the new node
p.next = new_node

# now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

go 🤖

// create a singly linked list
head := createLinkedList([]int{1, 2, 3, 4, 5})

// insert a new node with value 66 after the 3rd node
// first, find the predecessor node, which is the 3rd node
p := head
for i := 0; i < 2; i++ {
    p = p.next
}
// at this point, p points to the 3rd node
// assemble the next pointer of the new node
newNode := &ListNode{Val: 66}
newNode.next = p.next

// insert the new node
p.next = newNode

// now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

javascript 🤖

// create a singly linked list
var head = createLinkedList([1, 2, 3, 4, 5]);

// insert a new node 66 after the 3rd node
// first, find the predecessor node, which is the 3rd node
var p = head;
for (var i = 0; i < 2; i++) {
    p = p.next;
}
// at this point, p points to the 3rd node
// set up the new node's next pointer
var newNode = new ListNode(66);
newNode.next = p.next;

// insert the new node
p.next = newNode;

// now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

Deletion

Deleting a Node in a Singly Linked List

To delete a node, first locate the predecessor of the node to be deleted. Then, set the next pointer of this predecessor node to point to the node following the one to be deleted. This effectively removes the node from the list.

java 🟢

// create a singly linked list
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// to delete the 4th node, we need to operate on the predecessor node
ListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next;
}

// at this point, p points to the 3rd node, which is the predecessor of the node to be deleted
// remove the 4th node from the linked list
p.next = p.next.next;

// now the linked list becomes 1 -> 2 -> 3 -> 5

cpp 🤖

// create a single linked list
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// delete the 4th node, need to operate on the previous node
ListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}

// at this point p points to the 3rd node, which is the previous node of the node to be deleted
// remove the 4th node from the linked list
p->next = p->next->next;

// now the linked list becomes 1 -> 2 -> 3 -> 5

python 🤖

# create a singly linked list
head = createLinkedList([1, 2, 3, 4, 5])

# to delete the 4th node, we need to operate on the predecessor node
p = head
for i in range(2):
    p = p.next

# at this point, p points to the 3rd node, which is the predecessor of the node to be deleted
# remove the 4th node from the linked list
p.next = p.next.next

# now the linked list becomes 1 -> 2 -> 3 -> 5

go 🤖

// create a singly linked list
head := createLinkedList([]int{1, 2, 3, 4, 5})

// to delete the 4th node, operate on the predecessor node
p := head
for i := 0; i < 2; i++ {
    p = p.next
}

// at this point, p points to the 3rd node, which is the predecessor of the node to be deleted
// remove the 4th node from the linked list
p.next = p.next.next

// now the linked list becomes 1 -> 2 -> 3 -> 5

javascript 🤖

// create a singly linked list
var head = createLinkedList([1, 2, 3, 4, 5]);

// to delete the 4th node, we need to operate on the predecessor node
var p = head;
for (var i = 0; i < 2; i++) {
    p = p.next;
}

// at this point, p points to the 3rd node, which is the predecessor of the node to be deleted
// remove the 4th node from the linked list
p.next = p.next.next;

// now the linked list becomes 1 -> 2 -> 3 -> 5

Deleting an Element at the End of a Singly Linked List

This operation is relatively simple. Locate the second-to-last node and set its next pointer to null:

java 🟢

// create a singly linked list
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// delete the tail node
ListNode p = head;
// find the second to last node
while (p.next.next != null) {
    p = p.next;
}

// now p points to the second to last node
// remove the tail node from the linked list
p.next = null;

// now the linked list becomes 1 -> 2 -> 3 -> 4

cpp 🤖

// create a singly linked list
ListNode* head = createLinkedList({1, 2, 3, 4, 5});

// delete the tail node
ListNode* p = head;
// find the second to last node
while (p->next->next != nullptr) {
    p = p->next;
}

// at this point, p points to the second to last node
// remove the tail node from the linked list
p->next = nullptr;

// now the linked list becomes 1 -> 2 -> 3 -> 4

python 🤖

# create a singly linked list
head = createLinkedList([1, 2, 3, 4, 5])

# delete the tail node
p = head
# find the second to last node
while p.next.next is not None:
    p = p.next

# now p points to the second to last node
# detach the tail node from the linked list
p.next = None

# now the linked list becomes 1 -> 2 -> 3 -> 4

go 🤖

// create a singly linked list
head := createLinkedList([]int{1, 2, 3, 4, 5})

// delete the tail node
p := head
// find the second last node
for p.next.next != nil {
    p = p.next
}

// at this point, p points to the second last node
// remove the tail node from the linked list
p.next = nil

// now the linked list becomes 1 -> 2 -> 3 -> 4

javascript 🤖

// create a singly linked list
var head = createLinkedList([1, 2, 3, 4, 5]);

// delete the tail node
var p = head;
// find the second to last node
while (p.next.next !== null) {
    p = p.next;
}

// at this point p points to the second to last node
// remove the tail node from the list
p.next = null;

// now the linked list becomes 1 -> 2 -> 3 -> 4

Deleting an Element from the Head of a Singly Linked List

This operation is quite simple; just move the head to the next node. Let's look at the code directly:

java 🟢

// create a singly linked list
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// delete the head node
head = head.next;

// now the linked list becomes 2 -> 3 -> 4 -> 5

cpp 🤖

// create a singly linked list
ListNode* head = createLinkedList(vector<int>{1, 2, 3, 4, 5});

// delete the head node
head = head->next;

// now the linked list becomes 2 -> 3 -> 4 -> 5

python 🤖

# create a singly linked list
head = createLinkedList([1, 2, 3, 4, 5])

# delete the head node
head = head.next

# now the linked list becomes 2 -> 3 -> 4 -> 5

go 🤖

// create a singly linked list
head := createLinkedList([]int{1, 2, 3, 4, 5})

// delete the head node
head = head.Next

// now the linked list becomes 2 -> 3 -> 4 -> 5

javascript 🤖

// create a singly linked list
var head = createLinkedList([1, 2, 3, 4, 5]);

// delete the head node
head = head.next;

// now the linked list becomes 2 -> 3 -> 4 -> 5

Some readers might wonder if the old head node 1 still points to node 2 with its next pointer, will this cause a memory leak?

No, it won't. It's fine for node 1 to point to other nodes. As long as there are no other references pointing to node 1, it can be garbage collected.

Of course, if you explicitly set the next pointer of node 1 to null, that's a good habit. It can help avoid potential pointer issues in other scenarios.

In the visualization panel below, I've explicitly set the next pointer of the node to be deleted to null:

Does it seem complicated?

Operations on a linked list, such as adding, deleting, searching, and updating, are indeed more complex than those on an array. This is because the nodes in a linked list are not contiguous. To add or delete a node, you must first find its predecessor and successor nodes, and then coordinate them to insert or delete the node using pointer operations.

The code provided above is just the simplest example. You will find that the code for adding or deleting elements at the head, tail, or middle of the list is different. To implement a truly functional linked list, you also need to consider many edge cases, such as the list being empty or the predecessor or successor nodes being null. All of these cases must be handled correctly.

Moreover, the above explanation is only for a "singly linked list." In the next chapter, we will implement a "doubly linked list," which requires maintaining both predecessor and successor pointers, making the pointer operations more complex.

Does it already feel overwhelming? Don't worry, it's not as difficult as you think, for a few reasons:

There are actually just a few operations. Once we start implementing the linked list API, you'll get the hang of it by writing some code yourself.
For complex operations, I've prepared visual panels. You can understand the code and animations together.
Most importantly, we will use the "dummy head node" technique to unify the operations for the head, tail, and middle of the list. This also helps avoid edge cases where the head or tail pointers are null.

I've discussed the dummy node technique in Summary of Linked List Double Pointer Techniques. We will also cover it when implementing the doubly linked list later, but for now, I'll just briefly mention it here.

Basic Operations of a Doubly Linked List

Let me start with a utility function to create a doubly linked list, which will help with the following explanations:

java 🟢

class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) { val = x; }
}

DoublyListNode createDoublyLinkedList(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    DoublyListNode head = new DoublyListNode(arr[0]);
    DoublyListNode cur = head;
    // use a for loop to iteratively create the doubly linked list
    for (int i = 1; i < arr.length; i++) {
        DoublyListNode newNode = new DoublyListNode(arr[i]);
        cur.next = newNode;
        newNode.prev = cur;
        cur = cur.next;
    }
    return head;
}

cpp 🤖

class DoublyListNode {
public:
    int val;
    DoublyListNode *next, *prev;
    DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
};

DoublyListNode* createDoublyLinkedList(vector<int>& arr) {
    if (arr.empty()) {
        return NULL;
    }
    DoublyListNode* head = new DoublyListNode(arr[0]);
    DoublyListNode* cur = head;
    // use for loop to iteratively create the doubly linked list
    for (int i = 1; i < arr.size(); i++) {
        DoublyListNode* newNode = new DoublyListNode(arr[i]);
        cur->next = newNode;
        newNode->prev = cur;
        cur = cur->next;
    }
    return head;
}

python 🤖

class DoublyListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        self.prev = None
        
def createDoublyLinkedList(arr: List[int]) -> Optional[DoublyListNode]:
    if not arr:
        return None
    
    head = DoublyListNode(arr[0])
    cur = head
    
    # use for loop to iteratively create the doubly linked list
    for val in arr[1:]:
        new_node = DoublyListNode(val)
        cur.next = new_node
        new_node.prev = cur
        cur = cur.next
    
    return head

go 🤖

type DoublyListNode struct {
    Val        int
    Prev, Next *DoublyListNode
}

func NewDoublyListNode(x int) *DoublyListNode {
    return &DoublyListNode{Val: x}
}

func CreateDoublyLinkedList(arr []int) *DoublyListNode {
    if arr == nil || len(arr) == 0 {
        return nil
    }
    head := NewDoublyListNode(arr[0])
    cur := head
    // use for loop to iteratively create the doubly linked list
    for i := 1; i < len(arr); i++ {
        newNode := NewDoublyListNode(arr[i])
        cur.Next = newNode
        newNode.Prev = cur
        cur = cur.Next
    }
    return head
}

javascript 🤖

function DoublyListNode(x) {
  this.val = x;
  this.next = this.prev = null;
}

var createDoublyLinkedList = function(arr) {
  if (arr === null || arr.length === 0) {
    return null;
  }

  var head = new DoublyListNode(arr[0]);
  var cur = head;

  // use a for loop to iteratively create the doubly linked list
  for (var i = 1; i < arr.length; i++) {
    var newNode = new DoublyListNode(arr[i]);
    cur.next = newNode;
    newNode.prev = cur;
    cur = cur.next;
  }

  return head;
}

Search/Modify

Traversing/Searching/Modifying a Doubly Linked List

For traversing and searching in a doubly linked list, we can start from either the head node or the tail node and move forward or backward as needed:

java 🟢

// create a doubly linked list
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});
DoublyListNode tail = null;

// traverse the doubly linked list from the head node to the end
for (DoublyListNode p = head; p != null; p = p.next) {
    System.out.println(p.val);
    tail = p;
}

// traverse the doubly linked list from the tail node to the front
for (DoublyListNode p = tail; p != null; p = p.prev) {
    System.out.println(p.val);
}

cpp 🤖

// create a doubly linked list
DoublyListNode* head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});
DoublyListNode* tail = nullptr;

// traverse the doubly linked list from the head node to the end
for (DoublyListNode* p = head; p != nullptr; p = p->next) {
    cout << p->val << endl;
    tail = p;
}

// traverse the doubly linked list from the tail node to the head
for (DoublyListNode* p = tail; p != nullptr; p = p->prev) {
    cout << p->val << endl;
}

python 🤖

# create a doubly linked list
head = createDoublyLinkedList([1, 2, 3, 4, 5])
tail = None

# traverse the doubly linked list from the head node to the end
p = head
while p:
    print(p.val)
    tail = p
    p = p.next

# traverse the doubly linked list from the tail node to the start
p = tail
while p:
    print(p.val)
    p = p.prev

go 🤖

// create a doubly linked list
head := createDoublyLinkedList([]int{1, 2, 3, 4, 5})
var tail *DoublyListNode

// traverse the doubly linked list from head to tail
for p := head; p != nil; p = p.Next {
    fmt.Println(p.Val)
    tail = p
}

// traverse the doubly linked list from tail to head
for p := tail; p != nil; p = p.Prev {
    fmt.Println(p.Val)
}

javascript 🤖

// create a doubly linked list
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);
var tail = null;

// traverse the doubly linked list from the head node
for (var p = head; p !== null; p = p.next) {
    console.log(p.val);
    tail = p;
}

// traverse the doubly linked list from the tail node
for (var p = tail; p !== null; p = p.prev) {
    console.log(p.val);
}

When accessing or modifying a node, you can choose the appropriate direction to traverse based on whether the index is closer to the head or the tail. This can improve efficiency to some extent.

Insertion

Inserting a New Element at the Head of a Doubly Linked List

To insert an element at the head of a doubly linked list, you need to adjust the pointers of the new node and the original head node:

java 🟢

// create a doubly linked list
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// insert a new node 0 at the head of the doubly linked list
DoublyListNode newHead = new DoublyListNode(0);
newHead.next = head;
head.prev = newHead;
head = newHead;
// now the list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

cpp 🤖

// create a doubly linked list
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// insert a new node 0 at the head of the doubly linked list
DoublyListNode* newHead = new DoublyListNode(0);
newHead->next = head;
head->prev = newHead;
head = newHead;

// now the list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

python 🤖

# create a doubly linked list
head = create_doubly_linked_list([1, 2, 3, 4, 5])

# insert a new node 0 at the head of the doubly linked list
new_head = DoublyListNode(0)
new_head.next = head
head.prev = new_head
head = new_head
# now the linked list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

go 🤖

// create a doubly linked list
head := createDoublyLinkedList([]int{1, 2, 3, 4, 5})

// insert a new node 0 at the head of the doubly linked list
newHead := &DoublyListNode{val: 0}
newHead.next = head
head.prev = newHead
head = newHead
// now the linked list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

javascript 🤖

// create a doubly linked list
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// insert a new node 0 at the head of the doubly linked list
var newHead = new DoublyListNode(0);
newHead.next = head;
head.prev = newHead;
head = newHead;
// now the list becomes 0 -> 1 -> 2 -> 3 -> 4 -> 5

Inserting a New Element at the Tail of a Doubly Linked List

When inserting an element at the tail of a doubly linked list, if we have a reference to the tail node, this operation becomes very straightforward:

java 🟢

// create a doubly linked list
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

DoublyListNode tail = head;
// first, go to the last node of the linked list
while (tail.next != null) {
    tail = tail.next;
}

// insert a new node with value 6 at the end of the doubly linked list
DoublyListNode newNode = new DoublyListNode(6);
tail.next = newNode;
newNode.prev = tail;
// update the tail node reference
tail = newNode;

// now the linked list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

cpp 🤖

// create a doubly linked list
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

DoublyListNode* tail = head;
// first go to the last node of the list
while (tail->next != nullptr) {
    tail = tail->next;
}

// insert a new node 6 at the end of the doubly linked list
DoublyListNode* newNode = new DoublyListNode(6);
tail->next = newNode;
newNode->prev = tail;
// update the tail node reference
tail = newNode;

// now the list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

python 🤖

# create a doubly linked list
head = createDoublyLinkedList([1, 2, 3, 4, 5])

tail = head
# first, move to the last node of the list
while tail.next is not None:
    tail = tail.next

# insert a new node 6 at the tail of the doubly linked list
newNode = DoublyListNode(6)
tail.next = newNode
newNode.prev = tail
# update the tail node reference
tail = newNode

# now the list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

go 🤖

// create a doubly linked list
head := createDoublyLinkedList([]int{1, 2, 3, 4, 5})

tail := head
// first go to the last node of the list
for tail.next != nil {
    tail = tail.next
}

// insert a new node with value 6 at the end of the doubly linked list
newNode := &DoublyListNode{value: 6}
tail.next = newNode
newNode.prev = tail
// update the tail node reference
tail = newNode

// now the list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

javascript 🤖

// create a doubly linked list
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

var tail = head;
// first, move to the last node of the list
while (tail.next !== null) {
    tail = tail.next;
}

// insert a new node 6 at the end of the doubly linked list
var newNode = new DoublyListNode(6);
tail.next = newNode;
newNode.prev = tail;
// update the tail node reference
tail = newNode;

// now the list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6

Inserting a New Element in the Middle of a Doubly Linked List

Inserting a new element at a specified position in a doubly linked list requires adjusting the pointers of the predecessor and successor nodes:

java 🟢

// create a doubly linked list
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// insert a new node 66 after the 3rd node
// find the 3rd node
DoublyListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next;
}

// assemble the new node
DoublyListNode newNode = new DoublyListNode(66);
newNode.next = p.next;
newNode.prev = p;

// insert the new node
p.next.prev = newNode;
p.next = newNode;

// now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

cpp 🤖

// create a doubly linked list
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// insert a new node 66 after the 3rd node
// find the 3rd node
DoublyListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}

// assemble the new node
DoublyListNode* newNode = new DoublyListNode(66);
newNode->next = p->next;
newNode->prev = p;

// insert the new node
p->next->prev = newNode;
p->next = newNode;

// now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

python 🤖

# create a doubly linked list
head = createDoublyLinkedList([1, 2, 3, 4, 5])

# insert a new node 66 after the 3rd node
# find the 3rd node
p = head
for _ in range(2):
    p = p.next

# assemble the new node
newNode = DoublyListNode(66)
newNode.next = p.next
newNode.prev = p

# insert the new node
p.next.prev = newNode
p.next = newNode

# now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

go 🤖

// create a doubly linked list
head := createDoublyLinkedList([]int{1, 2, 3, 4, 5})

// insert a new node 66 after the 3rd node
// find the 3rd node
p := head
for i := 0; i < 2; i++ {
    p = p.next
}

// assemble the new node
newNode := &DoublyListNode{val: 66}
newNode.next = p.next
newNode.prev = p

// insert the new node
p.next.prev = newNode
p.next = newNode

// now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

javascript 🤖

// create a doubly linked list
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// insert a new node 66 after the 3rd node
// find the 3rd node
var p = head;
for (var i = 0; i < 2; i++) {
    p = p.next;
}

// assemble the new node
var newNode = new DoublyListNode(66);
newNode.next = p.next;
newNode.prev = p;

// insert the new node
p.next.prev = newNode;
p.next = newNode;

// now the linked list becomes 1 -> 2 -> 3 -> 66 -> 4 -> 5

Deletion

Deleting a Node in a Doubly Linked List

When deleting a node in a doubly linked list, it is necessary to adjust the pointers of the predecessor and successor nodes to remove the target node:

java 🟢

// create a doubly linked list
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// delete the 4th node
// first find the 3rd node
DoublyListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next;
}

// now p points to the 3rd node, we remove the node after it
DoublyListNode toDelete = p.next;

// remove toDelete from the list
p.next = toDelete.next;
toDelete.next.prev = p;

// setting toDelete's previous and next pointers to null is a good habit (optional)
toDelete.next = null;
toDelete.prev = null;

// now the list becomes 1 -> 2 -> 3 -> 5

cpp 🤖

// create a doubly linked list
DoublyListNode* head = createDoublyLinkedList(std::vector<int>{1, 2, 3, 4, 5});

// delete the 4th node
// first find the 3rd node
DoublyListNode* p = head;
for (int i = 0; i < 2; ++i) {
    p = p->next;
}

// now p points to the 3rd node, we will remove the node after it
DoublyListNode* toDelete = p->next;

// remove toDelete from the linked list
p->next = toDelete->next;
toDelete->next->prev = p;

// it is good practice to set toDelete's next and prev pointers to null (optional)
toDelete->next = nullptr;
toDelete->prev = nullptr;

// now the linked list becomes 1 -> 2 -> 3 -> 5

python 🤖

# create a doubly linked list
head = createDoublyLinkedList([1, 2, 3, 4, 5])

# delete the 4th node
# first find the 3rd node
p = head
for i in range(2):
    p = p.next

# now p points to the 3rd node, we will remove the node following it
toDelete = p.next

# remove toDelete from the list
p.next = toDelete.next
toDelete.next.prev = p

# it is a good practice to set toDelete's next and prev pointers to null (optional)
toDelete.next = None
toDelete.prev = None

# now the list becomes 1 -> 2 -> 3 -> 5

go 🤖

// create a doubly linked list
head := createDoublyLinkedList([]int{1, 2, 3, 4, 5})

// delete the 4th node
// first find the 3rd node
p := head
for i := 0; i < 2; i++ {
    p = p.Next
}

// now p points to the 3rd node, we will remove the node after it
toDelete := p.Next

// remove toDelete from the linked list
p.Next = toDelete.Next
if toDelete.Next != nil {
    toDelete.Next.Prev = p
}

// setting toDelete's next and prev pointers to nil is a good habit (optional)
toDelete.Next = nil
toDelete.Prev = nil

// now the linked list becomes 1 -> 2 -> 3 -> 5

javascript 🤖

// create a doubly linked list
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// delete the 4th node
// first, find the 3rd node
var p = head;
for (var i = 0; i < 2; i++) {
    p = p.next;
}

// now p points to the 3rd node, we remove the node after it
var toDelete = p.next;

// remove toDelete from the linked list
p.next = toDelete.next;
toDelete.next.prev = p;

// it's a good practice to set both pointers of toDelete to null (optional)
toDelete.next = null;
toDelete.prev = null;

// now the linked list becomes 1 -> 2 -> 3 -> 5

Deleting an Element at the Head of a Doubly Linked List

To delete an element at the head of a doubly linked list, you need to adjust the pointers of the head node:

java 🟢

// create a doubly linked list
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// delete the head node
DoublyListNode toDelete = head;
head = head.next;
head.prev = null;

// clear the pointers of the deleted node
toDelete.next = null;

// now the linked list becomes 2 -> 3 -> 4 -> 5

cpp 🤖

// create a doubly linked list
DoublyListNode* head = createDoublyLinkedList({1, 2, 3, 4, 5});

// delete the head node
DoublyListNode* toDelete = head;
head = head->next;
head->prev = nullptr;

// clean up the pointers of the deleted node
toDelete->next = nullptr;

// now the linked list becomes 2 -> 3 -> 4 -> 5

python 🤖

# create a doubly linked list
head = createDoublyLinkedList([1, 2, 3, 4, 5])

# delete the head node
toDelete = head
head = head.next
head.prev = None

# clear the pointers of the deleted node
toDelete.next = None

# now the linked list becomes 2 -> 3 -> 4 -> 5

go 🤖

// create a doubly linked list
head := createDoublyLinkedList([]int{1, 2, 3, 4, 5})

// delete the head node
toDelete := head
head = head.next
head.prev = nil

// clean up the pointers of the deleted node
toDelete.next = nil

// now the linked list becomes 2 -> 3 -> 4 -> 5

javascript 🤖

// create a doubly linked list
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// delete the head node
var toDelete = head;
head = head.next;
head.prev = null;

// clean up the pointers of the deleted node
toDelete.next = null;

// now the linked list becomes 2 -> 3 -> 4 -> 5

Deleting an Element at the Tail of a Doubly Linked List

In a singly linked list, due to the lack of a predecessor pointer, deleting the tail node requires traversing to the second-to-last node and adjusting its next pointer to remove the tail node.

However, in a doubly linked list, since each node stores a pointer to its predecessor, we can directly remove the tail node by adjusting its own pointers:

java 🟢

// create a doubly linked list
DoublyListNode head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

// delete the tail node
DoublyListNode p = head;
// find the tail node
while (p.next != null) {
    p = p.next;
}

// now p points to the tail node
// remove the tail node from the list
p.prev.next = null;

// it's a good habit to disconnect all pointers of the deleted node (optional)
p.prev = null;

// now the list becomes 1 -> 2 -> 3 -> 4

cpp 🤖

// create a doubly linked list
DoublyListNode* head = createDoublyLinkedList(std::vector<int>{1, 2, 3, 4, 5});

// delete the tail node
DoublyListNode* p = head;
// find the tail node
while (p->next != nullptr) {
    p = p->next;
}

// now p points to the tail node
// remove the tail node from the linked list
p->prev->next = nullptr;

// it's a good habit to break the pointers of the deleted node (optional)
p->prev = nullptr;

// now the linked list becomes 1 -> 2 -> 3 -> 4

python 🤖

# create a doubly linked list
head = createDoublyLinkedList([1, 2, 3, 4, 5])

# delete the tail node
p = head
# find the tail node
while p.next is not None:
    p = p.next

# now p is pointing to the tail node
# remove the tail node from the linked list
p.prev.next = None

# it's a good practice to break all pointers of the deleted node (optional)
p.prev = None

# now the linked list becomes 1 -> 2 -> 3 -> 4

go 🤖

// create a doubly linked list
head := createDoublyLinkedList([]int{1, 2, 3, 4, 5})

// delete the tail node
p := head
// find the tail node
for p.next != nil {
    p = p.next
}

// now p points to the tail node
// remove the tail node from the list
p.prev.next = nil

// it is a good practice to break the pointers of the deleted node (optional)
p.prev = nil

// now the list becomes 1 -> 2 -> 3 -> 4

javascript 🤖

// create a doubly linked list
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// delete the tail node
var p = head;
// find the tail node
while (p.next !== null) {
    p = p.next;
}

// now p points to the tail node
// remove the tail node from the linked list
p.prev.next = null;

// it is a good practice to break all pointers of the deleted node (optional)
p.prev = null;

// now the linked list becomes 1 -> 2 -> 3 -> 4

In the next article, we will implement a MyLinkedList with basic operations like add, delete, search, and update using both singly and doubly linked lists. We will also employ the "dummy head node" technique to simplify the code logic and avoid edge cases where head or tail pointers are null.