LinkedList

发表于 | 分类于 | |

简介

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存在下一个的指针(Pointer)。

链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点都包含指向下一个节点的链接。

由于不需要按照顺序存储，链表在插入的时候可以达到O(1)的复杂度。所以比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别为O(logn)和O(1).

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针。链表允许插入和移除表上任意位置上的结点，但是不允许随机存取。

删除节点x后的下一节点使用的语句是：

1
x->next = x->next->next;

把节点t插入链表中节点x后的下一位置，我们使用语句：

1
t->next = x->next; x->next=t;

约瑟夫问题

假设有N个人决定选出一个领导人，方法如下：所有人排成一个圆圈，按顺序数数，每隔第M的人出局，此时，他两边的人靠拢重新形成圆圈。问题是找出哪一个人将会是最后剩下的那个人。所选出的领导人的号码是一个N和M的函数，我们称之为约瑟夫函数（Jesephus function）。更为一般地，我们希望知道所有人出局的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdlib.h>
typedef struct node* link;
struct node {int item; link next;};
main(int argc, char *argv[])
{
    int i, N = atoi(argv[1]), M = atoi(argv[2]);
    link t = malloc(sizeof *t), x=t;
    t->item = 1; t->next = t;
    for (i = 2; i <= N; i++)
    {
        x = (x->next = malloc(sizeof *x));
        x->item = i; x->next = t;
    }
    while (x != x->next)
    {
        for (i = 1; i < M; i++) x = x->next;
        x->next = x->next->next;N--;
    }
    printf("%d\n", x->item);
}

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

单向链表

Singly LinkedList

链表中最简单的一种，包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个结点，而最后一个结点则指向一个空值。

一个单向链表的节点被分为两个部分，第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

双向链表

Doubly LinkedList

一种更复杂的链表是双向链表。每个节点有两个链接：一个指向前一个节点，而另一个指向下一个节点。

循环链表

首节点和末节点被连接在一起。

块状链表

本身是一种链表，但是链表存储的并不是一般的数据，而是由这些数据组成的顺序表，每一个块状链表的节点也就是顺序表，可以被叫做一个块。

链表的应用

链表用来构建许多其他的数据结构，如堆栈，队列和它们的派生。

Array vs. Linked List

计算机科学已经研究出一种定义新类型的成功方法。这种方法使用3个步骤来完成从抽象到具体的过程：

  1. 为类型的属性和客队类型执行的操作提供一个抽象的描述。这个描述不应受任何特定实现的约束，甚至不应收到任何特定变成语言的约束。这样一种正式的抽象描述被称为抽象数据类型（ADT）。

  2. 开发一个实现该ADT的编程接口。即说明如何存储数据并描述用于执行所需操作的函数集合。

  3. 编写代码来实现这个接口。

Reference

算法：C语言实现

More than your eyes can see