Linked List (Chain Storage)

labuladongOriginalAbout 7459 words

Readers familiar with LeetCode will certainly know about 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

type ListNode struct {
    Val  int
    Next *ListNode
}

javascript

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

This is just the simplest singly linked list node for algorithm problems on LeetCode. In actual programming languages, linked list nodes are slightly 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

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 usually provide generics, allowing you to specify the val field to be of any type, whereas LeetCode's singly linked list node's val field is of type int only.
Standard libraries generally use doubly linked lists instead of singly linked lists. A singly linked list node has only a 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 predecessor pointer, linked lists support bidirectional traversal. However, maintaining an additional pointer makes operations like insertion, deletion, searching, and updating slightly more complex. We will introduce the implementation of doubly linked lists in detail later.

Why Linked Lists are Needed

Previously, we discussed the underlying principles of arrays (sequential storage), which is essentially a contiguous block of memory. With the starting address of this memory block, you can directly calculate the address of any element using its index.

Linked lists are different. A linked list does not require a contiguous block of memory to store elements. The elements of the linked list can be scattered throughout memory, linked together using the next and prev pointers in each node to form a chain structure.

The advantage is clear: it improves memory utilization efficiency. Linked list nodes do not need to be adjacent, and you can create a new node whenever there is available memory. The operating system finds this approach flexible.

Another advantage is that nodes can be added or removed as needed, without concerns about resizing or data relocation. Theoretically, linked lists have no capacity limits (unless all memory is used up, which is unlikely).

Of course, there are limitations as well. The biggest advantage of arrays is the ability to quickly access elements using an index, which is not possible with linked lists.

This is easy to understand since the elements are not contiguous. If you want to access the 3rd element of a linked list, you must start from the head node and follow the next pointer until you reach the 3rd node.

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

Basic Operations of Singly Linked List

First, let's write a utility function to create a singly linked list, which will make the following explanations easier:

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

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

Access / Modify

Traversing, Accessing, and Modifying a Singly Linked List

For example, if I want to visit each node in a singly linked list and print its value, I can write:

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

// 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 want to access or modify a node at a specific index, you have to use a for loop to start from the head node and move forward until you find the node at the given index, then perform the access or modification.

Insert

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

We usually have a reference to the head node, so we only need to insert the new node before the head node and set the new node as the head.

java

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

// insert a new node with value 0 at the head of the single linked list
ListNode newNode = new ListNode(0);
newNode.next = head;
head = newNode;

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

cpp

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

// insert a new node with value 0 at the head of the single linked list
ListNode* newNode = new ListNode(0);
newNode->next = head;
head = newNode;

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

python

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

# insert a new node with value 0 at the head of the single linked list
newNode = ListNode(0)
newNode.next = head
head = newNode

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

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

// insert a new node with value 0 at the head of the single linked list
newNode := &ListNode{Val: 0}
newNode.Next = head
head = newNode

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

javascript

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

// insert a new node with value 0 at the head of the single linked list
var newNode = new ListNode(0);
newNode.next = head;
head = newNode;

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

Inserting a New Element at the Tail 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 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({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

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

Of course, if we have a reference to the tail node, inserting a new node at the tail becomes much easier and we don't need to traverse from the head every time. This optimization will be introduced later when we implement a doubly linked list.

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

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

This operation is a bit more complex. We need to find the previous node of the insertion position, and then use the previous node 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

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

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

Delete

Deleting a Node in a Singly Linked List

To delete a node, you first need to find the previous node of the one to be deleted, then set the next pointer of the previous node to the node after the one being 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

// 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 a Node in a Singly Linked List

Deleting the Tail Node in a Singly Linked List

This operation is simple. Just find 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

// 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 the Tail Node in a Singly Linked List

Deleting the Head Node in a Singly Linked List

This operation is straightforward. Just move the head pointer to the next node. Let's look at the code:

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

// 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 may wonder, since the old head node 1 still has its next pointer pointing to node 2, will this cause a memory leak?

No, it won’t. As long as there are no other references pointing to node 1, it will be garbage collected, regardless of whether it still points to other nodes.

Of course, it is a good habit to explicitly set the next pointer of node 1 to null, as this can help avoid pointer errors in some situations.

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

Deleting the Head Node in a Singly Linked List

Does This Feel Complicated?

Linked list operations such as insertion, deletion, searching, and updating are indeed more complex than arrays. This is because the nodes in a linked list are not stored contiguously, so to insert or delete a node, you must first find its previous and next nodes, then adjust the pointers accordingly.

The code above is just the simplest example. You may have noticed that the code for inserting or deleting elements at the head, tail, and middle is different. To implement a fully functional linked list, you also need to handle many edge cases, such as when the list is empty or when the previous or next nodes are null.

Moreover, the above only introduces "singly linked lists." In the next chapter, we will implement "doubly linked lists," which require managing both previous and next pointers, making pointer operations even more complex.

Does it feel overwhelming? Don’t worry. It's not as hard as it seems, for several reasons:

There are only a few core operations. Once you write the linked list API yourself, you’ll quickly get the hang of it.
For complex operations, I’ve provided visualization panels so 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, while also avoiding edge cases where head or tail pointers are null.

The dummy node technique is frequently used in Classic Linked List Algorithms. Here, we just mention it briefly; the detailed implementation will be discussed later.

Basic Operations of Doubly Linked List

First, let's write a utility function to create a doubly linked list. This will make the explanations easier:

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(const 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

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 / Update

Traversing, Searching, and Modifying a Doubly Linked List

For traversing and searching a doubly linked list, you can start from either the head or the tail, 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({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

// 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 to traverse from the head or tail based on which is closer to the target index. This can improve efficiency to some extent.

Insert

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

// 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 Head of a Doubly Linked List

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 you have a reference to the tail node, this operation becomes very simple:

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

// 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 at the Tail of a Doubly Linked List

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

To insert a new element at a specific position in a doubly linked list, you need to adjust the pointers of the predecessor and successor nodes.

For example, in the following case, insert element 66 at index 3 (the fourth node):

java

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

// if we want to insert at index 3 (4th node)
// we need to operate the node at index 2
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});

// if we want to insert at index 3 (4th node)
// we need to operate the node at index 2
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])

# if we want to insert at index 3 (4th node)
# we need to operate the node at index 2
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

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

// if we want to insert at index 3 (4th node)
// we need to operate the node at index 2
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]);

// if we want to insert at index 3 (4th node)
// we need to operate the node at index 2
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

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

Delete

Deleting a Node from a Doubly Linked List

When deleting a node from a doubly linked list, you need 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({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

// 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 a Node from a Doubly Linked List

Deleting the Head Element from a Doubly Linked List

Deleting the head element from a doubly linked list requires adjusting the head node's pointer:

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

// 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 the Head Element from a Doubly Linked List

Deleting the Tail Element from a Doubly Linked List

In a singly linked list, since there is no previous pointer, deleting the tail node requires traversing to the second-to-last node and updating its next pointer to remove the tail.

But in a doubly linked list, since each node stores a pointer to its predecessor, you can directly operate on the tail node to remove it from the list:

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({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

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

Deleting the Tail Element from a Doubly Linked List

Next Steps

In the next article, we will use both singly and doubly linked lists to implement a MyLinkedList that supports basic operations such as insert, delete, search, and update. We will also use the "dummy head node" technique to simplify code logic and avoid dealing with edge cases where head or tail pointers are null.