算法与数据结构之链表

fansichao 2021-10-23 16:16:35
Categories： > Tags：

链表

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

手把手实现 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 代码实现

相关资源

Python23项目切换
learn9-code-format