python數(shù)據(jù)結構——單鏈表

  • 鏈表
  • 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)鏈表的操作

  1. 實現(xiàn)一個簡單的單向鏈表
    步驟:
    • 創(chuàng)建Node(節(jié)點)類
      • 值域:存放數(shù)據(jù)
      • 指針域:存放指向下一個元素的指針
    • 創(chuàng)建一個單鏈表結構
      • 初始化鏈表
      • 檢測是否為空鏈表
      • head
      • tail
  2. 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
            

源碼地址

參考文獻:

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市笑旺,隨后出現(xiàn)的幾起案子昼浦,更是在濱河造成了極大的恐慌,老刑警劉巖筒主,帶你破解...
    沈念sama閱讀 222,590評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件关噪,死亡現(xiàn)場離奇詭異,居然都是意外死亡乌妙,警方通過查閱死者的電腦和手機使兔,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來冠胯,“玉大人,你說我怎么就攤上這事锦针≤欤” “怎么了置蜀?”我有些...
    開封第一講書人閱讀 169,301評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長悉盆。 經(jīng)常有香客問我盯荤,道長,這世上最難降的妖魔是什么焕盟? 我笑而不...
    開封第一講書人閱讀 60,078評論 1 300
  • 正文 為了忘掉前任秋秤,我火速辦了婚禮,結果婚禮上脚翘,老公的妹妹穿的比我還像新娘灼卢。我一直安慰自己,他們只是感情好来农,可當我...
    茶點故事閱讀 69,082評論 6 398
  • 文/花漫 我一把揭開白布鞋真。 她就那樣靜靜地躺著,像睡著了一般沃于。 火紅的嫁衣襯著肌膚如雪涩咖。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,682評論 1 312
  • 那天繁莹,我揣著相機與錄音檩互,去河邊找鬼。 笑死咨演,一個胖子當著我的面吹牛闸昨,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播雪标,決...
    沈念sama閱讀 41,155評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼零院,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了村刨?” 一聲冷哼從身側響起告抄,我...
    開封第一講書人閱讀 40,098評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎嵌牺,沒想到半個月后打洼,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,638評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡逆粹,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3 342
  • 正文 我和宋清朗相戀三年募疮,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片僻弹。...
    茶點故事閱讀 40,852評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡阿浓,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出蹋绽,到底是詐尸還是另有隱情芭毙,我是刑警寧澤筋蓖,帶...
    沈念sama閱讀 36,520評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站退敦,受9級特大地震影響粘咖,放射性物質發(fā)生泄漏。R本人自食惡果不足惜侈百,卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3 335
  • 文/蒙蒙 一瓮下、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧钝域,春花似錦讽坏、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至战虏,卻和暖如春拣宰,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背烦感。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1 274
  • 我被黑心中介騙來泰國打工巡社, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人手趣。 一個月前我還...
    沈念sama閱讀 49,279評論 3 379
  • 正文 我出身青樓晌该,卻偏偏與公主長得像,于是被迫代替她去往敵國和親绿渣。 傳聞我的和親對象是個殘疾皇子朝群,可洞房花燭夜當晚...
    茶點故事閱讀 45,851評論 2 361

推薦閱讀更多精彩內(nèi)容