数据结构复习二 双向链表(python实现)

前言

端午假期差不多结束了,感觉离暑假又靠近了,好像我们学校放假比较晚,还是别想放假的事情了,我还是乖乖去复习我的概率(求二重积分全都忘光了,重新拿起高数奋斗),
微机(实验写汇编对指令不熟),计网(子网跟超网的题目还不熟练),双向链表其实就是比单向链表的节点多了一个前驱结点的部分,虽然简单但是还是在编写时出现问题,出现问题就值得去记录

正文

双向链表的实现,这个双向链表比昨天写的多了一点点而而已,头结点的前驱节点默认是None,而且在遍历,搜索以及判空等步骤都是与昨天的写法一样,可以直接尝试import一下昨天的文件,让今天的双向链表继承昨天的单向链表的相同操作
(python 3.5实现)

代码如下:

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
# -*- coding: utf-8 -*-
# Author:0verWatch

class Node(object):
def __init__(self, elem):
self.elem = elem
self.next = None
self.prev = None

class DoubleLinkList(object):
def __init__(self, node=None): #这里默认第一个节点的前驱指针指的是None
self.__head = node #私有化

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


def length(self):
cur = self.__head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count



def travel(self):
cur = self.__head
while cur is not None:
print(cur.elem, end=" ")
cur = cur.next #这两句话顺序不能调换


##其实上面的都不用改

def add(self, item):
node = Node(item)
node.next = self.__head
self.__head = node
if node.next is not None:
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 is not None:
cur = cur.next
node.next = cur.next
node.prev = cur
cur.next = node

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

def remove(self, item):
cur = self.__head
while cur is not None:
if cur.elem == item:
if cur == self.__head:
# 判断链表是否只有一个节点,不是的话就执行这一条件语句
self.__head = None
if cur.next:
self.__head = cur.next
else:
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
break #注意下这里的break,不要忘了
else:
cur = cur.next


def search(self, item):
cur = self.__head
while cur is not None:
if cur.elem == item:
return True
else:
cur = cur.next
return False




if __name__ == '__main__':
# test_1
lst = DoubleLinkList()
print(lst.is_empty())
print(lst.length())

# test_2
lst.append(2)
print(lst.is_empty())
lst.add(3) # 3 2
lst.insert(1, 5) # 3 1 5 2
lst.add(4) # 4 3 5 2
lst.append(6) # 4 3 5 2 6
print(lst.search(5))
lst.travel()


# test_3
lst.remove(5)
lst.remove(4)
lst.remove(6)
lst.travel()

小结

这里我记录一下我出现的几个问题
第一,各节点的链接操作一定要注意顺序,比如在遍历的时候进入循环后是先进行输出操作,再把指针移到下一位等等
第二,每一种操作都要注意考虑单个节点,是否为头结点,尾节点的问题,然后去给出一定的条件去控制,不然很容易出错,在写remove操作的时候我就在考虑完头结点之后就没有考虑是否为单个节点的情况,导致程序出错,
第三,注意remove操作break,这一点我还是用debugger功能一直F7 F8 F9找出来的。。。就发现一直在那个函数里面不出来,一直循环才惊醒要加break,23333
早早睡觉,明天早起复习概率论!!!!!!


听说,打赏我的人最后都成了大佬。



文章目录
  1. 1. 前言
  2. 2. 正文
  3. 3. 小结