算法与数据结构之链表

python►data-structure , Comments

链表

链表是计算机科学中最常用的数据结构之一。它也是最简单的结构之一，也是更高层结构(如堆栈、循环缓冲区和队列)的基础

  • 定义

    • 链表是计算机科学中最常用的数据结构之一。它也是最简单的结构之一，也是更高层结构(如堆栈、循环缓冲区和队列)的基础
    • 列表是通过引用连接的单个数据元素的集合.数据元素可以由地址数据、地理数据、几何数据、路由信息或事务细节组成。通常，链接列表的每个元素都具有特定于列表的相同数据类型
    • 单个列表元素称为节点。节点不同于顺序存储在内存中的数组。相反，它可能会在不同的内存段中找到它们，您可以通过跟踪从一个节点到下一个节点的指针找到这些内存段。通常使用 null 元素标记列表的结尾，该元素由 python 等效的 None 表示。
    • 链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题
    • 链表允许插入和删除表上任意位置上的节点，但是不允许随即存取
    • 内存中的存储形式可以分为连续存储和离散存储两种。因此，数据的物理存储结构就有连续存储和离散存储两种，它们对应了我们通常所说的数组和链表。

  • 单链表数据结构

    • head 保存首尾节点的地址
    • data1,next -> data2,next -> data3,next

  • 双链表数据结构

    • head=None 时为首节点，next=null 时为尾节点
    • head,data,next -> head,data,next -> head,data,next

  • 链表类型

    • 单链接列表
      • 节点只指向列表中的下一个元素
    • 双链接列表
      • 节点指向列表中的下一个元素，也指向上一个节点
    • 循环链表
      • 循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点

  • 链表应用场景

    • 数组应用场景：
      • 数据比较少
      • 经常做的运算是按序号访问数据元素；数组更容易实现，任何高级语言都支持；
      • 构建的线性表较稳定。
    • 链表应用场景：
      • 对线性表的长度或者规模难以估计
      • 频繁做插入删除操作
      • 构建动态性比较强的线性表。

手把手实现 python 的链表数据结构

数组和链表差异分析

  • 数组和链表的差异分析
    • 差异点
      • 链表是链式的存储结构；数组是顺序的存储结构。
      • 链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
      • 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；
      • 数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。
    • 相同点
      • 两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。

单链表和双链表的差异

  • 一、方向不同
    • 单链表只有指向下一个结点的指针
    • 双链表既有指向下一个结点的指针，也有指向上一个结点的指针
  • 二、适用情况不同
    • 单向链表更适合元素的增加与删除
    • 双向链表更适合元素的查询工作
  • 三、读取不同
    • 单链表只能单向读取
    • 双链表可以双向读取

链表的代码实现

单链表 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
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
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __str__(self):
        return str(self.data)


# 通过单链表构建一个list的结构： 添加  删除  插入   查找 获取长度  判断是否为空...
# list1 = []  list1.append(5)     [5,]             slist =  SingleList()   slist.append(5)
class SingleList:
    def __init__(self, node=None):
        self._head = node

    def isEmpty(self):
        return self._head == None

    def append(self, item):
        # 尾部添加
        node = Node(item)
        if self.isEmpty():
            self._head = node
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    # 求长度
    def len(self):
        cur = self._head
        count = 0

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

        return count

    # 遍历
    def print_all(self):
        cur = self._head
        while cur != None:
            print(cur)
            cur = cur.next

    def pop(self, index):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if index == 0:
            self._head = self._head.next
        else:
            cur = self._head
            # 找到当前下标的前一个元素
            while index - 1:
                cur = cur.next
                index -= 1
            # 修改的next的指向位置
            cur.next = cur.next.next

    def insert(self, index, item):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if isinstance(item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(item)

        if index == 0:
            node.next = self._head
            self._head = node
        else:
            cur = self._head

            while index - 1:
                cur = cur.next
                index -= 1

            node.next = cur.next
            cur.next = node

    def update(self, index, new_item):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if isinstance(new_item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(new_item)

        if index == 0:
            node.next = self._head.next
            self._head = node
        else:
            cur = self._head
            node.next = cur.next.next
            cur.next = node



    def remove(self, item):
        if isinstance(item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(item)

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


if __name__ == '__main__':
    slist = SingleList()
    print(slist.isEmpty())  # True
    print(slist.len())

    slist.append(5)
    print(slist.isEmpty())  # False
    print(slist.len())  # 1

    slist.append(8)
    slist.append(6)
    slist.append(3)
    slist.append(1)
    print(slist.isEmpty())  # True
    print(slist.len())
    print('---------------------')
    slist.print_all()

    print('----------pop-------------')
    slist.pop(2)
    slist.print_all()

    print('--------insert-------')
    slist.insert(1, 19)
    slist.print_all()

    print('--------update-------')
    slist.update(1, 18)
    slist.print_all()

    print('--------remove-------')
    slist.remove(18)
    slist.print_all()

双链表 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
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
'''
双向链表
'''
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

    def __str__(self):
        return str(self.data)


class DoubleList:
    def __init__(self):
        self._head = None

    def isEmpty(self):
        return self._head == None

    def append(self, item):
        # 尾部添加
        node = Node(item)
        if self.isEmpty():
            self._head = node
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node

        # 求长度

    def add(self, item):
        node = Node(item)
        if self.isEmpty():
            self._head = node
        else:
            node.next = self._head
            self._head.prev = node
            self._head = node

    def len(self):
        cur = self._head
        count = 0

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

        return count

    def print_all(self):
        cur = self._head
        while cur != None:
            print(cur)
            cur = cur.next

    def insert(self, index, item):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if isinstance(item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(item)

        if index == 0:
            node.next = self._head
            node.prev = self._head.prev
            self._head = node
        else:
            cur = self._head

            while index - 1:
                cur = cur.next
                index -= 1

            node.next = cur.next
            node.prev = cur.prev
            cur.next = node
            cur.prev = node.prev

    def remove(self, item):
        if isinstance(item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(item)

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

        cur.next = cur.next.next
        cur.prev = cur.prev

    def update(self, index, new_item):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if isinstance(new_item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(new_item)

        if index == 0:
            node.next = self._head.next
            node.prev = self._head.prev
            self._head = node
        else:
            cur = self._head
            node.next = cur.next.next
            node.prev = cur.prev
            cur.next = node
            cur.prev = node


if __name__ == '__main__':
    dlist = DoubleList()

    print(dlist.len())
    print(dlist.isEmpty())

    # dlist.append(6)
    # dlist.append(9)
    # dlist.append(5)
    # print(dlist.len())
    # print(dlist.isEmpty())
    # dlist.print_all()

    dlist.add(6)
    dlist.add(9)
    dlist.add(5)

    dlist.print_all()

    print('--------insert-------')
    dlist.insert(1, 19)
    dlist.print_all()

    print('--------update-------')
    dlist.update(1, 18)
    dlist.print_all()

    print('--------remove-------')
    dlist.remove(18)
    dlist.print_all()

单链表和双链表的 Python 代码实现

相关资源

fansichaoData Engineer & SSE & CYO

个人简介。