Linked List (Chain Storage)
Readers familiar with LeetCode will certainly know about singly linked lists. The definition of a singly linked list node on LeetCode is as follows:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
type ListNode struct {
Val int
Next *ListNode
}
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:
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;
}
}
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;
}
};
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,
}
}
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'sval
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 andnext
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:
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;
}
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;
}
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
}
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:
// 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);
}
// 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;
}
# 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)
}
// 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.
// 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
// 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
# 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
// 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:
// 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
// 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
# 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
// 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:
// 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
// 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
# 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
// 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.
// 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
// 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
# 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
// 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:
// 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
// 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
# 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
// 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:
// 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
// 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
# 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
// 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:
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;
}
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;
}
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
}
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:
// 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);
}
// 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;
}
# 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)
}
// 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:
// 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
// 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
# 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
// 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:
// 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
// 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
# 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
// 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):
// 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
// 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
# 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
// 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:
// 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
// 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
# 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
// 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:
// 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
// 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
# 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
// 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:
// 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
// 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
# 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
// 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.