-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathsinglinklist.py
More file actions
122 lines (109 loc) · 2.91 KB
/
Copy pathsinglinklist.py
File metadata and controls
122 lines (109 loc) · 2.91 KB
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
# -*- coding: utf-8 -*-
# @Time : 2019/5/2 9:52
# @Author : Scavenger
# @FileName: singlinklist.py
# @Software: PyCharm
# @Github : https://github.com/dgfwork/
# @Blog : https://www.cnblogs.com/gaofeng-d/
class Node(object):
def __init__(self, val):
self.next = None
self.val = val
class SingLinkList(object):
def __init__(self, node=None):
self.__head = node
def is_empty(self):
return self.__head == None
def length(self):
"""
:return:链表长度
"""
if self.is_empty():
return 0
else:
cur = self.__head
count = 0
while cur:
count += 1
cur = cur.next
return count
def append(self, val): # 尾插法
node = Node(val)
if self.__head == None:
self.__head = node
else:
cur = self.__head
while cur.next:
cur = cur.next # 找到尾结点
cur.next = node
def travel(self):
if self.is_empty():
return
else:
cur = self.__head
while cur:
print(cur.val, end=" ")
cur = cur.next
def add(self, val):
"""
头插法 画表示意即可
:param val:插入值
:return:
"""
node = Node(val)
node.next = self.__head
self.__head = node
def insert(self, position, value):
if position <= 0:
position = 0
if position >= self.length() - 1:
position = self.length() - 1
# 插入位置正常之后，找到位置插入进去即可
pre = self.__head
count = 0
node = Node(value)
while count < position - 1:
count += 1
pre = pre.next
node.next = pre.next
pre.next = node
def remove(self, item):
pre = self.__head
# 要遍历到需要删除节点的前一个节点
while pre.next:
# 这里面还需要对删除第一个元素做单独处理
if item == pre.val:
self.__head = pre.next
break
else:
# 处理中间和后面的元素
if pre.next.val == item:
pre.next = pre.next.next
else:
pre = pre.next
def search(self, item):
"""
全部遍历一遍
:param item:
:return:
"""
cur = self.__head
while cur:
if cur.val == item:
return True
else:
cur = cur.next
return False
if __name__ == "__main__":
sll = SingLinkList()
sll.append(100)
sll.append(200)
sll.append(300)
sll.append(400)
sll.add(10)
sll.add(20)
sll.travel()
print(" ")
print(sll.length())
sll.remove(200)
sll.travel()