链表是一种物理存储单元上非连续、非顺序的存储结构, 数据元素的逻辑顺序是通过链表中的指针链接次序实现的.
介绍
链表的基本单位为 node
node 存储 data 和 next
data: 数据
next: 指向下一个 node 的指针
插入单位为 n 的数据 时间复杂度为 O(1)
查找单位为 n 的数据 时间复杂度为 O(n)
代码
node
1
2
3
4
5
6
7
|
class Node(object):
def __init__(self,data):
self.data = data
self.next = None
def __repr__(self):
return str(self.data)
|
链表
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
|
class Link(object):
def __init__(self,head=None):
self.head = Node(head)
if head:
self.length = 1
else:
self.length = 0
def __len__(self):
return self.length
def __str__(self):
current = 0
p = self.head
item = '['
while current <= self.length:
item += ' ' + '\'' + str(p) + '\''
p = p.next
current += 1
item += ' ]'
return item
def __call__(self):
current = 0
p = self.head
while current <= self.length:
yield p
p = p.next
current += 1
def append(self,data):
data = Node(data)
if self.head == None:
self.head = data
else:
p = self.head
while p.next:
p = p.next
p.next,p.next.next = data,None
self.length += 1
def pop(self):
p = self.head
while p.next:
p = p.next
pp = p
pp = None
self.length -= 1
def insert(self,index,data):
data = Node(data)
if index == 0:
p = self.head
self.head = data
self.head.next = p
else:
current = 0
p = self.head
while current <= self.length:
if current +1 == index:
pp = p.next
p.next = data
p.next.next = pp
break
else:
current += 1
p = p.next
self.length += 1
def delete(self,index):
if index == 0:
self.head = self.head.next
else:
current = 0
p = self.head
while current <= self.length:
if current + 1 == index:
pp = p.next.next
p.next = pp
break
else:
current += 1
p = p.next
self.length -= 1
|