Skip to content

Linked List

This page provides a brief introduction to linked lists.

Introduction

A linked list is a data structure used to store data, connecting elements via pointers like a chain. Its key features are convenient insertion and deletion of data, but relatively poor performance in searching and reading data.

Comparison with Arrays

Both linked lists and arrays can be used to store data. Unlike linked lists, arrays store all elements sequentially in order. Their different storage structures give them distinct advantages:

Due to its chain-like structure, a linked list can conveniently delete and insert data with an operation count of \(O(1)\). However, because of this, searching and reading data is less efficient than in arrays, with an operation count of \(O(n)\) for random access.

Arrays can conveniently search and read data, with an operation count of \(O(1)\) for random access. However, deletion and insertion operations take \(O(n)\) steps.

Constructing a Linked List

Tip

When constructing a linked list, the pointer-related parts can be abstract. Relying solely on textual descriptions and code may make it difficult to understand. It is recommended to use diagrams alongside the explanation.

Singly Linked List

A singly linked list contains a data field and a pointer field. The data field stores data, while the pointer field connects the current node to the next node.

Implementation 
1
2
3
4
struct Node {
  int value;
  Node *next;
};

1
2
3
4
class Node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next

Doubly Linked List

A doubly linked list also has data and pointer fields. The difference is that the pointer field has left/right (or previous/next) distinctions, used to connect the previous node, the current node, and the next node.

Implementation 
1
2
3
4
5
struct Node {
  int value;
  Node *left;
  Node *right;
};

1
2
3
4
5
class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

Inserting (Writing) Data into a Linked List

Singly Linked List

The general process is as follows:

  1. Initialize the data node to be inserted;
  2. Set node's next pointer to point to the node after p;
  3. Set p's next pointer to point to node.

Refer to the following diagram for the specific process:

Code implementation:

Implementation 
1
2
3
4
5
6
void insertNode(int i, Node *p) {
  Node *node = new Node;
  node->value = i;
  node->next = p->next;
  p->next = node;
}

1
2
3
4
5
def insertNode(i, p):
    node = Node()
    node.value = i
    node.next = p.next
    p.next = node

Singly Circular Linked List

Connecting the head and tail of a linked list turns it into a circular linked list. Since the list is connected end-to-end, when inserting data, it is necessary to check whether the original list is empty: if empty, it points to itself; if not empty, insert data normally.

The general process is as follows:

  1. Initialize the data node to be inserted;
  2. Determine if the given linked list p is empty;
  3. If empty, set both node's next pointer and p to point to itself;
  4. Otherwise, set node's next pointer to point to the node after p;
  5. Set p's next pointer to point to node.

Refer to the following diagram for the specific process:

Code implementation:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void insertNode(int i, Node *p) {
  Node *node = new Node;
  node->value = i;
  node->next = NULL;
  if (p == NULL) {
    p = node;
    node->next = node;
  } else {
    node->next = p->next;
    p->next = node;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def insertNode(i, p):
    node = Node()
    node.value = i
    node.next = None
    if p == None:
        p = node
        node.next = node
    else:
        node.next = p.next
        p.next = node

Doubly Circular Linked List

When inserting data into a doubly circular linked list, besides checking if the given list is empty, both the left and right pointers need to be modified simultaneously.

The general process is as follows:

  1. Initialize the data node to be inserted;
  2. Determine if the given linked list p is empty;
  3. If empty, set node's left and right pointers, and p, to point to itself;
  4. Otherwise, set node's left pointer to point to p;
  5. Set node's right pointer to point to p's right node;
  6. Set the left pointer of p's right node to point to node;
  7. Set p's right pointer to point to node.

Code implementation:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void insertNode(int i, Node *p) {
  Node *node = new Node;
  node->value = i;
  if (p == NULL) {
    p = node;
    node->left = node;
    node->right = node;
  } else {
    node->left = p;
    node->right = p->right;
    p->right->left = node;
    p->right = node;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def insertNode(i, p):
    node = Node()
    node.value = i
    if p == None:
        p = node
        node.left = node
        node.right = node
    else:
        node.left = p
        node.right = p.right
        p.right.left = node
        p.right = node

Deleting Data from a Linked List

Singly (Circular) Linked List

Let the node to be deleted be p. To delete it from the list, overwrite p with the value of p->next, and simultaneously update p's next-next node.

The general process is as follows:

  1. Assign the value of p's next node to p, effectively erasing p->value;
  2. Create a temporary node t to store the address of p->next;
  3. Set p's next pointer to point to p's next-next node, effectively erasing p->next;
  4. Delete t. Although the address of the original node p is still in use, what is deleted is the address of the original p->next. However, p's data is overwritten by p->next, making p exist in name only.

Refer to the following diagram for the specific process:

Code implementation:

Implementation 
1
2
3
4
5
6
void deleteNode(Node *p) {
  p->value = p->next->value;
  Node *t = p->next;
  p->next = p->next->next;
  delete t;
}

1
2
3
def deleteNode(p):
    p.value = p.next.value
    p.next = p.next.next

Doubly Circular Linked List

The general process is as follows:

  1. Set the right pointer of p's left node to point to p's right node;
  2. Set the left pointer of p's right node to point to p's left node;
  3. Create a temporary node t to store the address of p;
  4. Assign the address of p's right node to p to avoid p becoming a dangling pointer;
  5. Delete t.

Code implementation:

Implementation 
1
2
3
4
5
6
7
void deleteNode(Node *&p) {
  p->left->right = p->right;
  p->right->left = p->left;
  Node *t = p;
  p = p->right;
  delete t;
}

1
2
3
4
def deleteNode(p):
    p.left.right = p.right
    p.right.left = p.left
    p = p.right

Techniques

XOR Linked List

An XOR Linked List is essentially a doubly linked list, but it utilizes the bitwise XOR value to achieve the functionality of a doubly linked list using only the memory size of a single pointer.

In the structure Node, we define lr = left ^ right, which is the bitwise XOR value of the addresses of the previous and next elements. During forward traversal, XOR-ing the address of the previous element with the current node's lr yields the address of the next element. During backward traversal, XOR-ing the address of the next element with the current node's lr yields the address of the previous element. This way, the same functionality as a doubly linked list can be achieved with half the memory.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用