https://www.bilibili.com/video/av53583801/?p=20
学习笔记
文章目录
- 1 Single Link List
- 2 Double Link List
- 3 Single Cycle Link List
- 4 小结
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
# 头节点
count
=
0
while
(
cur
)
:
# 当前指针不指向 None 时候
count
+=
1
cur
=
cur
.
next
return
count
def
travel
(
self
)
:
"""遍历链表"""
cur
=
self
.
__head
# 头节点,私有变量
while
(
cur
)
:
# 当前指针不指向 None 时候
print
(
cur
.
value
,
end
=
" "
)
cur
=
cur
.
next
print
(
""
)
def
append
(
self
,
item
)
:
"""链表尾部添加元素"""
node
=
Node
(
item
,
None
)
# 创建一个新节点
if
self
.
is_enmpty
(
)
:
# 如果是空链表，头指针直接指向新的节点
self
.
__head
=
node
else
:
cur
=
self
.
__head
while
(
cur
.
next
)
:
cur
=
cur
.
next
cur
.
next
=
node
def
add
(
self
,
item
)
:
"""链表头部添加元素"""
node
=
Node
(
item
)
# 新建节点
node
.
next
=
self
.
__head
# 新建结点指向原来的第一个节点
self
.
__head
=
node
# 头部节点指向新建的节点（新的第一个节点）
def
insert
(
self
,
pos
,
item
)
:
"""链表任意位置添加元素，位置从0开始"""
if
pos
<=
0
:
# 插入的位置小于等于0，则等价于在链表头部添加元素
self
.
add
(
item
)
elif
pos
>
self
.
length
(
)
-
1
:
# 大于链表长度，等价于在链表尾部添加元素
self
.
append
(
item
)
else
:
cur
=
self
.
__head
for
i
in
range
(
pos
-
1
)
:
# 遍历到插入到位置的前一个位置
cur
=
cur
.
next
node
=
Node
(
item
)
# 新建一个节点
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
)
:
"""移除第一个匹配的元素"""
"""单指针，cur.next = cur.next.next"""
"""双指针，pre.next = cur.next"""
pre
=
None
cur
=
self
.
__head
while
(
cur
)
:
if
cur
.
value
==
item
:
if
cur
==
self
.
__head
:
# 匹配上了第一个节点，此时 pre 为空，没有next，所以单独讨论
self
.
__head
=
cur
.
next
else
:
pre
.
next
=
cur
.
next
# 删除节点
break
# 删完以后就应该退出
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 改动较大，注意要 remove 的元素是最后一个节点的时候的情况
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
# 头节点
count
=
0
while
(
cur
)
:
# 当前指针不指向 None 时候
count
+=
1
cur
=
cur
.
next
return
count
def
travel
(
self
)
:
# 同 SingleLinkList
"""遍历链表"""
cur
=
self
.
__head
# 头节点,私有变量
while
(
cur
)
:
# 当前指针不指向 None 时候
print
(
cur
.
value
,
end
=
" "
)
cur
=
cur
.
next
print
(
""
)
def
append
(
self
,
item
)
:
"""链表尾部添加元素"""
node
=
Node
(
item
,
None
)
# 创建一个新节点
if
self
.
is_enmpty
(
)
:
# 如果是空链表，头指针直接指向新的节点
self
.
__head
=
node
# 注意只有一个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
)
# 新建节点
node
.
next
=
self
.
__head
# 新建结点指向原来的第一个节点
self
.
__head
.
pre
=
node
# 相比于 SingleLinkList 新增
self
.
__head
=
node
# 头部节点指向新建的节点（新的第一个节点）
def
insert
(
self
,
pos
,
item
)
:
"""链表任意位置添加元素，位置从0开始"""
if
pos
<=
0
:
# 插入的位置小于等于0，则等价于在链表头部添加元素
self
.
add
(
item
)
elif
pos
>
self
.
length
(
)
-
1
:
# 大于链表长度，等价于在链表尾部添加元素
self
.
append
(
item
)
else
:
# 相比与 SingleLinkList
cur
=
self
.
__head
for
i
in
range
(
pos
)
:
# 遍历到插入的位置
cur
=
cur
.
next
node
=
Node
(
item
)
# 新建一个节点
node
.
next
=
cur
# 先让新建的节点搭在原来的列表上
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
)
:
"""移除第一个匹配的元素"""
"""不同于 singleLinkList，这里不需要定义两个指针了"""
cur
=
self
.
__head
while
(
cur
)
:
if
cur
.
value
==
item
:
if
cur
==
self
.
__head
:
# 匹配上了第一个节点，此时 pre 为空，没有next，所以单独讨论
self
.
__head
=
cur
.
next
else
:
cur
.
pre
.
next
=
cur
.
next
# 删除节点
if
cur
.
next
:
# 这里判断是否是最后一个节点（最后一个节点的next为none，none没有pre）
cur
.
next
.
pre
=
cur
.
pre
break
# 删完以后就应该退出
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
(
)
结果
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 的基础上改动还是比较大的，特别是
remove
的时候。
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
:
# 新建一个不为空的循环链表
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
# 头节点
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
# 头节点,私有变量
while
(
cur
.
next
!=
self
.
__head
)
:
# 当前指针不指向 None 时候
print
(
cur
.
value
,
end
=
" "
)
cur
=
cur
.
next
print
(
cur
.
value
,
end
=
" "
)
# 退出循环的时候，cur 指向尾节点，但尾节点的元素并没有打印
print
(
""
)
def
append
(
self
,
item
)
:
"""链表尾部添加元素"""
node
=
Node
(
item
,
None
)
# 创建一个新节点
if
self
.
is_enmpty
(
)
:
# 如果是空链表，头指针直接指向新的节点
self
.
__head
=
node
node
.
next
=
node
# 新增节点自己指向自己形成cycle
else
:
cur
=
self
.
__head
while
(
cur
.
next
!=
self
.
__head
)
:
# 遍历让cur指向尾节点
cur
=
cur
.
next
cur
.
next
=
node
node
.
next
=
self
.
__head
# 形成 cycle
def
add
(
self
,
item
)
:
"""链表头部添加元素"""
node
=
Node
(
item
)
# 新建节点
if
self
.
is_enmpty
(
)
:
self
.
__head
=
node
# 头指向新增的节点
node
.
next
=
node
# 新增节点自己指向自己形成cycle
else
:
cur
=
self
.
__head
while
(
cur
.
next
!=
self
.
__head
)
:
# 遍历让cur指向尾节点（因为是循环链表，所以尾部要指向新增的头）
cur
=
cur
.
next
node
.
next
=
self
.
__head
# 新建结点指向原来的第一个节点
self
.
__head
=
node
# 头部节点指向新建的节点（新的第一个节点）
cur
.
next
=
node
#相比于 SingleLinkList 新增，尾部指向头部
def
insert
(
self
,
pos
,
item
)
:
# 同 SingleLinkList
"""链表任意位置添加元素，位置从0开始"""
if
pos
<=
0
:
# 插入的位置小于等于0，则等价于在链表头部添加元素
self
.
add
(
item
)
elif
pos
>
self
.
length
(
)
-
1
:
# 大于链表长度，等价于在链表尾部添加元素
self
.
append
(
item
)
else
:
cur
=
self
.
__head
for
i
in
range
(
pos
-
1
)
:
# 遍历到插入到位置的前一个位置
cur
=
cur
.
next
node
=
Node
(
item
)
# 新建一个节点
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，退出循环的时候，cur 指向尾节点，但尾节点的元素并没有遍历
return
True
else
:
return
False
def
remove
(
self
,
item
)
:
"""移除第一个匹配的元素"""
if
self
.
is_enmpty
(
)
:
return
else
:
pre
=
None
cur
=
self
.
__head
while
(
cur
.
next
!=
self
.
__head
)
:
if
cur
.
value
==
item
:
### 匹配到了第一个
if
cur
==
self
.
__head
:
# 匹配上了第一个节点，此时 pre 为空，没有next，所以单独讨论
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
# 删除节点
return
# 删完以后就应该退出
else
:
# 向后走一步
pre
=
cur
cur
=
cur
.
next
if
cur
.
value
==
item
:
### while 循环外表示遍历到了最后一个节点（只有一个节点/不止一个节点），匹配到了第n个
if
cur
.
next
==
self
.
__head
:
# 这表示匹配的是链表中最后一个节点
pre
.
next
=
self
.
__head
else
:
#cur == self.__head: # 链表只有一个节点，此时 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 小结
Single Link List 是情况最简单的，在这个的基础上，我们改进实现了 Double Link List 和 Single Cycle Link List，三种链表的测试样例是一样的，所以如果 coding 没有问题的话，结果是一样的！
主要实现了如下功能：
-
is_empty()：是否为空 -
length()：链表的长度 -
traval()：遍历链表，打印出来 -
search(item)：查找元素是否在链表中，返回 boolean 值 -
add(item)：在链表的第一个位置添加元素 -
append(item)：在链表的最后一个位置添加元素 -
insert(pos,item)：在链表的指定位置插入元素 -
remove(item)：删除掉匹配到的第一个元素
在 coding 的时候一定要注意以下的边界情况是否要单独讨论：
- 链表为空
- 链表只有一个元素
- 要对链表的第一个元素进行操作
- 要对链表的最后一个元素进行操作
然后插入的时候，最好不要先动原来的链表，先让新节点搭上去，然后再改原来的链表。
