一、 定義見百度百科鏈表
鏈表由表頭和節點組成，節點分為數據域和指針域，數據域中存貯數據元素，指針域存儲下個結點的地址
二、單鏈表實現邏輯
- 創建節點類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
)
)
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
