https://www.bilibili.com/video/av53583801/?p=20
學(xué)習(xí)筆記
文章目錄
- 1 Single Link List
- 2 Double Link List
- 3 Single Cycle Link List
- 4 小結(jié)
1 Single Link List
圖片來源：https://www.bilibili.com/video/av53583801/?p=19
class
Node
(
object
)
:
def
__init__
(
self
,
value
,
next
=
None
)
:
self
.
value
=
value
self
.
next
=
next
class
SingleLinkList
(
object
)
:
def
__init__
(
self
,
node
=
None
)
:
self
.
__head
=
node
# 初始化頭指針指向 None
def
is_enmpty
(
self
)
:
"""鏈表是否為空"""
return
self
.
__head
==
None
def
length
(
self
)
:
"""鏈表長度"""
cur
=
self
.
__head
# 頭節(jié)點(diǎn)
count
=
0
while
(
cur
)
:
# 當(dāng)前指針不指向 None 時(shí)候
count
+=
1
cur
=
cur
.
next
return
count
def
travel
(
self
)
:
"""遍歷鏈表"""
cur
=
self
.
__head
# 頭節(jié)點(diǎn),私有變量
while
(
cur
)
:
# 當(dāng)前指針不指向 None 時(shí)候
print
(
cur
.
value
,
end
=
" "
)
cur
=
cur
.
next
print
(
""
)
def
append
(
self
,
item
)
:
"""鏈表尾部添加元素"""
node
=
Node
(
item
,
None
)
# 創(chuàng)建一個(gè)新節(jié)點(diǎn)
if
self
.
is_enmpty
(
)
:
# 如果是空鏈表，頭指針直接指向新的節(jié)點(diǎn)
self
.
__head
=
node
else
:
cur
=
self
.
__head
while
(
cur
.
next
)
:
cur
=
cur
.
next
cur
.
next
=
node
def
add
(
self
,
item
)
:
"""鏈表頭部添加元素"""
node
=
Node
(
item
)
# 新建節(jié)點(diǎn)
node
.
next
=
self
.
__head
# 新建結(jié)點(diǎn)指向原來的第一個(gè)節(jié)點(diǎn)
self
.
__head
=
node
# 頭部節(jié)點(diǎn)指向新建的節(jié)點(diǎn)（新的第一個(gè)節(jié)點(diǎn)）
def
insert
(
self
,
pos
,
item
)
:
"""鏈表任意位置添加元素，位置從0開始"""
if
pos
<=
0
:
# 插入的位置小于等于0，則等價(jià)于在鏈表頭部添加元素
self
.
add
(
item
)
elif
pos
>
self
.
length
(
)
-
1
:
# 大于鏈表長度，等價(jià)于在鏈表尾部添加元素
self
.
append
(
item
)
else
:
cur
=
self
.
__head
for
i
in
range
(
pos
-
1
)
:
# 遍歷到插入到位置的前一個(gè)位置
cur
=
cur
.
next
node
=
Node
(
item
)
# 新建一個(gè)節(jié)點(diǎn)
node
.
next
=
cur
.
next
cur
.
next
=
node
def
search
(
self
,
item
)
:
"""查找元素是否在鏈表中，返回布爾值"""
cur
=
self
.
__head
while
(
cur
)
:
if
cur
.
value
==
item
:
return
True
else
:
return
False
def
remove
(
self
,
item
)
:
"""移除第一個(gè)匹配的元素"""
"""單指針，cur.next = cur.next.next"""
"""雙指針，pre.next = cur.next"""
pre
=
None
cur
=
self
.
__head
while
(
cur
)
:
if
cur
.
value
==
item
:
if
cur
==
self
.
__head
:
# 匹配上了第一個(gè)節(jié)點(diǎn)，此時(shí) pre 為空，沒有next，所以單獨(dú)討論
self
.
__head
=
cur
.
next
else
:
pre
.
next
=
cur
.
next
# 刪除節(jié)點(diǎn)
break
# 刪完以后就應(yīng)該退出
else
:
# 向后走一步
pre
=
cur
cur
=
cur
.
next
if
__name__
==
"__main__"
:
ll
=
SingleLinkList
(
)
print
(
"is_empty:"
,
ll
.
is_enmpty
(
)
)
print
(
"length"
,
ll
.
length
(
)
)
ll
.
append
(
1
)
print
(
"is_empty:"
,
ll
.
is_enmpty
(
)
)
print
(
"length"
,
ll
.
length
(
)
)
ll
.
append
(
2
)
ll
.
add
(
8
)
ll
.
append
(
3
)
ll
.
append
(
4
)
ll
.
append
(
5
)
ll
.
append
(
6
)
ll
.
insert
(
-
1
,
9
)
ll
.
insert
(
3
,
100
)
ll
.
insert
(
10
,
200
)
ll
.
travel
(
)
result
=
ll
.
search
(
9
)
print
(
result
)
result
=
ll
.
search
(
300
)
print
(
result
)
ll
.
remove
(
9
)
ll
.
travel
(
)
ll
.
remove
(
200
)
ll
.
travel
(
)
ll
.
remove
(
100
)
ll
.
travel
(
)
output
is_empty
:
True
length
0
is_empty
:
False
length
1
9
8
1
100
2
3
4
5
6
200
True
False
8
1
100
2
3
4
5
6
200
8
1
100
2
3
4
5
6
8
1
2
3
4
5
6
2 Double Link List
圖片來源：https://www.bilibili.com/video/av53583801/?p=23
is_enmpty
、
length
、
travel
、
search
同 Single Link List，完全可以繼承 Single Link List 類！remove 改動(dòng)較大，注意要 remove 的元素是最后一個(gè)節(jié)點(diǎn)的時(shí)候的情況
class
Node
(
object
)
:
def
__init__
(
self
,
value
,
pre
=
None
,
next
=
None
)
:
self
.
value
=
value
self
.
pre
=
pre
self
.
next
=
next
class
DoubleLinkList
(
object
)
:
def
__init__
(
self
,
node
=
None
)
:
self
.
__head
=
node
# 初始化頭指針指向 None
def
is_enmpty
(
self
)
:
# 同 SingleLinkList
"""鏈表是否為空"""
return
self
.
__head
==
None
def
length
(
self
)
:
# 同 SingleLinkList
"""鏈表長度"""
cur
=
self
.
__head
# 頭節(jié)點(diǎn)
count
=
0
while
(
cur
)
:
# 當(dāng)前指針不指向 None 時(shí)候
count
+=
1
cur
=
cur
.
next
return
count
def
travel
(
self
)
:
# 同 SingleLinkList
"""遍歷鏈表"""
cur
=
self
.
__head
# 頭節(jié)點(diǎn),私有變量
while
(
cur
)
:
# 當(dāng)前指針不指向 None 時(shí)候
print
(
cur
.
value
,
end
=
" "
)
cur
=
cur
.
next
print
(
""
)
def
append
(
self
,
item
)
:
"""鏈表尾部添加元素"""
node
=
Node
(
item
,
None
)
# 創(chuàng)建一個(gè)新節(jié)點(diǎn)
if
self
.
is_enmpty
(
)
:
# 如果是空鏈表，頭指針直接指向新的節(jié)點(diǎn)
self
.
__head
=
node
# 注意只有一個(gè)node的話，pre 和 next 都是空，不要以為 pre 是 head
else
:
cur
=
self
.
__head
while
(
cur
.
next
)
:
cur
=
cur
.
next
cur
.
next
=
node
node
.
pre
=
cur
# 相比于 SingleLinkList 新增
def
add
(
self
,
item
)
:
"""鏈表頭部添加元素"""
node
=
Node
(
item
)
# 新建節(jié)點(diǎn)
node
.
next
=
self
.
__head
# 新建結(jié)點(diǎn)指向原來的第一個(gè)節(jié)點(diǎn)
self
.
__head
.
pre
=
node
# 相比于 SingleLinkList 新增
self
.
__head
=
node
# 頭部節(jié)點(diǎn)指向新建的節(jié)點(diǎn)（新的第一個(gè)節(jié)點(diǎn)）
def
insert
(
self
,
pos
,
item
)
:
"""鏈表任意位置添加元素，位置從0開始"""
if
pos
<=
0
:
# 插入的位置小于等于0，則等價(jià)于在鏈表頭部添加元素
self
.
add
(
item
)
elif
pos
>
self
.
length
(
)
-
1
:
# 大于鏈表長度，等價(jià)于在鏈表尾部添加元素
self
.
append
(
item
)
else
:
# 相比與 SingleLinkList
cur
=
self
.
__head
for
i
in
range
(
pos
)
:
# 遍歷到插入的位置
cur
=
cur
.
next
node
=
Node
(
item
)
# 新建一個(gè)節(jié)點(diǎn)
node
.
next
=
cur
# 先讓新建的節(jié)點(diǎn)搭在原來的列表上
node
.
pre
=
cur
.
pre
cur
.
pre
=
node
# 再斷開原有鏈表的鏈接,搭在新建列表上
node
.
pre
.
next
=
node
def
search
(
self
,
item
)
:
# 同 SingleLinkList
"""查找元素是否在鏈表中"""
cur
=
self
.
__head
while
(
cur
)
:
if
cur
.
value
==
item
:
return
True
else
:
return
False
def
remove
(
self
,
item
)
:
"""移除第一個(gè)匹配的元素"""
"""不同于 singleLinkList，這里不需要定義兩個(gè)指針了"""
cur
=
self
.
__head
while
(
cur
)
:
if
cur
.
value
==
item
:
if
cur
==
self
.
__head
:
# 匹配上了第一個(gè)節(jié)點(diǎn)，此時(shí) pre 為空，沒有next，所以單獨(dú)討論
self
.
__head
=
cur
.
next
else
:
cur
.
pre
.
next
=
cur
.
next
# 刪除節(jié)點(diǎn)
if
cur
.
next
:
# 這里判斷是否是最后一個(gè)節(jié)點(diǎn)（最后一個(gè)節(jié)點(diǎn)的next為none，none沒有pre）
cur
.
next
.
pre
=
cur
.
pre
break
# 刪完以后就應(yīng)該退出
else
:
# 向后走一步
if
cur
.
next
:
cur
=
cur
.
next
if
__name__
==
"__main__"
:
ll
=
DoubleLinkList
(
)
print
(
"is_empty:"
,
ll
.
is_enmpty
(
)
)
print
(
"length"
,
ll
.
length
(
)
)
ll
.
append
(
1
)
print
(
"is_empty:"
,
ll
.
is_enmpty
(
)
)
print
(
"length"
,
ll
.
length
(
)
)
ll
.
append
(
2
)
ll
.
add
(
8
)
ll
.
append
(
3
)
ll
.
append
(
4
)
ll
.
append
(
5
)
ll
.
append
(
6
)
ll
.
insert
(
-
1
,
9
)
ll
.
insert
(
3
,
100
)
ll
.
insert
(
10
,
200
)
ll
.
travel
(
)
result
=
ll
.
search
(
9
)
print
(
result
)
result
=
ll
.
search
(
300
)
print
(
result
)
ll
.
remove
(
9
)
ll
.
travel
(
)
ll
.
remove
(
200
)
ll
.
travel
(
)
ll
.
remove
(
100
)
ll
.
travel
(
)
結(jié)果
is_empty
:
True
length
0
is_empty
:
False
length
1
9
8
1
100
2
3
4
5
6
200
True
False
8
1
100
2
3
4
5
6
200
8
1
100
2
3
4
5
6
8
1
2
3
4
5
6
3 Single Cycle Link List
圖片來源：https://www.bilibili.com/video/av53583801/?p=25
Single Cycle Link List 在 Single Link List 的基礎(chǔ)上改動(dòng)還是比較大的，特別是
remove
的時(shí)候。
search
同 Single Link List
class
Node
(
object
)
:
def
__init__
(
self
,
value
,
next
=
None
)
:
self
.
value
=
value
self
.
next
=
next
class
SingleCycleLinkList
(
object
)
:
def
__init__
(
self
,
node
=
None
)
:
self
.
__head
=
node
# 初始化頭指針指向 None
if
node
:
# 新建一個(gè)不為空的循環(huán)鏈表
node
.
next
=
self
.
__head
def
is_enmpty
(
self
)
:
# 同 SingleLinkList
"""鏈表是否為空"""
return
self
.
__head
==
None
def
length
(
self
)
:
"""鏈表長度"""
if
self
.
is_enmpty
(
)
:
return
0
else
:
cur
=
self
.
__head
# 頭節(jié)點(diǎn)
count
=
1
while
(
cur
.
next
!=
self
.
__head
)
:
count
+=
1
cur
=
cur
.
next
return
count
def
travel
(
self
)
:
"""遍歷鏈表"""
if
self
.
is_enmpty
(
)
:
return
0
else
:
cur
=
self
.
__head
# 頭節(jié)點(diǎn),私有變量
while
(
cur
.
next
!=
self
.
__head
)
:
# 當(dāng)前指針不指向 None 時(shí)候
print
(
cur
.
value
,
end
=
" "
)
cur
=
cur
.
next
print
(
cur
.
value
,
end
=
" "
)
# 退出循環(huán)的時(shí)候，cur 指向尾節(jié)點(diǎn)，但尾節(jié)點(diǎn)的元素并沒有打印
print
(
""
)
def
append
(
self
,
item
)
:
"""鏈表尾部添加元素"""
node
=
Node
(
item
,
None
)
# 創(chuàng)建一個(gè)新節(jié)點(diǎn)
if
self
.
is_enmpty
(
)
:
# 如果是空鏈表，頭指針直接指向新的節(jié)點(diǎn)
self
.
__head
=
node
node
.
next
=
node
# 新增節(jié)點(diǎn)自己指向自己形成cycle
else
:
cur
=
self
.
__head
while
(
cur
.
next
!=
self
.
__head
)
:
# 遍歷讓cur指向尾節(jié)點(diǎn)
cur
=
cur
.
next
cur
.
next
=
node
node
.
next
=
self
.
__head
# 形成 cycle
def
add
(
self
,
item
)
:
"""鏈表頭部添加元素"""
node
=
Node
(
item
)
# 新建節(jié)點(diǎn)
if
self
.
is_enmpty
(
)
:
self
.
__head
=
node
# 頭指向新增的節(jié)點(diǎn)
node
.
next
=
node
# 新增節(jié)點(diǎn)自己指向自己形成cycle
else
:
cur
=
self
.
__head
while
(
cur
.
next
!=
self
.
__head
)
:
# 遍歷讓cur指向尾節(jié)點(diǎn)（因?yàn)槭茄h(huán)鏈表，所以尾部要指向新增的頭）
cur
=
cur
.
next
node
.
next
=
self
.
__head
# 新建結(jié)點(diǎn)指向原來的第一個(gè)節(jié)點(diǎn)
self
.
__head
=
node
# 頭部節(jié)點(diǎn)指向新建的節(jié)點(diǎn)（新的第一個(gè)節(jié)點(diǎn)）
cur
.
next
=
node
#相比于 SingleLinkList 新增，尾部指向頭部
def
insert
(
self
,
pos
,
item
)
:
# 同 SingleLinkList
"""鏈表任意位置添加元素，位置從0開始"""
if
pos
<=
0
:
# 插入的位置小于等于0，則等價(jià)于在鏈表頭部添加元素
self
.
add
(
item
)
elif
pos
>
self
.
length
(
)
-
1
:
# 大于鏈表長度，等價(jià)于在鏈表尾部添加元素
self
.
append
(
item
)
else
:
cur
=
self
.
__head
for
i
in
range
(
pos
-
1
)
:
# 遍歷到插入到位置的前一個(gè)位置
cur
=
cur
.
next
node
=
Node
(
item
)
# 新建一個(gè)節(jié)點(diǎn)
node
.
next
=
cur
.
next
cur
.
next
=
node
def
search
(
self
,
item
)
:
"""查找元素是否在鏈表中，返回布爾值"""
if
self
.
is_enmpty
(
)
:
return
False
else
:
cur
=
self
.
__head
while
(
cur
.
next
!=
self
.
__head
)
:
# 遍歷 1-n-1
if
cur
.
value
==
item
:
return
True
else
:
return
False
if
cur
.
value
==
item
:
# 同travel，退出循環(huán)的時(shí)候，cur 指向尾節(jié)點(diǎn)，但尾節(jié)點(diǎn)的元素并沒有遍歷
return
True
else
:
return
False
def
remove
(
self
,
item
)
:
"""移除第一個(gè)匹配的元素"""
if
self
.
is_enmpty
(
)
:
return
else
:
pre
=
None
cur
=
self
.
__head
while
(
cur
.
next
!=
self
.
__head
)
:
if
cur
.
value
==
item
:
### 匹配到了第一個(gè)
if
cur
==
self
.
__head
:
# 匹配上了第一個(gè)節(jié)點(diǎn)，此時(shí) pre 為空，沒有next，所以單獨(dú)討論
end
=
self
.
__head
while
(
end
.
next
!=
self
.
__head
)
:
# 遍歷定位到尾部指針
end
=
end
.
next
self
.
__head
=
self
.
__head
.
next
end
.
next
=
self
.
__head
else
:
### 匹配到了 2-n-1，刪除操作同單鏈表
pre
.
next
=
cur
.
next
# 刪除節(jié)點(diǎn)
return
# 刪完以后就應(yīng)該退出
else
:
# 向后走一步
pre
=
cur
cur
=
cur
.
next
if
cur
.
value
==
item
:
### while 循環(huán)外表示遍歷到了最后一個(gè)節(jié)點(diǎn)（只有一個(gè)節(jié)點(diǎn)/不止一個(gè)節(jié)點(diǎn)），匹配到了第n個(gè)
if
cur
.
next
==
self
.
__head
:
# 這表示匹配的是鏈表中最后一個(gè)節(jié)點(diǎn)
pre
.
next
=
self
.
__head
else
:
#cur == self.__head: # 鏈表只有一個(gè)節(jié)點(diǎn)，此時(shí) pre 為 none，不能用上面的一句話
self
.
__head
=
None
if
__name__
==
"__main__"
:
ll
=
SingleCycleLinkList
(
)
print
(
"is_empty:"
,
ll
.
is_enmpty
(
)
)
print
(
"length"
,
ll
.
length
(
)
)
ll
.
append
(
1
)
print
(
"is_empty:"
,
ll
.
is_enmpty
(
)
)
print
(
"length"
,
ll
.
length
(
)
)
ll
.
append
(
2
)
ll
.
add
(
8
)
ll
.
append
(
3
)
ll
.
append
(
4
)
ll
.
append
(
5
)
ll
.
append
(
6
)
ll
.
insert
(
-
1
,
9
)
ll
.
insert
(
3
,
100
)
ll
.
insert
(
10
,
200
)
ll
.
travel
(
)
result
=
ll
.
search
(
9
)
print
(
result
)
result
=
ll
.
search
(
300
)
print
(
result
)
ll
.
remove
(
9
)
ll
.
travel
(
)
ll
.
remove
(
200
)
ll
.
travel
(
)
ll
.
remove
(
100
)
ll
.
travel
(
)
output
is_empty
:
True
length
0
is_empty
:
False
length
1
9
8
1
100
2
3
4
5
6
200
True
False
8
1
100
2
3
4
5
6
200
8
1
100
2
3
4
5
6
8
1
2
3
4
5
6
4 小結(jié)
Single Link List 是情況最簡單的，在這個(gè)的基礎(chǔ)上，我們改進(jìn)實(shí)現(xiàn)了 Double Link List 和 Single Cycle Link List，三種鏈表的測試樣例是一樣的，所以如果 coding 沒有問題的話，結(jié)果是一樣的！
主要實(shí)現(xiàn)了如下功能：
-
is_empty()：是否為空 -
length()：鏈表的長度 -
traval()：遍歷鏈表，打印出來 -
search(item)：查找元素是否在鏈表中，返回 boolean 值 -
add(item)：在鏈表的第一個(gè)位置添加元素 -
append(item)：在鏈表的最后一個(gè)位置添加元素 -
insert(pos,item)：在鏈表的指定位置插入元素 -
remove(item)：刪除掉匹配到的第一個(gè)元素
在 coding 的時(shí)候一定要注意以下的邊界情況是否要單獨(dú)討論：
- 鏈表為空
- 鏈表只有一個(gè)元素
- 要對鏈表的第一個(gè)元素進(jìn)行操作
- 要對鏈表的最后一個(gè)元素進(jìn)行操作
然后插入的時(shí)候，最好不要先動(dòng)原來的鏈表，先讓新節(jié)點(diǎn)搭上去，然后再改原來的鏈表。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
