概念
鏈表(linked_list)是物理存盤單元上非連續的、非順序的存盤結構，資料元素的邏輯順序
是通過鏈表的指標地址實作，每個元素包含兩個結點，一個是存盤元素的資料域 (記憶體空間)
，另一個是指向下一個結點地址的指標域，根據指標的指向，鏈表能形成不同的結構，例如
單鏈表，雙向鏈表，回圈鏈表等.
鏈表通過將鏈點 i 與其鄰居鏈點 i+1 通過指標相關聯，從索引 0 到索引 N-1 對鏈點進
行排序.
實作
class Node:
"""
鏈點
"""
def __init__(self, data):
self.data = https://www.cnblogs.com/thunderLL/p/data # 資料域
self.next = None # 指標域
class SingleLinkedList:"""
單鏈表
"""
def __init__(self, head=None):
self.head = Node(head) # 鏈表頭部元素
self._length = None
# 向鏈表中添加新鏈點
def append(self, value):
self._length = None
new_node = Node(value)
# 將頭部節點指向臨時變數
current = self.head
# 當頭部節點存在時
if self.head:
# 回圈遍歷到鏈表的最后一個節點
while current.next:
current = current.next
current.next = new_node
# 當頭部節點不存在時
else:
self.head = new_node
# 判斷鏈表是否為空
def is_empty(self):
return bool(self.head)
# 向鏈表任意位置插入元素
def insert(self, position, value):
self._length = None
new_node = Node(value)
# 判斷插入位置是否在鏈表的索引范圍內
if position < 0 or position > self.get_length():
raise IndexError('Out of linked list range.')
# 當插入位置為頭節點時
if position == 0:
new_node.next, self.head = self.head, new_node
return
# 當插入位置不在頭節點時,遍歷鏈表找到插入位置,插入新節點
current = self.head
i = 0
while i < position:
pre, current = current, current.next
i += 1
pre.next, new_node.next = new_node, current
# 洗掉指定位置的節點
def remove(self, position):
self._length = None
# 判斷洗掉位置是否在鏈表的索引范圍內
if position < 0 or position > self.get_length() - 1:
raise IndexError('Position out of linked list range.')
i = 0
current = self.head
# 當洗掉位置為頭節點時
if position == i:
self.head, current.next = self.head.next, None
return
# 當洗掉位置不是頭節點時,遍歷鏈表找到洗掉位置
i += 1
prev, current = current, current.next
while i != position:
prev, current = current, current.next
i += 1
prev.next, current.next = current.next, None
# 獲取鏈表長度
def get_length(self):
if self._length is not None:
return self._length
current = self.head
length = 0
while current is not None:
length += 1
current = current.next
self._length = length
return length
# 遍歷鏈表,并依次列印節點資料
def print_list(self):
print('linked_list:')
current = self.head
while current is not None:
print(current.data)
current = current.next
# 將鏈表反轉
def reverse(self):
prev = None
current = self.head
while current is not None:
# next_node = current.next
# current.next = prev
# prev = current
# current = next_node
next_node, current.next = current.next, prev
prev, current = current, next_node
self.head = prev
# 將串列轉換為鏈表
def init_list(self, data_list):
self.head = Node(data_list[0])
current = self.head
for item in data_list[1:]:
node = Node(item)
current.next, current = node, node
# 替換指定位置的節點
def replace(self, position, value):
# 判斷替換位置是否在鏈表索引范圍內
if position < 0 or position > self.get_length() - 1:
raise IndexError("Position out of linked-list range.")
_node = Node(value)
_current = self.head
i = 0
if position == 0:
_node.next, self.head = self.head.next, _node
_current.next = None
else:
i += 1
_prev, _current = _current, _current.next
while i != position:
i += 1
_prev, _current = _current, _current.next
_prev.next, _node.next = _node, _current.next
_current.next = None
# 回傳給定值的第一個節點索引
def index(self, value):
_current = self.head
i = 0
while _current is not None:
if _current.data =https://www.cnblogs.com/thunderLL/p/= value:
return i
i += 1
_current = _current.next
return -1
def __getitem__(self, position):
if position < 0 or position > self.get_length() - 1:
raise IndexError("Position out of linked-list range.")
_current = self.head
i = 0
while i != position:
_current = _current.next
i += 1
return _current.data
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/116908.html
標籤：其他
上一篇：二分查找（Java）