数据结构算法之 链表

数据结构 阅读量

链表

链表概念

链表是一种数据结构，和数组同级。比如，java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历的效率不高，但是插入和删除时优势明显。
链表就是链式存储的线性表。根据指针域的不同，链表分为单向链表，双向链表，循环链表等等。

单向节点

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

单向链表是一种线性表，实际上是由节点(Node)组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个节点只能也只有它能知道下一个节点的存储位置。由N个节点(Node)组成单向链表，每一个节点记录本节点的数据和下一个节点。向外暴露的只有一个头节点(Head)，我们对联标的所有操作，都是直接或者间接的通过其头节点来进行的。

上图中最左边的节点即为头节点(Head)，但是添加节点的顺序是从右向左的，添加的新节点会被作为新节点。最先添加的节点对下一节点的引用可以为空。引用是引用下一节点而非下一个节点的对象。因为有着不断地引用，所以头节点就可以操作所有的节点了。
下图描述了单向链表存储情况。存储是分散的，每一个节点只要记录下一节点，就把所有数据串了起来，形成一个单向链表。

节点是由一个需要存储的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：存储的对象、对下一个节点的引用。如下图：

双向链表

双向链表是一种更复杂的链表。每个节点有两个连接：一个指向前一个节点，(当此”连接”为第一个”连接”时，指向空值或者空列表)；而当另一个指向下一个节点，(当此“连接”为最后一个“连接”时，指向空值或者空列表)

一个双向链表有三个整数值：数值，向后的节点链接，向前的节点链接。
双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样就可以从任何一个节点访问前一个节点，当然也可以访问后一个节点么，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。
由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点，形成一个下面说的循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表，对于把链表单独的存在数组里的情况，也可以直接用这个数组表示链表并用第0个或者第-1个(如果编译器支持)节点固定的表示这个虚拟节点。

循环链表

在一个循环链表中，首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向知道返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存，假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。
指向整个列表的指针可以被称作存储指针。

如上图用单向链表构建的循环链表。
循环链表中第一个节点就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大。当然，如果只会在最后插入数据(或者只会在之前)，处理也很容易。
另外一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手动跳转到第一个节点。访问到第一个节点之前的时候，也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

存储结构

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

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

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

链表的几大特性

链表主要有以下几个特性：

  1. 解决数组无法存储多种数据类型的问题
  2. 解决数组中，元素个数无法改变的限制
  3. 数组移动元素的过程中，要对元素进行大范围的移动，很耗时间，效率也不高。

链表的应用

连表用来构建许多其他的数据结构，如堆栈，行列和他们的衍生。
节点的数据域，也可以成为另一个链表。通过这种手段，我们可以用列表来构建许多链性数据结构；这个实例产生于Lisp编程语言，在Lisp中链表是初级数据结构，并且成为了常见的基础编程模式。有时候，链表用来生成联合数组，在这种情况下我们称之为联合数列。这种情况下用链表会优于其他数据结构，如自平衡二叉查找树(self-balancing binary search trees)甚至是一些小的数据集合。不管怎样，一些时候一个链表在这样一个树中建立一个节点子集，并且以此来更有效率的转换这个集合。

C代码实例

链表的数据结构

1
2
3
4
struct list_node {
    int data; //数据域，用于存储数据
    struct list_node *next; //指针，可以用来访问节点数据，也可以遍历，指向下一个节点
};

创建一个链表的一个节点

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list_node {
    int data;
    struct list_node *next;
};

typedef struct list_node list_single;

int main(void) {
    list_single *node = NULL; //1、首先定义一个头指针
    node = (list_single *)malloc(sizeof(list_single)); //2、然后分配内存空间
    
    if (node == NULL) {
        printf("malloc fair!\n");
    }
    
    memset(node, 0, sizeof(list_single)); //3、清一下
    node->data = 100; //4、给链表节点的数据赋值
    node->next = NULL; //5、将链表的指针域指向空
    printf("%d\n", node->data);
    free(node);
    return 0;
}

把创建节点封装成一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
list_single *create_list_node(int data) {
    list_single *node = NULL; //1、首先定义一个头指针
    node = (list_single *)malloc(sizeof(list_single)); //2、然后分配内存空间
    
    if (node == NULL) {
        printf("malloc fair!\n");
    }
    
    memset(node, 0, sizeof(list_single)); //3、清一下
    node->data = data; //4、给链表节点的数据赋值
    node->next = NULL; //5、将链表的指针域指向空
    printf("%d\n", node->data);
    free(node);
    return 0;
}

接着完成上面的程序

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list_node {
    int data;
    struct list_node *next;
};

typedef struct list_node list_single;

list_single *create_list_node(int data) {
    list_single *node = NULL; //1、首先定义一个头指针
    node = (list_single *)malloc(sizeof(list_single)); //2、然后分配内存空间
    
    if (node == NULL) {
        printf("malloc fair!\n");
    }
    
    memset(node, 0, sizeof(list_single)); //3、清一下
    node->data = data; //4、给链表节点的数据赋值
    node->next = NULL; //5、将链表的指针域指向空
    printf("%d\n", node->data);
    free(node);
    return 0;
}

