数据结构之链表

发表于 | 更新于: | 分类于 |
字数统计: 3,402 | 阅读时长 ≈ 14

什么是链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（”links”）。
链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。
而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。
链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。
链表有很多种不同的类型：单向链表，双向链表以及循环链表等。

点击这里查看博客对应的完整代码

单向链表


链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
一个单向链表的节点被分成两个部分。
第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。
一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。
当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个节点（需要储存反向的指针，也就是双向链表）。
相对于下面说的双向链表，这种普通的，每个节点只有一个指针的链表也叫单向链表，或者单链表，通常用在每次都只会按顺序遍历这个链表的时候。

单向链表的实现

定义单向链表数据结构

1
2
3
4
5
struct node
{
    int data;
    ss* next;
};

这是一个最简单的单向链表的数据结构，链表中的每个元素我们称之为node，node中的data为数据域，next为指针域，指向下一个元素，下面我们来声明几个链表，并给链表的数据域中放上数据。

1
2
3
4
5
6
node* s1 = new node();
s1->data = 1;
node* s2 = new node();
s2->data = 2;
node* s3 = new node();
s3->data = 3;

这里我们初始化了3个node，将node关联起来后才是一个完整的链表，那么怎么关联呢？我们继续看下面的代码。

1
2
3
4
5
6
7
8
9
10
11
s1->next = s2;
s2->next = s3;

//打印链表中的数据
cout << s1->data << endl;
cout << s1->next->data << endl;
cout << s1->next->next->data << endl;
//输出结果为
//1
//2
//3

没错，到这里我们已经实现了一个完整的链表了，是不是很简单。
下面我们先插入一个节点，并输出一下每个node的内存地址和每个node中的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//  插入节点
//  链表的插入非常简单，复杂度仅为O(1)。
//  这也就是为什么说链表插入快，因为他只需要改变插入元素前后的指针指向。
node* s4 = new node();
s4->data = 40;
s1->next = s4;
s4->next = s2;

//  打印内存地址
cout << s1 << endl;
cout << s2 << endl;
cout << s3 << endl;
//输出的内存地址(以下地址仅供参考，每个计算机输出的内存地址都不一样)
//以下内存地址毫无规律，如果有，纯属巧合~
//0xff1478
//0xff14a8
//0xff14b8

//  链表的查询复杂度为O(n)，除非查询的是首元素。
//  由于链表内存不连续，所以没有下标的概念，取值只能循环取，
//  这也就是为什么链表查询慢的原因
//  因为我们例子中的链表很短，并且为了更加直观，所以我们这里没有用循环。
cout << s1->data << endl;
cout << s1->next->data << endl;
cout << s1->next->next->data << endl;
//输出结果为
//1
//40
//2
//3

从上面的代码中很明显的体现出了链表的特点，线性、无序(这里说的无序是内存无序，和数据顺序无关)、查询慢、插入快。

双向链表


一种更复杂的链表是“双向链表”或“双面链表”。
双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。
这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。
一般是在需要大批量存储另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。
由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点，这时候就要修改指向首个节点的指针。
有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点（头节点），形成一个下面说的循环链表。
这个虚拟节点之后的节点就是真正的第一个节点。

循环链表


将一个单向链表或双向链表首尾相连，就成了循环链表。
这种方式在单向和双向链表中皆可实现，区别仅在于单向循环链表只能从一个方向循环，双向循环链表可以超两个方向循环。
循环链表可以被视为“无头无尾”，循环链表中第一个节点之前就是最后一个节点，反之亦然。
循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。
对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大(详见下面实例代码)。

双向循环链表的实现

有了上面的了解，我们下面来实现一个完整的双向循环链表。
首先我们定义头文件，头文件大家可以理解为java语言中的接口，如果我们不定义头文件也是可以的，只不过定义了头文件，我们实现了什么功能，大家在头文件中可以一目了然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#ifndef LINKED_LIST_H
#define LINKED_LIST_H

//打印
typedef void node_print_fun_t(void*);
//比较
typedef int node_compare_fun_t(const void*, const void*);

typedef void LINKED_LIST_T;

//初始化
LINKED_LIST_T *linked_list_new(int elmsize);

//销毁
int linked_list_delete(int *ptr);

//插入节点 尾插入
int linked_list_node_append(int *ptr, const void *data);

//插入节点 头插入
int linked_list_node_prepend(int *ptr, const void *data);

//遍历节点
int linked_list_travel(int *ptr, node_print_fun_t *proc);

//删除节点
void linked_list_node_delete(int *ptr, node_compare_fun_t *compare, const void *key);

//查找节点
void *linked_list_node_find(int *ptr, node_compare_fun_t *compare, const void *key);

#endif

定义链表的数据结构

1
2
3
4
5
6
7
8
9
10
11
//定义双向链表节点
struct node{
    void *data;
    node *prev,*next;
};
//定义双向链表结构体
struct linked_list{
    node head;
    //元素大小
    int elm_size;
};

