Sui Xin's Blog

链表的基础知识+Python实现四种链表

Posted on In Disqus:

链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入或删除的时候最快可以达到O(1)的复杂度（告诉节点地址的情况下），比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

四种常见的链表

  1. 单链表。每个节点只有一个属性.next，用于存放其后继节点；尾节点的后继为None；若链表为空，则头节点.head为None。
  2. 单向循环链表。每个节点只有一个属性.next，用于存放其后继节点；由于循环，故尾节点的后继为头节点；若链表为空，则头节点.head为None。
  3. 双向链表。每个节点有两个属性.prev和.next，分别用于存放其前驱节点和后继节点；尾节点的后继和头节点的前驱都为None；若链表为空，则头节点.head为None。
  4. 双向循环链表。每个节点有两个属性.prev和.next，分别用于存放其前驱节点和后继节点；由于循环，故尾节点的后继为头节点，头节点的前驱为尾节点；若链表为空，则头节点.head为None。

常见操作的时间复杂度

  1. 查找：O(n)；
  2. 插入：O(1)或O(n)，见下；
  3. 删除：O(1)或O(n)，见下。

  • O(1)的情况：

    • 一个已知头节点的链表，在某节点后面插入新节点，值为newdata，且告诉你该节点的地址node

      1
      2
      newnode = ListNode(newdata, _next=node.next)
      node.next = newnode
    • 一个已知头节点的链表，删除某节点，且告诉你该节点的地址node（思路为：将后面的节点前移一位） 
      1
      2
      3
      4
      node_n = node.next  # node_n为需删除节点node的下一个节点
      node.item = node_n
      node.next = node_n.next
      del node_n
  • O(n)的情况（见后文代码）：
    • 一个已知头节点的链表，在第index个元素后插入一个新元素
    • 一个已知头节点的链表，删除第index个元素或删除某个值为data的元素

Python实现

单节点类

1
2
3
4
5
class SingleListNode(object):
    """单节点类"""
    def __init__(self, _item, _next=None):
        self.item = _item
        self.next = _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
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
class SingleLinkedList(object):
    """单链表类"""
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def add(self, newdata):
        node = SingleListNode(newdata, _next=self.head)
        self.head = node

    def append(self, newdata):
        node = SingleListNode(newdata)
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, newdata):
        """将newdata插入pos位置之后"""
        if pos <= 0:
            self.add(newdata)
        elif pos > self.length() - 1:
            self.append(newdata)
        else:
            node = SingleListNode(newdata)
            cur = self.head
            count = 0
            while count < pos - 1:
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, olddata):
        """从单链表中删除所有的olddata"""
        cur = self.head
        pre = None
        while cur is not None:
            if cur.item == olddata:
                if not pre:
                    self.head = cur.next
                else:
                    pre.next = cur.next
                cur = cur.next
            else:
                pre = cur
                cur = cur.next

    def length(self):
        """返回单链表的长度"""
        cur = self.head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """打印整个单链表
        return
        ------
        ls: list，从前至后的单链表"""
        cur = self.head
        ls = []
        while cur is not None:
            ls.append(cur.item)
            cur = cur.next
        return ls

    def search(self, data):
        cur = self.head
        while cur is not None:
            if cur.item == data:
                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
class SingleCircleLinkedList(SingleLinkedList):
    """单向循环链表，继承单链表类"""
    def __init__(self):
        self.head = None

    def add(self, newdata):
        """将新节点添加到单向循环链表头部。即头指针指向新节点，尾节点的指针指向新节点，新节点的指针指向原头节点"""
        node = SingleListNode(newdata)
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            cur.next = node
            self.head = node

    def append(self, newdata):
        """与add方法唯一的区别为链表头的指针不变"""
        node = SingleListNode(newdata)
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            cur.next = node

    def remove(self, olddata):
        """删除一个指定的节点"""
        cur = self.head
        pre = None
        if self.is_empty():
            return
        elif self.head.item == olddata:
            while cur.next != self.head:
                cur = cur.next
            cur.next = self.head.next
            self.head = self.head.next
        else:
            pre = self.head
            while cur.next != self.head:
                if cur.item == olddata:
                    pre.next = cur.next
                    return
                pre = cur
                cur = cur.next
            if cur.item == olddata:
                pre.next = self.head

    def length(self):
        if self.is_empty():
            return 0
        cur = self.head
        count = 1
        while cur.next != self.head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        if self.is_empty():
            return
        cur = self.head
        ls = []
        while cur.next != self.head:
            ls.append(cur.item)
            cur = cur.next
        ls.append(cur.item)
        return ls

    def search(self, data):
        if self.is_empty():
            return False
        cur = self.head
        while cur.next != self.head:
            if cur.item == data:
                return True
            else:
                cur = cur.next
        if cur.item == data:
            return True
        return False

双向节点类

