鏈表是線性表的一種實(shí)現(xiàn)方式，它的基本想法是：
- 將表中的元素分別存放在各個(gè)獨(dú)立的存儲(chǔ)區(qū)內(nèi)飞蛹，存儲(chǔ)區(qū)又稱為結(jié)點(diǎn)谤狡；
- 在表中，可以通過(guò)任意結(jié)點(diǎn)找到與之相關(guān)的下一個(gè)結(jié)點(diǎn)桩皿；
- 在前一個(gè)結(jié)點(diǎn)上豌汇，通過(guò)鏈接的方式記錄與下一個(gè)結(jié)點(diǎn)的關(guān)聯(lián)。
當(dāng)找到組成表結(jié)構(gòu)的第一個(gè)結(jié)點(diǎn)時(shí)泄隔，就能按照順序找到屬于這個(gè)表的其它結(jié)點(diǎn)。
單鏈表
單鏈表
如上圖(a)所示宛徊，單鏈表的結(jié)點(diǎn)是一個(gè)二元組佛嬉，elem保存元素的數(shù)據(jù)，next表示下一個(gè)結(jié)點(diǎn)的標(biāo)識(shí)闸天。
為了掌握一個(gè)單鏈表暖呕，需要用一個(gè)變量來(lái)保存這個(gè)表的首結(jié)點(diǎn)的引用（或標(biāo)識(shí)），該變量可以稱之為表頭變量或表頭指針
基本鏈表操作
- 創(chuàng)建空鏈表
- 刪除鏈表
- 判斷鏈表是否為空
- 加入元素
- 首端加入
- 尾端加入
- 中間加入
- 刪除元素
- 首端刪除
- 尾端刪除
- 中間刪除
- 遍歷鏈表
- 查找元素
代碼實(shí)現(xiàn)苞氮，里面實(shí)現(xiàn)幾個(gè)典型方法
class Node:
"""結(jié)點(diǎn)"""
def __init__(self, elem):
self.elem = elem
self.next = None
class SingleLinkList:
"""單鏈表"""
def __init__(self):
self._head = None
def is_empty(self):
"""鏈表是否為空"""
return self._head == None
def length(self):
"""鏈表長(zhǎng)度"""
# cur游標(biāo)湾揽，用來(lái)移動(dòng)遍歷結(jié)點(diǎn)
cur = self._head
# count記錄數(shù)量
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍歷整個(gè)鏈表"""
cur = self._head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next
print("")
def add(self, item):
"""鏈表頭部添加元素，頭插法"""
node = Node(item)
node.next = self._head
self._head = node
def append(self, item):
"""鏈表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self._head = node
else:
cur = self._head
while cur.next != None:
cur = cur.next
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素
:param pos 從0開(kāi)始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self._head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 當(dāng)循環(huán)退出后笼吟，pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
"""刪除結(jié)點(diǎn)"""
cur = self._head
pre = None
while cur != None:
if cur.elem == item:
# 先判斷此結(jié)點(diǎn)是否是頭結(jié)點(diǎn)
# 頭結(jié)點(diǎn)
if cur == self._head:
self._head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
def search(self, item):
"""查找結(jié)點(diǎn)是否存在"""
cur = self._head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
通過(guò)上面的代碼库物，可以說(shuō)明一下單鏈表的操作復(fù)雜度：
- 創(chuàng)建空鏈表：O(1)
- 判斷鏈表是否為空：O(1)
- 鏈表長(zhǎng)度：O(n)
- 加入元素：
- 首端加入：O(1)
- 尾端加入：O(n)
- 中間加入：O(n)
- 刪除元素：
- 首端刪除：O(1)
- 尾端刪除：O(n)
- 中間刪除：O(n)
- 遍歷，查找：O(n)
上面的單鏈表實(shí)現(xiàn)有個(gè)缺點(diǎn)贷帮，在尾端操作元素的效率低戚揭，只能從表頭開(kāi)始遍歷到尾部。
在實(shí)際中撵枢，會(huì)添加一個(gè)尾部結(jié)點(diǎn)的引用民晒，這樣在尾部添加精居，刪除元素測(cè)復(fù)雜度就降為O(1)。
循環(huán)單鏈表
循環(huán)單鏈表
單鏈表的一種變形是循環(huán)單鏈表潜必，它的最后一個(gè)結(jié)點(diǎn)的next不指向None靴姿，而是指向首結(jié)點(diǎn)的位置，如上圖所示磁滚。
代碼實(shí)現(xiàn)佛吓，部分和單鏈表類似
class SingleCycleLinkList:
"""單向循環(huán)鏈表"""
def __init__(self):
self._head = None
def add(self, item):
"""鏈表頭部添加元素，頭插法"""
node = Node(item)
if self.is_empty():
self._head = node
node.next = node
else:
cur = self._head
while cur.next != self._head:
cur = cur.next
# 退出循環(huán)恨旱，cur指向尾結(jié)點(diǎn)
node.next = self._head
self._head = node
# cur.next = node
cur.next = self._head
def append(self, item):
"""鏈表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self._head = node
node.next = node
else:
cur = self._head
while cur.next != self._head:
cur = cur.next
# node.next = cur.next
node.next = self._head
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素
:param pos 從0開(kāi)始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self._head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 當(dāng)循環(huán)退出后辈毯，pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
"""刪除結(jié)點(diǎn)"""
if self.is_empty():
return
cur = self._head
pre = None
while cur.next != self._head:
if cur.elem == item:
# 先判斷此結(jié)點(diǎn)是否是頭結(jié)點(diǎn)
if cur == self._head:
# 頭結(jié)點(diǎn)的情況
# 找尾結(jié)點(diǎn)
rear = self._head
while rear.next != self._head:
rear = rear.next
self._head = cur.next
rear.next = self._head
else:
# 中間結(jié)點(diǎn)
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
# 退出循環(huán)，cur指向尾結(jié)點(diǎn)
if cur.elem == item:
if cur == self._head:
# 鏈表只有一個(gè)結(jié)點(diǎn)
self._head = None
else:
# pre.next = cur.next
pre.next = self._head
其它的方法和單鏈表一樣搜贤。
同樣的谆沃，可以添加一個(gè)尾部結(jié)點(diǎn)的引用，使得運(yùn)算量下降仪芒。
雙向鏈表
帶有尾結(jié)點(diǎn)引用的雙向鏈表
單鏈表只有一個(gè)方向的鏈接唁影，從一個(gè)方向進(jìn)行鏈表的遍歷。為了是從兩端的插入和刪除操作都能高效完成掂名，可以加入另一個(gè)方向的鏈接据沈。如上圖所示，就形成了雙向鏈表饺蔑，或雙鏈表
雙向鏈表的結(jié)點(diǎn)除了next引用锌介，還需要一個(gè)prev引用：
class Node(object):
"""結(jié)點(diǎn)"""
def __init__(self, item):
self.elem = item
self.next = None
self.prev = None
雙向鏈表的一些操作要做一些修改：
class DoubleLinkList(object):
"""雙鏈表"""
def __init__(self):
self._head = None
self._rear = None
def add(self, item):
"""鏈表頭部添加元素，頭插法"""
node = Node(item)
if self.is_empty():
self._rear = node
node.next = self._head
self._head = node
node.next.prev = node
def append(self, item):
"""鏈表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self._head = node
else:
cur = self._head
while cur.next != None:
cur = cur.next
cur.next = node
node.prev = cur
self._rear = node
def insert(self, pos, item):
"""指定位置添加元素
:param pos 從0開(kāi)始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
cur = self._head
count = 0
while count < pos:
count += 1
cur = cur.next
# 當(dāng)循環(huán)退出后猾警，cur指向pos位置
node = Node(item)
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
def remove(self, item):
"""刪除節(jié)點(diǎn)"""
cur = self._head
while cur != None:
if cur.elem == item:
# 先判斷此結(jié)點(diǎn)是否是頭節(jié)點(diǎn)
# 頭節(jié)點(diǎn)
if cur == self._head:
self._head = cur.next
if cur.next:
# 判斷鏈表是否只有一個(gè)結(jié)點(diǎn)
cur.next.prev = None
else:
self._rear = None
else:
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
else:
self._rear = cur.prev
break
else:
cur = cur.next
總結(jié)
鏈接表的優(yōu)點(diǎn)：
- 由于表結(jié)構(gòu)是由鏈接起來(lái)的結(jié)點(diǎn)形成孔祸，表結(jié)構(gòu)很容易修改；
- 整個(gè)表由一些小的存儲(chǔ)塊構(gòu)成发皿，比較容易安排和管理崔慧，不需要連續(xù)的內(nèi)存塊。
缺點(diǎn)：
- 鏈表元素的定位需要線性的時(shí)間穴墅，比列表效率底惶室；
- 鏈表的存儲(chǔ)代價(jià)會(huì)比列表高。
轉(zhuǎn)載自：
https://codeeper.com/2020/03/30/tech/python/structure/link-intro.html
