單向鏈表定義如下所示:

在頭部插入元素如下所示：

頭部插入元素最終達到的效果，先改變指向100的節點，再改變指向頭部的節點(這個有先后順序)，這樣以前100之后的節點順序什么的就不用改變了

在指定位置插入元素，如下所示:

單鏈表查找元素如下所示:

單鏈表刪除元素如下所示:

頭節點是刪除的節點的時候，如下所示:

還有一種情況是只有一個節點的時候，如下所示:

代碼如下所示:

# -*-coding=utf-8-*- class Node(object):"""單鏈表的節點"""def __init__(self, elem):# item存放數據元素self.elem = elem# next是下一個節點的標識self.next = Noneclass SingleLinkList(object):"""單鏈表"""# head是頭節點屬性,_head在Python中加兩個下劃線就是私有屬性# 這個node是用戶傳進來的def __init__(self, node=None):self.__head = nodedef is_empty(self):"""判斷是否為空"""return self.__head==Nonedef length(self):"""鏈表長度"""# cur初始時指向頭節點# cur游標，用來移動遍歷節點cur = self.__head # 這里是一個下劃線還是兩個待確定# count 記錄數量count = 0# 當cur.next != None，表示始終進入循環體，因為cur.next需要在循環體里面才能知道是多少# 尾節點指向None，當未到達尾部時while cur != None:count += 1# 將cur后移一個節點cur = cur.nextreturn countdef travel(self):"""遍歷整個鏈表"""cur = self.__headwhile cur != None:#添加這個這個，后期打印就不換行了print(cur.elem,end=" ")cur = cur.nextprint("")# passdef append(self, item):"""鏈表尾部添加元素，尾插法"""node = Node(item)# print('node值是:')# print(node)# 這個if條件是空鏈表的意思，我們需要考慮特殊條件# 先判斷鏈表是否為空，若是空鏈表，則將_head指向新節點if self.is_empty(): #賦值為空不然會報錯self.__head = node# 若不為空，則找到尾部，將尾節點的next指向新節點else:# print("222")# cur = self.__headcur = self.__headwhile cur.next != None:cur = cur.nextcur.next = node # 到最后一個位置將元素賦值def add(self,item):"""鏈表頭部添加元素，頭插法"""# 先創建一個保存item值的節點node = Node(item)# 將新節點的鏈接域next指向頭節點，即_head指向的位置node.next = self.__head# 將鏈表的頭_head指向新節點self.__head = node#pos是指定的位置,item是保存的元素def insert(self,pos,item):"""鏈表指定位置添加元素:param pos 從0開始"""# 若指定位置pos為第一個元素之前，則執行頭部插入if pos<=0: #頭插法self.add(item)# 若指定位置超過鏈表尾部，則執行尾部插入elif pos > (self.length()-1):#尾插法self.append(item)# 找到指定位置else:# pre用來指向指定位置pos的前一個位置pos-1，初始從頭節點開始移動到指定位置prev = self.__headcount = 0while count<(pos-1):count+=1prev = prev.next#當循環退出后,prev指向pos-1位置node = Node(item)# 先將新節點node的next指向插入位置的節點#prev.next存儲的是下一個節點的地址，因為是在任意位置插入的，新節點node需要連接下一個節點，node.next指向了下一個節點node.next = prev.next# 將插入位置的前一個節點的next指向新節點prev.next = nodedef search(self,item):"""查找節點是否存在""""""鏈表查找節點是否存在，并返回True或者False"""cur = self.__headwhile cur!=None:if cur.elem == item:return Trueelse:cur = cur.nextreturn Falsedef remove(self,item):"""刪除節點"""cur = self.__headpre = Nonewhile cur != None:# 找到了指定元素if cur.elem == item:#先判斷此節點是否是頭節點#頭節點 # 如果第一個就是刪除的節點if cur == self.__head:# 將頭指針指向頭節點的后一個節點self.__head = cur.nextelse:# 將刪除位置前一個節點的next指向刪除位置的后一個節點pre.next = cur.nextbreak # 刪除后再退出循環,需要一個總的break退出else:# 繼續按鏈表后移節點pre = curcur = cur.nextif __name__ == "__main__":# node = Node(100)ll = SingleLinkList()print(ll.is_empty()) #Trueprint(ll.length()) #0ll.append(1)print(ll.is_empty()) #Falseprint(ll.length()) #1#ll.append(2)ll.add(8)ll.append(3)ll.append(4)ll.append(5)ll.append(6)#8 1 2 3 4 5 6ll.insert(-1,9)ll.travel() #9 8 1 2 3 4 5 6ll.insert(3, 100)ll.travel() #9 8 1 100 2 3 4 5 6ll.insert(10,200)ll.travel() #9 8 1 100 2 3 4 5 6 200ll.remove(100)ll.travel() #9 8 1 2 3 4 5 6 200ll.remove(9)ll.travel() #8 1 2 3 4 5 6 200ll.remove(200)ll.travel() #8 1 2 3 4 5 6

總結

以上是生活随笔為你收集整理的python算法与数据结构-单链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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