Fork me on GitHub

链表

translation/linked_list/banner

在计算机科学领域,链表就是一组数据的线性集合,这种集合的顺序不是根据数据被存放在内存中的顺序决定的。而是根据每个元素的指向下一个的指针决定。

链表是由类队列的一组节点组合而成的数据。每个节点包括了数据和一个指向下一个节点的指针。这种结构在对数据的添加和移除是非常方便的,不管数据所在的位置。

translation/linked_list/data

缺点

  • 相比数组,链表因为使用指针来存储会更耗内存

  • 链表的节点必须是从头开始按照顺序读取,因为它本质上就是顺序访问

  • 节点不连续存储,大大增加了访问列表中元素的所需的时间端,尤其在cpu的缓存中

  • 当反向便利链表的时候会比较困难。比如,单链表向后导航比较麻烦,而双链表比较容易阅读,内存消耗在为后向指针分配空间

基本概念和术语

链表中的每条记录通常被称为元素或节点(一般叫节点)。

每个节点的字段包含下一个节点的的地址,这个字段通常被叫做下个链接或者下个指向(一般叫指针)。剩下的字段被称为数据,信息,值,负载或者载荷(一般称为值)。

列表的头是它的第一个节点,列表的尾部可以指除头节点后其余部分,或者指列表最后的一个节点。

单向链表

单链表包含数据字段和指向下个节点的尾指针字段。可以在单链表上执行的操作包括插入,删除和遍历。

translation/linked_list/data

以下的代码演示了如何将具有数据的新节点添加到单链表的末尾:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
node addNode(node head , int value){
node temp,p; // 声明两个节点temp和p
temp = createNode(); // 假设方法createNode创建一个data=0和指向空的指针节点
temp->data = value; // 添加元素的值到创建的节点data字段
if(head == NULL){
head = temp; // 当链表尾空时
}else{
p = head; // head节点赋值给p节点
while(p->next != NULL){
p = p->next; // 遍历链表到最后一个节点。最后一个节点的指向为空
}
p->next = temp;
}
return head;
}

双向链表

在双向链表中,节点中除了指向下一个节点的指针,还包含指向序列中上一个节点的指针字段。

translation/linked_list/double_linkedl_list

许多现代操作系统使用双向链接列表来维护。

权衡

和计算机编程和设计中的大多数选择一样,没有一种方法是可以适用多种情况的。链表数据结构可能在一种情况下运行良好,在另外一个情况下就有问题了。下面列表是包含链表的数据结构的权衡。

translation/linked_list/list_compare

参考

维基百科link_list

后话

自己在维基百科上查找到的介绍,然后翻译了一丢丢,链接请见上面的参考。翻译到此为止,如果看者感兴趣可以自行查看啦 @~@

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)