链表

何为链表

链表和数组都可用于存储数据，其中链表通过指针来连接元素，而数组则是把所有元素按次序依次存储。

不同的存储结构令他们有了不同的优势：

链表可以方便地删除、插入数据，操作次数是 O(1) 。但也因为这样寻找读取数据的效率不如数组高，在随机访问数据中的操作次数是 O(n) 。

数组可以方便的寻找读取数据，在随机访问中操作次数是 O(1) 。但删除、插入的操作次数却是却是 O(n) 次。

构建链表

关于链表的构建使用到指针的部分比较抽象，光靠文字描述和代码可能难以理解，建议配合作图来理解。

单向链表

单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用来连接当前结点和下一节点。

1
2
3
4
5
// C++ Version
struct Node {
  int value;
  Node *next;
};

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

双向链表

双向链表中同样有数据域和指针域，不同之处在于指针域有左右（或上一个、下一个）之分，用来连接上一个节点、当前结点、下一个结点。

1
2
3
4
5
6
// C++ Version
struct Node {
  int value;
  Node *left;
  Node *right;
};

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

向链表中插入（写入）数据

单向链表

1
2
3
4
5
6
7
// C++ Version
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
6
# Python Version
def insertNode(i, p):
    node = Node()
    node.value = i
    node.next = p.next
    p.next = node

具体过程可参考下面这张图。

单向循环链表

上面介绍了简单的单向链表的插入数据，有时我们会将链表的头尾连接起来将链表变为循环链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// C++ Version
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
11
# Python Version
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

由于是循环的链表，我们在插入数据时需要判断原链表是否为空，为空则自身循环，不为空则正常插入数据循环。具体过程可参考下面这张图。

双向循环链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// C++ Version
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
13
# Python Version
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

从链表中删除数据

单向（循环）链表

1
2
3
4
5
6
7
// C++ Version
void deleteNode(Node *p) {
  p->value = p->next->value;
  Node *t = p->next;
  p->next = p->next->next;
  delete t;
}

1
2
3
4
# Python Version
def deleteNode(p):
    p.value = p.next.value
    p.next = p.next.next

从链表中删除某个结点时，将 p 的下一个结点 (p->next) 的值覆盖给 p 即可，与此同时更新 p 的下下个结点。具体过程可参考下面这张图。

双向循环链表

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
5
# Python Version
def deleteNode(p):
    p.left.right = p.right
    p.right.left = p.left
    p = p.right
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论