int main(void) {
    int data = 100;
    list_single *node = create_list_node(data);
    printf("node->data = %d\n", node->data);
    printf("node->next = %d\n", node->next);
    free(node);
    return 0;
}

执行结果

范例代码是一个ADT（抽象数据类型）双向环形链表的基本操作部分的实例（未包含线程安全机制），全部遵从ANSI C标准，由User:JohnBull贡献，代码遵从GPL版权许可：

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
//声明接口
#ifndef LLIST_H
#define LLIST_H

typedef void node_proc_fun_t(void *);
typedef int node_comp_fun_t(const void*, const void*);

typedef void LLIST_T;

LLIST_T *llist_new(int elmsize);
int llist_delete(LLIST_T *);

int llist_node_append(LLIST_T *, const void *);
int llist_node_prepend(LLIST_T *, const void *);

int llist_travel(LLIST_T *, node_proc_fun_t*);
int llist_sort(LLIST_T *, node_comp_fun_t*);

void *llist_node_delete(LLIST_T *, node_comp_fun_t *, const void *key);
void *llist_node_find(LLIST_T *, node_comp_fun_t *, const void *key);

//类型确定
struct node_st{
    void *datap;
    struct node_st *next, *prev;
};

struct llist_st{
    struct node_st head;
    int elmsize;
    int elmnr;
};

//初始化和销毁
LLIST_T *llist_new(int elmsize){
    struct llist_st *newlist;
    newlist = malloc(sizeof(struct llist_st));
    
    if (newlist == NULL) {
        return NULL;
    }
    
    newlist -> head.datap = NULL;
    newlist -> head.next = &newlist -> head;
    newlist -> head.prev = &newlist -> head;
    
    newlist -> elmsize = elmsize;
    
    return (void *)newlist;
}

int llist_delete(LLIST_T *ptr) {
    struct llist_st *me = ptr;
    struct node_st *curr, *save;
    
    for (curr = me -> head.next; curr != &me -> head; curr = save) {
        save = curr -> next;
        free(curr -> datap);
        free(curr);
    }
    
    free(me);
    return 0;
}

//节点插入
int llist_node_append(LLIST_T *ptr, const void *datap) {
    struct llist_st *me = ptr;
    struct node_st *newnodep;
    
    newnodep = malloc(sizeof(struct node_st));
    
    if (newnodep == NULL) {
        return -1;
    }
    
    newnodep -> datap = malloc(me -> elmsize);
    
    if (newnodep -> datap == NULL) {
        free(newnodep);
        return -1;
    }
    
    memcpy(newnodep -> datap, datap, me -> elmsize);
    
    me -> head.prev -> next = newnodep;
    newnodep -> prev = me -> head.prev;
    me -> head.prev = newnodep;
    newnodep -> next = &me -> head;
    
    return 0;
}

//遍历
template<class T>
class ChainIterator {
    public: T* Initialize(const Chain<T> &c) {
        location = c.first;
        if (!location) return &location -> data;
        return 0;
    }
    
    T *Next() {
        if (!location) return 0;
        location = location -> link;
        if (location) return &location -> data;
        return 0;
    }
    
    private: ChainNode<T> *location;
}

以下代码摘自Linux内核2.6.21.5源码(部分)，展示了链表的另一种实现思路，未采用ANSI C标准，采用GNU C标准，遵从GPL版权许可：

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
struct list_head {
    struct list_head *next, *prev;
};
 
#define LIST_HEAD_INIT(name) { &(name), &(name) }
 
#define LIST_HEAD(name) /
    struct list_head name = LIST_HEAD_INIT(name)
 
static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}
 