1
2
3
4
5
6
class DoubleListNode(object):
    """双向节点类"""
    def __init__(self, _item, _prev=None, _next=None):
        self.item = _item
        self.prev = _prev
        self.next = _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
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
class DoubleLinkedList(SingleLinkedList):
    """双向链表类，继承单链表类"""
    def __init__(self):
        self.head = None

    def add(self, newdata):
        node = DoubleListNode(newdata)
        if self.is_empty():
            self.head = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node

    def append(self, newdata):
        node = DoubleListNode(newdata)
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self, pos, newdata):
        if pos <= 0:
            self.add(newdata)
        elif pos > self.length() - 1:
            self.append(newdata)
        else:
            node = DoubleListNode(newdata)
            cur = self.head
            count = 0
            while count < pos - 1:
                count += 1
                cur = cur.next
            node.next = cur.next
            node.prev = cur
            cur.next.prev = node
            cur.next = node

    def remove(self, olddata):
        """删除一个指定的节点"""
        if self.is_empty():
            return
        elif self.head.item == olddata:
            if self.head.next is None:
                self.head = None
            else:
                self.head.next.prev = None
                self.head = self.head.next
        else:
            cur = self.head
            while cur.next is not None:
                if cur.item == olddata:
                    cur.next.prev = cur.prev
                    cur.prev.next = cur.next
                    return
                cur = cur.next
            if cur.item == olddata:
                cur.prev.next = None

双向循环链表

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
class DoubleCircleLinkedList(SingleCircleLinkedList):
    """双向循环链表类"""
    def __init__(self):
        self.head = None

    def add(self, newdata):
        node = DoubleListNode(newdata)
        if self.is_empty():
            self.head = node
            node.prev = node
            node.next = node
        else:
            node.prev = self.head.prev
            node.next = self.head
            self.head.prev.next = node
            self.head.prev = node
            self.head = node

    def append(self, newdata):
        node = DoubleListNode(newdata)
        if self.is_empty():
            self.head = node
            node.prev = node
            node.next = node
        else:
            self.head.prev.next = node
            self.head.prev = node
            node.prev = self.head.prev
            node.next = self.head

    def insert(self, pos, newdata):
        if pos <= 0:
            self.add(newdata)
        elif pos > self.length() - 1:
            self.append(newdata)
        else:
            node = DoubleListNode(newdata)
            cur = self.head
            count = 0
            while count < pos - 1:
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next.prev = node
            node.prev = cur
            cur.next = node

    def remove(self, olddata):
        if self.is_empty():
            return
        elif self.head.item == olddata:
            if self.length() == 1:
                self.head = None
            else:
                self.head.prev.next = self.head.next
                self.head.next.prev = self.head.prev
                self.head = self.head.next
        else:
            cur = self.head.next
            while cur != self.head:
                if cur.item == olddata:
                    cur.prev.next = cur.next
                    cur.next.prev = cur.prev
                cur = cur.next

测试函数

1
2
3
4
5
6
7
8
9
10
11
12
13
def test_SL():
    SL = SingleLinkedList()
    print('单链表是否为空：', SL.is_empty())
    SL.add(1)
    SL.add(2)
    SL.append(5)
    print('单链表为：', SL.travel())
    SL.insert(2, 3)
    print('单链表中是否有4：', SL.search(4))
    print('单链表为：', SL.travel())
    print('单链表长度：', SL.length())
    SL.remove(2)
    print('单链表为：', SL.travel())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def test_SCL():
    SCL = SingleCircleLinkedList()
    print('单循环链表是否为空：', SCL.is_empty())
    SCL.add(1)
    SCL.add(2)
    SCL.append(5)
    print('单循环链表为：', SCL.travel())
    print("在第二个节点之后插入节点'3'")
    SCL.insert(2, 3)
    print('单循环链表为：', SCL.travel())
    print('单循环链表中是否有4：', SCL.search(4))
    print('单循环链表长度：', SCL.length())
    print("删除节点'5'")
    SCL.remove(5)
    print('单循环链表为：', SCL.travel())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def test_DL():
    DL = DoubleLinkedList()
    print('双向链表是否为空：', DL.is_empty())
    DL.add(1)
    DL.add(2)
    DL.append(5)
    print('双向链表为：', DL.travel())
    print("在第二个节点之后插入节点'3'")
    DL.insert(2, 3)
    print('双向链表为：', DL.travel())
    print('双向链表中是否有4：', DL.search(4))
    print('双向链表长度：', DL.length())
    print("删除节点'1'")
    DL.remove(1)
    print('双向链表为：', DL.travel())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def test_DCL():
    DCL = DoubleCircleLinkedList()
    print('双向循环链表是否为空：', DCL.is_empty())
    DCL.add(1)
    DCL.add(2)
    DCL.append(5)
    print('双向循环链表为：', DCL.travel())
    print("在第二个节点之后插入节点'3'")
    DCL.insert(2, 3)
    print('双向循环链表为：', DCL.travel())
    print('双向循环链表中是否有10：', DCL.search(10))
    print('双向循环链表长度：', DCL.length())
    print("删除节点'1'")
    DCL.remove(1)
    print('双向循环链表为：', DCL.travel())

参考

维基百科：链表
数据结构：线性表
https://segmentfault.com/a/1190000014484156
https://www.jianshu.com/p/06a0e3c433c6
https://www.cnblogs.com/Lin-Yi/p/7326713.html

Related Posts