链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向NULL。为了方便链表的删除与插入操作，可以为链表添加一个表头。
删除操作可以通过修改一个指针来实现。
插入操作需要执行两次指针调整。
1.1 Node实现
每个Node分为两部分。一部分含有链表的元素，可以称为数据域；另一部分为一指针，指向下一个Node。
|
1
2
3
4
5
6
7
8
9
10
11
12
13 |
class
Node(): __slots__=[‘_item‘,‘_next‘] #限定Node实例的属性 def
__init__(self,item): self._item=item self._next=None
#Node的指针部分默认指向None def
getItem(self): return
self._item def
getNext(self): return
self._next def
setItem(self,newitem): self._item=newitem def
setNext(self,newnext): self._next=newnext |
1.2 SinglelinkedList的实现
|
1
2
3
4 |
class
SingleLinkedList(): def
__init__(self): self._head=None
#初始化链表为空表 self._size=0 |
1.3 检测链表是否为空
|
1
2 |
def isEmpty(self): return
self._head==None |
1.4 add在链表前端添加元素
|
1
2
3
4 |
def add(self,item): temp=Node(item) temp.setNext(self._head) self._head=temp |
1.5 append在链表尾部添加元素
|
1
2
3
4
5
6
7
8
9
10 |
def append(self,item): temp=Node(item) if
self.isEmpty(): self._head=temp #若为空表，将添加的元素设为第一个元素 else: current=self._head while
current.getNext()!=None: current=current.getNext() #遍历链表 current.setNext(temp) #此时current为链表最后的元素 |
1.6 search检索元素是否在链表中
|
1
2
3
4
5
6
7
8
9 |
def search(self,item): current=self._head founditem=False while
current!=None
and not founditem: if
current.getItem()==item: founditem=True else: current=current.getNext() return
founditem |
1.7 index索引元素在链表中的位置
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 |
def index(self,item): current=self._head count=0 found=None while
current!=None
and not found: count+=1 if
current.getItem()==item: found=True else: current=current.getNext() if
found: return
count else: raise
ValueError,‘%s is not in linkedlist‘%item |
1.8 remove删除链表中的某项元素
|
1
2
3
4
5
6
7
8
9
10
11
12
13 |
def remove(self,item): current=self._head pre=None while
current!=None: if
current.getItem()==item: if
not pre: self._head=current.getNext() else: pre.setNext(current.getNext()) break else: pre=current current=current.getNext() |
1.9 insert链表中插入元素
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 |
def insert(self,pos,item): if
pos<=1: self.add(item) elif
pos>self.size(): self.append(item) else: temp=Node(item) count=1 pre=None current=self._head while
count<pos: count+=1 pre=current current=current.getNext() pre.setNext(temp) temp.setNext(current) |
全部代码
|
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 |
class
Node(): __slots__=[‘_item‘,‘_next‘] def
__init__(self,item): self._item=item self._next=None def
getItem(self): return
self._item def
getNext(self): return
self._next def
setItem(self,newitem): self._item=newitem def
setNext(self,newnext): self._next=newnext class
SingleLinkedList(): def
__init__(self): self._head=None
#初始化为空链表 def
isEmpty(self): return
self._head==None def
size(self): current=self._head count=0 while
current!=None: count+=1 current=current.getNext() return
count def
travel(self): current=self._head while
current!=None: print
current.getItem() current=current.getNext() def
add(self,item): temp=Node(item) temp.setNext(self._head) self._head=temp def
append(self,item): temp=Node(item) if
self.isEmpty(): self._head=temp #若为空表，将添加的元素设为第一个元素 else: current=self._head while
current.getNext()!=None: current=current.getNext() #遍历链表 current.setNext(temp) #此时current为链表最后的元素 def
search(self,item): current=self._head founditem=False while
current!=None
and not founditem: if
current.getItem()==item: founditem=True else: current=current.getNext() return
founditem def
index(self,item): current=self._head count=0 found=None while
current!=None
and not found: count+=1 if
current.getItem()==item: found=True else: current=current.getNext() if
found: return
count else: raise
ValueError,‘%s is not in linkedlist‘%item def
remove(self,item): current=self._head pre=None while
current!=None: if
current.getItem()==item: if
not pre: self._head=current.getNext() else: pre.setNext(current.getNext()) break else: pre=current current=current.getNext() def
insert(self,pos,item): if
pos<=1: self.add(item) elif
pos>self.size(): self.append(item) else: temp=Node(item) count=1 pre=None current=self._head while
count<pos: count+=1 pre=current current=current.getNext() pre.setNext(temp) temp.setNext(current)if __name__==‘__main__‘: a=SingleLinkedList() for
i in
range(1,10): a.append(i) print
a.size() a.travel() print
a.search(6) print
a.index(5) a.remove(4) a.travel() a.insert(4,100) a.travel() |
原文：http://www.cnblogs.com/linxiyue/p/3551633.html