單向鏈表
單向鏈表也叫單鏈表,是鏈表中最簡單的一種形式,它的每個節(jié)點包含兩個域,一個信息域(元素域)和一個鏈接域。這個鏈接指向鏈表中的下一個節(jié)點,而最后一個節(jié)點的鏈接域則指向一個空值。
表元素域elem用來存放具體的數(shù)據(jù)。
鏈接域next用來存放下一個節(jié)點的位置(python中的標(biāo)識)
變量p指向鏈表的頭節(jié)點(首節(jié)點)的位置,從p出發(fā)能找到表中的任意節(jié)點。
節(jié)點實現(xiàn)
class Node(object): """單鏈表的結(jié)點""" def __init__(self,item): # item存放數(shù)據(jù)元素 self.item = item # next是下一個節(jié)點的標(biāo)識 self.next = None
單鏈表的操作
is_empty() 鏈表是否為空
length() 鏈表長度
travel() 遍歷整個鏈表
add(item) 鏈表頭部添加元素
append(item) 鏈表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 刪除節(jié)點
search(item) 查找節(jié)點是否存在
單鏈表的實現(xiàn)
class Singlepnkpst(object): """單鏈表""" def __init__(self): self.__head = None def is_empty(self): """判斷鏈表是否為空""" return self.__head == None def length(self): """鏈表長度""" # cur初始時指向頭節(jié)點 cur = self.__head count = 0 # 尾節(jié)點指向None,當(dāng)未到達(dá)尾部時 while cur != None: count += 1 # 將cur后移一個節(jié)點 cur = cur.next return count def travel(self): """遍歷鏈表""" cur = self.__head while cur != None: print(cur.item,end = ' ') cur = cur.next print("")
頭部添加元素
def add(self, item): """頭部添加元素""" # 先創(chuàng)建一個保存item值的節(jié)點 node = Node(item) # 將新節(jié)點的鏈接域next指向頭節(jié)點,即_head指向的位置 node.next = self.__head # 將鏈表的頭_head指向新節(jié)點 self.__head = nod
尾部添加元素
def append(self, item): """尾部添加元素""" node = Node(item) # 先判斷鏈表是否為空,若是空鏈表,則將_head指向新節(jié)點 if self.is_empty(): self.__head = node # 若不為空,則找到尾部,將尾節(jié)點的next指向新節(jié)點 else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node
指定位置添加元素
def insert(self, pos, item): """指定位置添加元素""" # 若指定位置pos為第一個元素之前,則執(zhí)行頭部插入 if pos <= 0: self.add(item) # 若指定位置超過鏈表尾部,則執(zhí)行尾部插入 epf pos > (self.length()-1): self.append(item) # 找到指定位置 else: node = Node(item) count = 0 # pre用來指向指定位置pos的前一個位置pos-1,初始從頭節(jié)點開始移動到指定位置 pre = self.__head while count < (pos-1): count += 1 pre = pre.next # 先將新節(jié)點node的next指向插入位置的節(jié)點 node.next = pre.next # 將插入位置的前一個節(jié)點的next指向新節(jié)點 pre.next = node
刪除節(jié)點
def remove(self,item): """刪除節(jié)點""" cur = self.__head pre = None while cur != None: # 找到了指定元素 if cur.item == item: # 如果第一個就是刪除的節(jié)點 if not pre: # 將頭指針指向頭節(jié)點的后一個節(jié)點 self.__head = cur.next else: # 將刪除位置前一個節(jié)點的next指向刪除位置的后一個節(jié)點 pre.next = cur.next break else: # 繼續(xù)按鏈表后移節(jié)點 pre = cur cur = cur.next
查找節(jié)點是否存在
def search(self,item): """鏈表查找節(jié)點是否存在,并返回True或者False""" cur = self.__head while cur != None: if cur.item == item: return True cur = cur.next return False
以上這篇python數(shù)據(jù)結(jié)構(gòu)鏈表之單向鏈表(實例講解)就是小編分享給大家的全部內(nèi)容了,希望能給大家一個參考,也希望大家多多支持腳本之家。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