看，是不是和我们之前实现的单向链表差不多呢。
然后我们实现头文件中的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
//初始化
LINKED_LIST_T *linked_list_new(int elm_size) {
    linked_list *new_list = (linked_list *)malloc(sizeof(linked_list));
    if (new_list == NULL)
        return NULL;
    new_list->head.data = NULL;
    new_list->head.next = &new_list->head;
    new_list->head.prev = &new_list->head;
    new_list->elm_size = elm_size;
    return (void *)new_list;
};

//销毁
int linked_list_delete(LINKED_LIST_T *ptr) {
    linked_list *me = (linked_list*)ptr;
    node *curr, *save;
    for (curr = me->head.next; curr != &me->head; curr = save) {
        save = curr->next;
        free(curr->data);
        free(curr);
    }
    free(me);
    return 0;
}

//插入节点 在元素末尾追加元素
int linked_list_node_append(LINKED_LIST_T *ptr, const void *data) {
    linked_list *new_list = (linked_list*)ptr;
    node *new_node;
    new_node = (node*)malloc(sizeof(node));
    if (new_node == NULL)
        return -1;
    new_node->data = malloc(new_list->elm_size);
    if (new_node->data == NULL) {
        free(new_node);
        return -1;
    }
    //复制内存
    memcpy(new_node->data, data, new_list->elm_size);
    new_list->head.prev->next = new_node;
    new_node->prev = new_list->head.prev;
    new_list->head.prev = new_node;
    new_node->next = &new_list->head;
    return 0;
}

//插入节点 在元素头追加元素
int linked_list_node_prepend(LINKED_LIST_T *ptr, const void *data) {
    linked_list *new_list = (linked_list*)ptr;
    node *new_node;
    new_node = (node*)malloc(sizeof(node));
    if (new_node == NULL)
        return -1;
    new_node->data = malloc(new_list->elm_size);
    if (new_node->data == NULL) {
        free(new_node);
        return -1;
    }
    //复制内存
    memcpy(new_node->data, data, new_list->elm_size);
    new_list->head.next->prev = new_node;
    new_node->next = new_list->head.next;
    new_list->head.next = new_node;
    new_node->prev = &new_list->head;
    return 0;
}

//遍历节点
int linked_list_travel(LINKED_LIST_T *ptr, node_print_fun_t *proc) {
    linked_list *me = (linked_list*)ptr;
    node *curr;
    for (curr = me->head.next; curr != &me->head; curr = curr->next){
        proc(curr->data); // proc(something you like)
    }
    return 0;
}

//删除节点
void linked_list_node_delete(LINKED_LIST_T *ptr,
                       node_compare_fun_t *comp,
                       const void *key) {
    linked_list *me = (linked_list*)ptr;
    node *curr;
    for (curr = me->head.next;
            curr != &me->head; curr = curr->next) {
        if ( (*comp)(curr->data, key) == 0 ) {
            node *_next, *_prev;
            _prev = curr->prev; _next = curr->next;
            _prev->next = _next; _next->prev = _prev;
            free(curr->data);
            free(curr);
            break;
        }
    }
    return;
}

//查找节点
void *linked_list_node_find(LINKED_LIST_T *ptr,
                      node_compare_fun_t *comp,
                      const void *key) {
    linked_list *me = (linked_list*)ptr;
    node *curr;
    for (curr = me->head.next;
            curr != &me->head; curr = curr->next) {
        if ( (*comp)(curr->data, key) == 0 )
            return curr->data;
    }
    return NULL;
}

//比较函数
int compare(const void *data1, const void *data2){
    if (*((int*)data1) == *((int*)data2)){
        return 0;
    }
    return -1;
}

//打印函数
void proc(void *data)
{

    cout << *((int*)data) << endl;
}

链表的存储结构

链表中的节点不需要以特定的方式存储，但是集中存储也是可以的，主要分下面这几种具体的存储方法：

共用存储空间

链表的节点和其它的数据共用存储空间，优点是可以存储无限多的内容（不过要处理器支持这个大小，并且存储空间足够的情况下），不需要提前分配内存；缺点是由于内容分散，有时候可能不方便调试。

独立存储空间

一个链表或者多个链表使用独立的存储空间，一般用数组或者类似结构实现，优点是可以自动获得一个附加数据：唯一的编号，并且方便调试；缺点是不能动态的分配内存。
当然，另外的在上面加一层块状链表用来分配内存也是可以的，这样就解决了这个问题。这种方法有时候被叫做数组模拟链表，但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针，这种下标索引其实也是逻辑上的指针，整个结构还是链表，并不算是被模拟的（但是可以说成是用数组实现的链表）。

总结

单向链表

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

双向链表

双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。

循环链表

将一个单向链表或双向链表首尾相连，就成了循环链表。
这种方式在单向和双向链表中皆可实现，区别仅在于单向循环链表只能从一个方向循环，双向循环链表可以超两个方向循环。

链表特点

线性、无序、查询慢、插入快

Choice wechat
关注公众号，获取文章更新通知。
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！