一、 定义见百度百科链表
链表由表头和节点组成，节点分为数据域和指针域，数据域中存贮数据元素，指针域存储下个结点的地址
二、单链表实现逻辑
- 创建节点类Node和链表类Linklist，Linklist类中包含head属性，head的值为0或Node对象，Node类中包含value属性存储数据，next属性存储下个节点的地址（Node对象）
- 循环节点从head开始取next属性，直到next=0为止，返回当前对象
- 添加节点时调用循环方法返回最后一个节点对象，把返回节点的next改为当前Node对象，如当前没有节点，则Linklist实例的head属性修改为当前Node对象
- 删除节点时把前一个节点的next属性修改为后一个节点的Node对象，如果当前节点是最后一个对象
三、单链表代码实现
class
Node
:
def
__init__
(
self
,
value
,
node
=
0
)
:
self
.
value
=
value
self
.
next
=
node
class
LinkList
:
def
__init__
(
self
,
value
=
0
,
*
args
)
:
self
.
lenth
=
0
#创建表头head
self
.
head
=
0
if
value
==
0
else
Node
(
value
)
#如果初始化实例时传入多个参数，循环加入链表
p
=
self
.
head
for
i
in
[
*
args
]
:
node
=
Node
(
i
)
p
.
next
=
node
p
=
p
.
next
def
append
(
self
,
value
)
:
if
self
.
head
==
0
:
self
.
head
=
Node
(
value
)
else
:
self
.
iternodes
(
)
.
next
=
Node
(
value
)
def
iternodes
(
self
)
:
p
=
self
.
head
while
p
:
print
(
p
.
value
)
if
not
p
.
next
:
return
p
p
=
p
.
next
四、双链表实现
- 对比单链表，Node对象增加了before属性记录前一节点对象，同时增加insert、pop等方法
- 利用python的特殊方法，把Linklist类构造成一个类似list的类，可以使用len（）方法，可迭代
#创建Node类
class
Node
:
def
__init__
(
self
,
value
,
before
=
0
,
node
=
0
)
:
self
.
value
=
value
self
.
next
=
node
self
.
before
=
before
#创建链表类
class
LinkList
:
def
__init__
(
self
,
value
=
0
,
*
args
)
:
self
.
lenth
=
0
#创建表头head
self
.
head
=
0
if
value
==
0
else
Node
(
value
)
#如果初始化实例时传入多个参数，循环加入链表
if
self
.
head
!=
0
:
self
.
lenth
+=
1
p
=
self
.
head
for
i
in
[
*
args
]
:
node
=
Node
(
i
)
p
.
next
=
node
node
.
before
=
p
p
=
p
.
next
self
.
lenth
+=
1
#append方法，判断表头是否为空，每次执行lenth属性值+1
def
append
(
self
,
value
)
:
if
self
.
head
==
0
:
self
.
head
=
Node
(
value
)
self
.
lenth
+=
1
else
:
p
=
Node
(
value
)
cur
=
self
.
iternodes
(
)
cur
.
next
=
p
p
.
before
=
cur
self
.
lenth
+=
1
#insert方法（后插），是否表头特殊处理，每次执行lenth属性值+1
def
instert
(
self
,
value
,
index
)
:
if
self
.
head
==
0
:
self
.
append
(
value
)
else
:
p
=
Node
(
value
)
prv
=
self
.
iternodes
(
index
)
if
prv
.
__dict__
.
get
(
'head'
)
:
p
.
before
=
prv
.
head
prv
.
head
.
next
=
p
if
prv
.
head
.
next
!=
0
:
prv
.
head
.
next
.
before
=
p
p
.
next
=
prv
.
head
.
next
else
:
p
.
before
=
prv
if
prv
.
next
!=
0
:
prv
.
next
.
before
=
p
p
.
next
=
prv
.
next
prv
.
next
=
p
self
.
lenth
+=
1
#遍历方法，每次从表头开始
def
iternodes
(
self
,
index
=
None
)
:
if
index
is
not
None
:
if
index
>
self
.
lenth
:
raise
Exception
(
"索引超界"
)
p
=
self
.
head
i
=
0
while
p
:
if
i
==
index
:
return
p
p
=
p
.
next
i
+=
1
else
:
p
=
self
.
head
while
p
:
if
not
p
.
next
:
return
p
p
=
p
.
next
#删除方法，删除指定索引的值，表头特殊处理，每次执行lenth属性值-1
def
pop
(
self
,
index
=
None
)
:
if
self
.
lenth
==
0
:
return
'LinkList is empty'
if
index
is
None
:
if
self
.
lenth
==
1
:
self
.
head
=
0
self
.
lenth
-=
1
return
if
self
.
iternodes
(
)
.
before
==
0
:
self
.
iternodes
(
)
.
value
=
0
else
:
self
.
iternodes
(
)
.
before
.
next
=
0
elif
index
==
0
:
if
self
.
iternodes
(
index
)
.
next
==
0
:
self
.
head
=
0
else
:
self
.
head
.
next
.
before
=
0
self
.
head
=
self
.
head
.
next
else
:
self
.
iternodes
(
index
)
.
before
.
next
=
self
.
iternodes
(
index
)
.
next
self
.
iternodes
(
index
)
.
next
.
before
=
self
.
iternodes
(
index
)
.
before
self
.
lenth
-=
1
def
__len__
(
self
)
:
return
self
.
lenth
def
__iter__
(
self
)
:
yield
from
(
self
.
iternodes
(
i
)
for
i
in
range
(
self
.
lenth
)
)
