linked list

This page briefly introduces linked lists.

Introduction

A linked list is a data structure used to store data, connecting elements with pointers like links in a chain. Its characteristic is that inserting and deleting data are very convenient, while searching for and reading data perform poorly.

Difference from 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 different advantages:

Because of its chained structure, a linked list can conveniently delete and insert data, with $O(1)$ operations. But for the same reason, searching for and reading data are less efficient than with an array, taking $O(n)$ operations for random access.

An array makes searching for and reading data convenient, taking $O(1)$ operations for random access. But insertion and deletion take $O(n)$ operations.

Building linked lists

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.

struct Node {
  int value;
  Node *next;
};

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 its pointer field is divided into left and right (or previous and next) pointers, connecting the previous node, the current node, and the next node.

struct Node {
  int value;
  Node *left;
  Node *right;
};

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 the node pointer of next to point to the next node after p;
3. Set the p pointer of next to point to node.

The specific process is shown in the figures below:

The implementation is as follows:

void insertNode(int i, Node *p) {
  Node *node = new Node;
  node->value = i;
  node->next = p->next;
  p->next = node;
}

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 head and tail are connected, when inserting data it is necessary to check whether the original list is empty: if it is empty, make it circular by itself; otherwise, insert the data normally.

The general process is as follows:

1. Initialize the data node to be inserted;
2. Check whether the given linked list p is empty;
3. If it is empty, make both the node pointer of next and p point to node itself;
4. Otherwise, set the next pointer of p to point to the next node after p;
5. Set the next pointer of node to point to node.

The specific process is shown in the figures below:

The implementation is as follows:

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

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, in addition to checking whether the given list is empty, both the left and right pointers must be updated.

The general process is as follows:

1. Initialize the data p to be inserted;
2. Check whether the given linked list node is empty;
3. If it is empty, make the left and right pointers of p, as well as node, point to left itself;
4. Otherwise, set the p pointer of node to right;
5. Set the p pointer of p to the right node of left;
6. Set the node pointer of the right node of p to right;
7. Set the node pointer of p to p.

The implementation is as follows:

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

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

Suppose the node to be deleted is p->next. To delete it from the list, copy the value of the next node p into p, and update the node after p at the same time.

The general process is as follows:

1. Assign the value of the next node of p to p->value, erasing t;
2. Create a temporary node p->next to store the address of p;
3. Set the next pointer of p to point to the node after p->next, erasing t;
4. Delete p. Although the address of the original node p->next is still in use, the address deleted is that of the original node p; because the data of p->next has been overwritten by p, p is effectively dead.

The specific process is shown in the figures below:

The implementation is as follows:

void deleteNode(Node *p) {
  p->value = p->next->value;
  Node *t = p->next;
  p->next = p->next->next;
  delete t;
}

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 the left node of p to point to the right node of p;
2. Set the left pointer of the right node of p to point to the left node of t;
3. Create a temporary node p to store the address of p;
4. Assign the address of the right node of p to p to prevent t from becoming a dangling pointer;
5. Delete Node.

The implementation is as follows:

void deleteNode(Node *&p) {
  p->left->right = p->right;
  p->right->left = p->left;
  Node *t = p;
  p = p->right;
  delete t;
}

def deleteNode(p):
    p.left.right = p.right
    p.right.left = p.left
    p = p.right

Tricks

XOR linked list

An XOR linked list is essentially still a doubly linked list, but it uses bitwise XOR values so that the functionality of a doubly linked list can be implemented using only the memory size of one pointer.

In the lr = left ^ right structure, define lr, that is, the bitwise XOR value of the addresses of the preceding and following elements. When traversing forward, XORing the address of the preceding element with the lr of the current node gives the address of the following element; when traversing backward, XORing the address of the following element with the current node's gives the address of the preceding element. In this way, a doubly linked list with the same functionality can be implemented using half the memory.