static inline void __list_add(struct list_head *new, 
                        struct list_head *prev, 
                        struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
 
static inline void list_add(struct list_head *new, struct list_head *head) {
    __list_add(new, head, head->next);
}
 
static inline void __list_del(struct list_head * prev, struct list_head * next) {
    next->prev = prev;
    prev->next = next;
}
 
 
static inline void list_del(struct list_head *entry) {
    __list_del(entry->prev, entry->next);
    entry->next = NULL;
    entry->prev = NULL;
}
 
#define __list_for_each(pos, head) /
    for (pos = (head)->next; pos != (head); pos = pos->next)
 
#define list_for_each_entry(pos, head, member)                          /
    for (pos = list_entry((head)->next, typeof(*pos), member);      /
    prefetch(pos->member.next), &pos->member != (head);        /
    pos = list_entry(pos->member.next, typeof(*pos), member))

python代码的实现

单向链表

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
class SingleNode(object):
    """单链表的节点"""
    def __init__(self, element):
        self.elem = element
        self.next = None



class SingleLinkedList(object):
    """单链表"""
    def __init__(self, node = None):
        self._head = node

    def is_empty(self):
        """判断是否为空"""
        return self._head == None

    def length(self):
        """返回链表的长度"""
        # cur游标 用来遍历节点
        cur = self._head
        # count 记录数量
        count = 0

        while cur != None:
            count += 1
            cur = cur.next

        return count

    def travel(self):
        """遍历整个链表"""
        # cur游标 用来遍历节点
        cur = self._head

        while cur != None:
            print (cur.elem)
            cur = cur.next

    def add(self, item):
        """链表头部添加元素"""
        node = SingleNode(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        """链表尾部添加元素"""
        node = SingleNode(item)

        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素"""

        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            pre = self._head
            count = 0

            while count <= (pos - 1):
                count += 1
                pre = pre.next
            # 当循环结束后，pre指向pos-1的位置
            node = SingleNode(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """删除节点"""
        cur = self._head
        pre = None
        while cur != None:
            if cur.elem == item:
                if cur == self._head:
                    self._head = cur.next
                else:
                     pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next


    def search(self, item):
        """查找节点是否存在"""
        cur = self._head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

双向链表

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
class Node(object):
    """结点"""
    def __init__(self, item):
        self.elem = item
        self.next = None
        self.prev = None

class DoubleLinkedList(object):
    """双链表"""

    def __init__(self, node=None):
        self._head = node

    def is_empty(self):
        """判断是否为空"""
        return self._head == None

    def length(self):
        """返回链表的长度"""
        # cur游标 用来遍历节点
        cur = self._head
        # count 记录数量
        count = 0

        while cur != None:
            count += 1
            cur = cur.next

        return count

    def travel(self):
        """遍历整个链表"""
        # cur游标 用来遍历节点
        cur = self._head

        while cur != None:
            print (cur.elem)
            cur = cur.next

    def add(self, item):
        """链表头部添加元素"""
        node = Node(item)
        node.next = self._head
        self._head = node
        node.next.prev = node

    def append(self, item):
        """链表尾部添加元素"""
        node = Node(item)

        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self, pos, item):
        """指定位置添加元素"""

        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            cur = self._head
            count = 0

            while count <= pos:
                count += 1
                cur = cur.next
            # 当循环结束后，pre指向pos-1的位置
            node = Node (item)
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node

    def remove(self, item):
        """删除节点"""
        cur = self._head
        while cur != None:
            if cur.elem == item:
                if cur == self._head:
                    self._head = cur.next
                    if cur.next:
                        #判断链表是否只有一个节点
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    if cur.prev.next:
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

    def search(self, item):
        """查找节点是否存在"""
        cur = self._head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

单向链表实现的循环链表

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
class SingleNode(object):
    """单链表的节点"""
    def __init__(self, element):
        self.elem = element
        self.next = None



class SingleCycleLinkedList(object):
    """单向循环链表"""
    def __init__(self, node = None):
        self._head = node

        if node:
            node.next = node

    def is_empty(self):
        """判断是否为空"""
        return self._head == None

    def length(self):
        """返回链表的长度"""
        if self.is_empty():
            return 0
        # cur游标 用来遍历节点
        cur = self._head
        # count 记录数量
        count = 1

        while cur.next != self._head:
            count += 1
            cur = cur.next

        return count

    def travel(self):
        """遍历整个链表"""
        # cur游标 用来遍历节点
        cur = self._head

        while cur.next != self._head:
            print (cur.elem)
            cur = cur.next

        # 退出循环，打印尾节点
        print (cur.elem)

    def add(self, item):
        """链表头部添加元素"""
        node = SingleNode(item)

        if self.is_empty():
            self._head = node
            node.next = node
            return

        cur = self._head

        while cur.next != self._head:
            cur = cur.next

        node.next = self._head
        self._head = node
        cur.next = node

    def append(self, item):
        """链表尾部添加元素"""
        node = SingleNode(item)

        if self.is_empty():
            self._head = node
            node.next = node
        else:
            cur = self._head

            while cur.next != self._head:
                cur = cur.next

            cur.next = node
            node.next = self._head

    def insert(self, pos, item):
        """指定位置添加元素"""

        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            pre = self._head
            count = 0

            while count <= (pos - 1):
                count += 1
                pre = pre.next
            # 当循环结束后，pre指向pos-1的位置
            node = SingleNode(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """删除节点"""
        if self.is_empty():
            return

        cur = self._head
        pre = None
        while cur.next != self._head:
            if cur.elem == item:
                if cur == self._head:
                    # 头节点情况
                    # 找尾节点
                    rear = self._head
                    while rear.next != self._head:
                        rear = rear.next
                    self._head = cur.next
                    rear.next = self._head
                else:
                     pre.next = cur.next
                return
            else:
                pre = cur
                cur = cur.next

        # 退出循环，cur指向尾节点
        if cur.elem == item:
            if cur == self._head:
                # 链表只有一个节点
                self._head = None
            else:
                pre.next = cur.next


    def search(self, item):
        """查找节点是否存在"""
        if self.is_empty():
            return False

        cur = self._head
        while cur.next != self._head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next

        if cur.elem == item:
            return True

        return False

只要弄懂了链表的原理，其实不管用什么语言实现，只不过是一种描述方式而已。

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2020 KNOWLEDGE IS POWER All Rights Reserved.

访客数 : | 访问量 :