- 鏈表
- python實現(xiàn)鏈表
- 鏈表的初始化
- 創(chuàng)建
- 元素的插入和刪除
- 鏈表的遍歷
- 元素的查詢
- 鏈表的刪除
- 鏈表的逆序
- 判斷鏈表是否有環(huán)等
鏈表
鏈表是一種常見的基礎數(shù)據(jù)結構权她，結構體指針在這里得到了充分的利用随抠。鏈表可以動態(tài)的進行存儲分配篱蝇，也就是說捂掰，鏈表是一個功能極為強大的數(shù)組扫责，他可以在節(jié)點中定義多種數(shù)據(jù)類型请契，還可以根據(jù)需要隨意增添锅风，刪除脖镀，插入節(jié)點飒箭。
鏈表的基本結構
鏈表是通過一個個節(jié)點（Node）組成的，每個節(jié)點都包含了稱為數(shù)據(jù)域（value）和指針域（next）的基本單元蜒灰，它也是一種遞歸的數(shù)據(jù)結構弦蹂。它能保持數(shù)據(jù)之間的邏輯順序，但存儲空間不必按照順序存儲强窖。
鏈表的基本元素
- Node(節(jié)點)：節(jié)點包括兩個部分凸椿，左邊為值域（存放用戶數(shù)據(jù)），右邊為指針域（存放指向下一個元素的指針）
- head：指向第一個節(jié)點
- tail：指向最后一個節(jié)點
- None：鏈表的最后一個節(jié)點的指針域為None值
python實現(xiàn)鏈表
由于python是動態(tài)語言翅溺，沒有固定類型脑漫，可以直接把對象賦值給新的變量，所以在python上一切皆為對象的原理實現(xiàn)鏈表的操作
- 實現(xiàn)一個簡單的單向鏈表
步驟：- 創(chuàng)建Node（節(jié)點）類
- 值域：存放數(shù)據(jù)
- 指針域：存放指向下一個元素的指針
- 創(chuàng)建一個單鏈表結構
- 初始化鏈表
- 檢測是否為空鏈表
- head
- tail
- 創(chuàng)建Node（節(jié)點）類
- python實現(xiàn)
- 創(chuàng)建一個節(jié)點類并測試
'''
新建單鏈表Node節(jié)點類
'''
'''
新建單鏈表Node節(jié)點類
'''
class Node():
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def get_value(self):
return self.value
def get_next(self):
return self.next
def set_value(self, value):
self.value = value
def set_next(self, next):
self.next = next
head = None
for i in range(1, 6):
head = Node(i,head)
while head != None:
print(head.value) # 輸出：5,4,3,2,1,
head = head.next
此時鏈表結構為：
- 單鏈表結構
其中包括：
- 初始化鏈表
- 判斷鏈表是否為空
- 插入節(jié)點
鏈表末尾插入節(jié)點
- 判斷是否為空鏈表
- 空鏈表則頭結點指向該節(jié)點咙崎，length加一
- 非空鏈表則插入節(jié)點到最后一個优幸，length加一
- 鏈表長度
- 刪除節(jié)點
- 判斷鏈表是否為空
- 判斷刪除的是否為頭結點
- 判斷刪除的長度是都合法
- 找到要刪除的節(jié)點的前一個節(jié)點，然后將該節(jié)點的下一個指針指向要刪除的節(jié)點的下一個節(jié)點
- 刪除節(jié)點后length減一
- 修改節(jié)點
- 判斷鏈表是否為空
- 判斷index是否合法
- 找到待修改節(jié)點褪猛，修改其value值
- 查找鏈表
- 判斷鏈表是否為空
- 遍歷鏈表查找節(jié)點是否存在
'''
新建一個鏈表類
'''
class LinkList():
def __init__(self):
# 初始化鏈表頭結點以及鏈表的長度
self.head = Node()
self.length = 0
def isEmpty(self):
return self.length == 0
def append(self, value):
'''
鏈表末尾插入節(jié)點
* 判斷是否為空鏈表
* 空鏈表則頭結點指向該節(jié)點网杆，length加一
* 非空鏈表則插入節(jié)點到最后一個，length加一
'''
node = Node(value)
if self.length == 0:
self.head.next = node
self.length += 1
else:
tempNode = self.head.next
while tempNode.next:
tempNode = tempNode.next
tempNode.next = node
self.length += 1
def len(self):
return self.length
def remove(self, index):
'''
* 判斷鏈表是否為空
* 判斷刪除的是否為頭結點
* 判斷刪除的長度是否合法
* 找到要刪除的節(jié)點的前一個節(jié)點伊滋，然后將該節(jié)點的下一個指針指向要刪除的節(jié)點的下一個節(jié)點
* 刪除節(jié)點后length減一
'''
if self.isEmpty():
print('Error LinkList Length...')
elif (index <= 0 or index > self.length):
print('Error Length...')
elif index == 1:
p = self.head.next
self.head = p
self.length -= 1
else:
p = self.head.next
for i in range(2, index):
p = p.next
q = p.next
p.next = q.next
self.length -= 1
def update(self, index, value):
'''
* 判斷鏈表是否為空
* 判斷index是否合法
* 找到待修改節(jié)點碳却，修改其value值
'''
if self.isEmpty():
print('This LinkList Is Empty...')
elif (index <= 0 or index > self.length):
print('Error Length...')
else:
p = self.head.next
for i in range(1, index):
p = p.next
p.value = value
def search(self, value):
'''
* 判斷鏈表是否為空
* 遍歷鏈表查找節(jié)點是否存在
'''
if self.isEmpty():
print('This LinkList Is Empty...')
else:
p = self.head.next
for i in range(1, self.length + 1):
if p.value == value:
print('Search Success!')
break
elif i == self.length and p.value != value:
print('Search Faild!')
else:
p = p.next
