當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

列表的实现与应用

發布時間：2025/10/17 编程问答 4 豆豆

生活随笔收集整理的這篇文章主要介紹了列表的实现与应用小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

抽象數據結構list

python內置實現了list;但list是一種通用數據結構，類似于c++中的vector
下面使用鏈表來實現list;python內置list使用數組（array.Array模塊）來實現

list的數據結構和操作方法如下：

一、實現（基于鏈表）

由于實現方式不同，該實現方式的各種操作時間復雜度不同于內置list

方法1：內置list(基于數組實現)
方法2：基于鏈表

1.1 無序list

class Node():"""鏈表中的節點，包括數據域和指針域；使用單鏈表實現"""def __init__(self, data):self.data = dataself.next = Nonedef get_data(self):return self.datadef set_next(self, next_node):#python內變量為引用類型，可視作指針self.next = next_nodedef get_next(self):return self.nextclass UnOrderedList():"""無序列表的實現"""def __init__(self):"""構造函數創建一個空list空的單鏈表等價于頭部為空；根據頭部可以遍歷出所有所有鏈表信息故list只存儲頭部節點即可"""#頭部節點初始為Noneself.head = Nonedef add(self, item):"""在鏈表head添加元素"""temp_node = Node(item)temp_node.set_next(self.head)self.head = temp_nodedef isEmpty(self):return self.head == Nonedef size(self):#排除特殊情況count = 0node = self.headwhile node != None:count += 1node = node.get_next()return countdef search(self, item):found = Falsecurrent = self.headwhile current != None and not found:if current.get_data() == item:#found相當于指示器，相當于breakfound = Trueelse:current = current.get_next()return founddef remove(self, item):"""1、找到則刪除，未找到不做任何操作2、刪除節點關鍵是定位相鄰節點；左節點可以用previous表示，右節點用current.get_next()表示3、所以兩個變量previous與current至關重要4、刪除頭結點要分類討論"""found = Falsecurrent = self.headprevious = Nonewhile current != None and not found:if current.get_data() == item:#found相當于指示器，相當于breakfound = True#previous為None:刪除頭結點if previous == None:self.head = current.get_next()else:previous.set_next(current.get_next())else:previous = currentcurrent = current.get_next()def append(self, item):"""追加操作，鏈表首都append需要分類討論"""current = self.headif current == None:self.head = Node(item)else:current = self.head#尋找鏈表最后一個元素while current.get_next() is not None:current = current.get_next() current.set_next(Node(item))def insert(self, pos, item):"""插入操作，鏈表首都append需要分類討論"""if pos == 0:inserted_node = Node(item)inserted_node.set_next(self.head)self.head = inserted_nodeelif 0 < pos <=self.size() :#找到pos位置對應的當前元素current與前置元素previouscurrent = self.headprevious = Nonecount = 0while count < pos:previous = currentcurrent = current.get_next()count += 1inserted_node = Node(item)inserted_node.set_next(current)previous.set_next(inserted_node)def index(self, item):myindex = 0current = self.headif self.size():#非空執行操作，空list不做任何操作count = 0while current.get_data() != item:count += 1current = current.get_next()return countdef pop(self, pos=None):"""pop操作，鏈表首都pop需要分類討論"""#對于缺省值的處理if pos is None:pos = self.size() - 1 if pos == 0:self.head = self.head.get_next()return self.headelif 0 < pos < self.size():current = self.headprevious = Nonecount = 0while count != pos:previous = currentcurrent = current.get_next()count += 1previous.set_next(current.get_next())return currentif __name__ == '__main__':mylist = UnOrderedList()mylist.add(31)mylist.add(77)mylist.add(17)mylist.add(93)mylist.add(26)mylist.add(54)print(mylist.size())print(mylist.search(93))print(mylist.search(100))mylist.add(100)print(mylist.search(100))print(mylist.size())print('*'*50)mylist.remove(54)print(mylist.size())mylist.remove(93)print(mylist.size())mylist.remove(31)print(mylist.size())mylist.remove(11)print(mylist.size())print(mylist.search(93))print(mylist.append(66))print(mylist.size())print(mylist.pop(0))print(mylist.pop())print(mylist.index(17))print(mylist.insert(0, 333))print(mylist.insert(1, 444))print(mylist.index(333))print(mylist.index(444))

用單向鏈表實現的list各操作復雜度為：

append O(n)
pop O(n)
pop(k) O(k)
add O(1)
isEmpty O(1)
size O(n)
index O(n)
insert(k) O(k)
remove O(n)

對比使用數組實現的內置list,有一定性能差距

1.2 有序list

數據結構相同，部分操作方法要做對應修改

二、參考鏈接

http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganOrderedList.html

總結

以上是生活随笔為你收集整理的列表的实现与应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

列表