一、 定義見百度百科鏈表
鏈表由表頭和節(jié)點(diǎn)組成，節(jié)點(diǎn)分為數(shù)據(jù)域和指針域，數(shù)據(jù)域中存貯數(shù)據(jù)元素，指針域存儲(chǔ)下個(gè)結(jié)點(diǎn)的地址
二、單鏈表實(shí)現(xiàn)邏輯
- 創(chuàng)建節(jié)點(diǎn)類Node和鏈表類Linklist，Linklist類中包含head屬性，head的值為0或Node對(duì)象，Node類中包含value屬性存儲(chǔ)數(shù)據(jù)，next屬性存儲(chǔ)下個(gè)節(jié)點(diǎn)的地址（Node對(duì)象）
- 循環(huán)節(jié)點(diǎn)從head開始取next屬性，直到next=0為止，返回當(dāng)前對(duì)象
- 添加節(jié)點(diǎn)時(shí)調(diào)用循環(huán)方法返回最后一個(gè)節(jié)點(diǎn)對(duì)象，把返回節(jié)點(diǎn)的next改為當(dāng)前Node對(duì)象，如當(dāng)前沒有節(jié)點(diǎn)，則Linklist實(shí)例的head屬性修改為當(dāng)前Node對(duì)象
- 刪除節(jié)點(diǎn)時(shí)把前一個(gè)節(jié)點(diǎn)的next屬性修改為后一個(gè)節(jié)點(diǎn)的Node對(duì)象，如果當(dāng)前節(jié)點(diǎn)是最后一個(gè)對(duì)象
三、單鏈表代碼實(shí)現(xiàn)
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
#創(chuàng)建表頭head
self
.
head
=
0
if
value
==
0
else
Node
(
value
)
#如果初始化實(shí)例時(shí)傳入多個(gè)參數(shù)，循環(huán)加入鏈表
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
四、雙鏈表實(shí)現(xiàn)
- 對(duì)比單鏈表，Node對(duì)象增加了before屬性記錄前一節(jié)點(diǎn)對(duì)象，同時(shí)增加insert、pop等方法
- 利用python的特殊方法，把Linklist類構(gòu)造成一個(gè)類似list的類，可以使用len（）方法，可迭代
#創(chuàng)建Node類
class
Node
:
def
__init__
(
self
,
value
,
before
=
0
,
node
=
0
)
:
self
.
value
=
value
self
.
next
=
node
self
.
before
=
before
#創(chuàng)建鏈表類
class
LinkList
:
def
__init__
(
self
,
value
=
0
,
*
args
)
:
self
.
lenth
=
0
#創(chuàng)建表頭head
self
.
head
=
0
if
value
==
0
else
Node
(
value
)
#如果初始化實(shí)例時(shí)傳入多個(gè)參數(shù)，循環(huán)加入鏈表
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方法，判斷表頭是否為空，每次執(zhí)行l(wèi)enth屬性值+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方法（后插），是否表頭特殊處理，每次執(zhí)行l(wèi)enth屬性值+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
#刪除方法，刪除指定索引的值，表頭特殊處理，每次執(zhí)行l(wèi)enth屬性值-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
)
)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
