鏈表

基本概念

鏈表是由一系列節(jié)點(diǎn)組成的元素集合。

每個(gè)節(jié)點(diǎn)包含兩部分：數(shù)據(jù)域 item 、指向下一個(gè)節(jié)點(diǎn)的指針 next

通過(guò)節(jié)點(diǎn)之間的相互鏈接，形成一個(gè)鏈表

1. 鏈表的初始化

# 手動(dòng)建立鏈表
# 鏈表的初始化
class Node(object):def __init__(self, item):self.item = itemself.next = next# 手動(dòng)添加鏈表中的數(shù)據(jù)
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
# 將節(jié)點(diǎn)之間鏈接起來(lái)
a.next = b
b.next = c
c.next = d
# 可通過(guò)指針輸出想要的數(shù)據(jù)
print(a)  # 1
print(a.next)  # 2
print(a.next.next)  # 3
print(a.next.next.next)  # 4 

手動(dòng)添加數(shù)據(jù)的方式我們不怎么用，有專門的創(chuàng)建鏈表的方法 ，手動(dòng)創(chuàng)建我們只需知道了解即可。

2.創(chuàng)建鏈表

(1).頭插法

先把新的節(jié)點(diǎn)連到頭節(jié)點(diǎn)（head）前面

?再把頭節(jié)點(diǎn)head挪到這個(gè)新的元素上

代碼實(shí)現(xiàn)

def creat_linklist_head(li):head = Node(li[0])   # 將列表中的第一個(gè)元素設(shè)為頭節(jié)點(diǎn)for element in li[1:]:   # 循環(huán)遍歷鏈表node = Node(element)  # 將鏈表中的元素設(shè)置為一個(gè)節(jié)點(diǎn)node.next = head   # 將元素直接插到頭節(jié)點(diǎn)的前面head = node   # 再將頭節(jié)點(diǎn)直接挪到前面return head   # 返回頭節(jié)點(diǎn)

(2).尾插法?

?將尾指針指向下一個(gè)元素。

?再把尾指針先后挪。

代碼實(shí)現(xiàn)

def creat_linklist_tail(li):head = Node(li[0])  # 將列表中的第一個(gè)元素設(shè)為頭節(jié)點(diǎn)tail = head  # 當(dāng)一開(kāi)始只有一個(gè)節(jié)點(diǎn)的時(shí)候，頭節(jié)點(diǎn)和尾節(jié)點(diǎn)是同一個(gè)for element in li[1:]:  # 循環(huán)遍歷列表讀取數(shù)據(jù)node = Node(element)   # 將列表中的元素設(shè)置為一個(gè)節(jié)點(diǎn)tail.next = node  # 將尾指針指向新添加的元素tail = node  # 尾指針向后移，移到最后一個(gè)元素上return head  # 返回頭節(jié)點(diǎn)

3.遍歷鏈表

當(dāng)鏈表不為空時(shí)，直接循環(huán)打印當(dāng)前元素，并不斷指向下一個(gè)。

def print_linklist(lk):while lk:print(lk.item, end=" ")lk = lk.next# 集合尾插法進(jìn)行測(cè)試
lk = creat_linklist_tail([1,2,3,4])
print_linklist(lk)

運(yùn)行后可以正常給出遍歷結(jié)果，但是我不理解他為什么會(huì)報(bào)錯(cuò)，我跟著視頻中教程敲得代碼，人家沒(méi)報(bào)錯(cuò)為什么我的報(bào)錯(cuò)。等我研究研究。