-
Notifications
You must be signed in to change notification settings - Fork 0
/
SingleLink.py
134 lines (116 loc) · 3.22 KB
/
SingleLink.py
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
# 实现一个单链表
# 节点的实现
class SingleNode(object):
"""单链表的节点"""
def __init__(self, item):
#-item存放数据
self.item = item
#_next是下一个节点
self.next = None
'''
单链表的操作:
is_emoty()是否为空
length()链表长度
travel()链表遍历
add(item)链表头部添加元素
append(item)链表尾部添加元素
insert(pos,item)指定位置添加元素
remove(item)删除节点
search(item)搜索节点是否存在
'''
class SingleLinkList(object):
"""单链表"""
def __init__(self):
self._head = None
def is_emoty(self):
'''判断链表是否为空'''
return self._head == None
def length(self):
'''链表长度'''
# cur初始时指向头结点
cur = self._head
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
cur = self._head
while cur != None:
print(cur.item)
cur = cur.next
print('')
def add(self, item):
'''头部添加元素'''
node = SingleNode(item)
node.next = self._head
self._head = node
def append(self, item):
'''尾部添加元素'''
node = SingleNode(item)
if self.is_emoty():
self._head = node
else:
cur = self._head
while cur.next != None:
cur = cur.next
cur.next = node
def insert(self, pos, item):
'''指定位置添加元素'''
# 若指定位置为第一个元素前,执行头部插入
if pos <= 0:
self.add(item)
# 若指定位置为尾部,执行尾部插入
elif pos > (self.length() - 1):
self.append(item)
# 指定位置
else:
node = SingleNode(item)
count = 0
pre = self._head
while count < (pos - 1):
count += 1
pre = pre.next
node.next = pre.next
pre.next = node
def remove(self, item):
'''删除节点'''
cur = self._head
pre = None
while cur != None:
# 找到要删除的节点
if cur.item == item:
if not pre:
self._head = cur.next
else:
# 将删除位置的下一个节点赋给删除的前一个节点
pre.next = cur.next
break
# 没找到要删除的节点,继续向后移
else:
pre = cur
cur = cur.next
def search(self, item):
'''链表查找节点是否存在,并返回T,F'''
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
if __name__ == '__main__':
# 定义一个单链表
ll = SingleLinkList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(5)
ll.insert(3, 4)
ll.add(0)
print('链表长度为:', ll.length())
ll.travel()
print(ll.search(5))
ll.remove(2)
print(ll.search(2))
print('-------')
ll.travel()