双向链表的原理与实践

发表于 更新于 分类于 ，

1643104459(1)

双向链表的原理与实践

链表，别名链式存储结构或单链表，用于存储逻辑关系为 “一对一” 的数据。链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的，链表的每一个节点都有下一个节点的地址或引用，其结构类似下面这样：

1
（[数据域][指针域]）->（[数据域][指针域]）->（[数据域][指针域]）->（[数据域][指针域]）

其中每个（）代表一个链表的结点，而双向链表，指的是各个节点之间的逻辑关系是双向的，每个节点都有上一个节点和下一个节点的地址或引用

1
（[数据域][指针域]）<->（[数据域][指针域]）<->（[数据域][指针域]）<->（[数据域][指针域]）

双向链表可以快速找到一个节点的下一个节点，也可以快速找到一个节点的上一个节点，可以快速去掉链表中的某一个节点，使用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
146
147
148
# -*- coding: UTF-8 -*-

class Node:
    # 构造方法
    def __init__(self, key, value):
        self.key = key
        self.value = value
        # 上一个节点
        self.prev = None
        # 下一个节点
        self.next = None

    # 类似toString方法，使用print 打印这个类对象的时候，会隐式调用
    def __str__(self):
        val = '{%d: %d}' % (self.key, self.value)
        return val

    # 和__str__类似，也有相同的作用，命令行中空敲实例名则默认使用repr输出实例信息，结合eval函数使用通常会将该变量的结果转换回原始对象,即将对象转化为供编译器（即机器）读取的形式。
    def __repr__(self):
        val = '{%d: %d}' % (self.key, self.value)
        return val


class DoubleLinkList:
    def __init__(self, capacity=0xfffff):
        self.capacity = capacity
        # 头部节点引用
        self.head = None
        # 尾部节点引用
        self.tail = None
        # 当前存储了多少节点
        self.size = 0

    # 从头部添加
    def __add_head(self, node):
        # 如果当前链表没有头部节点，空的
        if not self.head:
            self.head = node
            self.tail = node
            self.head.next = None
            self.head.prev = None
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
            self.head.prev = None
        self.size += 1
        return node

    # 从尾部添加
    def __add_tail(self, node):
        # 如果当前链表没有尾部节点，尾部节点是空的
        if not self.tail:
            self.tail = node
            self.head = node
            self.tail.next = None
            self.tail.prev = None
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
            self.tail.next = None
        self.size += 1
        return node

    # 从尾部删除
    def __del_tail(self):
        if not self.tail:
            return
        node = self.tail

        if node.prev:
            self.tail = node.prev
            self.tail.next = None
        else:
            self.head = self.tail = None

        self.size -= 1
        return node

    # 从头部删除
    def __del_head(self):
        if not self.head:
            return
        node = self.head
        # 如果当前的头部节点有下一个节点，则把下一个节点设置为当前链表的头部节点
        if node.next:
            self.head = node.next
            self.head.prev = None
        else:
            self.head = self.tail = None
        self.size -= 1
        return node

    # 任意节点删除，注意此方法并没有判断传入的node在不在当前的链表中，如有需要自行实现
    def __remove(self, node):

        if self.size == 0:
            return
        # 如果node = None  默认删除尾部节点
        if not node:
            node = self.tail

        if node == self.tail:
            self.__del_tail()
        elif node == self.head:
            self.__del_head()
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
            self.size -= 1
        return node

    # 弹出头部节点
    def pop(self):
        return self.__del_head()

    # 添加节点
    def append(self, node):
        return self.__add_tail(node)

    # 往头部添加节点
    def append_front(self, node):
        return self.__add_head(node)

    # 删除节点
    def remove(self, node=None):
        return self.__remove(node)

    def print(self):
        p = self.head
        line = ''
        while p:
            line += '%s' % p
            p = p.next
            if p:
                line += '=>'
        print(line)


if __name__ == '__main__':
    l = DoubleLinkList(10)
    for i in range(10):
        l.append(Node(i, i))

    l.print()
    print(l.pop())
    l.print()