Python數據結構之雙鏈表

作者：一只小小鳥鳥 2021-07-15 06:43:12

開發(fā) 后端

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。

[[411390]]

本文轉載自微信公眾號「python與大數據分析」，作者一只小小鳥鳥。轉載本文請聯系python與大數據分析公眾號。

雙鏈表和單鏈表在查找和遍歷上沒什么區(qū)別，在新增節(jié)點、添加節(jié)點、刪除節(jié)點上需要注意前后節(jié)點的修改，比單鏈表會復雜一些，一不小心就繞暈了。

方法和單鏈表是一致的。

isempty(self) 鏈表是否為空

length(self) 鏈表長度

travel(self) 遍歷整個鏈表

add(self,item) 鏈表頭部添加元素

append(self,item) 鏈表尾部添加元素

insert(self,item,index) 指定位置添加元素

deletebyitem(self,item) 根據數據項刪除節(jié)點

deletebyindex(self,index) 根據索引位置刪除節(jié)點

search(self,item) 根據數據項查找節(jié)點是否存在

update(self,index,item) 暫無實現

getitem(self,index) 獲取索引位置對應的數據項

getindex(self,item) 獲取數據項對應的索引位置

如下：

#!/usr/bin/env python 
# -*- coding: UTF-8 -*- 
#                     _ooOoo_ 
#                   o8888888o 
#                    88" . "88 
#                 ( | -  _  - | ) 
#                     O\ = /O 
#                 ____/`---'\____ 
#                  .' \\| |// `. 
#                 / \\|||:|||// \ 
#               / _|||||-:- |||||- \ 
#                | | \\\ - /// | | 
#              | \_| ''\---/'' | _/ | 
#               \ .-\__ `-` ___/-. / 
#            ___`. .' /--.--\ `. . __ 
#         ."" '< `.___\_<|>_/___.' >'"". 
#       | | : `- \`.;`\  _ /`;.`/ - ` : | | 
#          \ \ `-. \_ __\ /__ _/ .-` / / 
#      ==`-.____`-.___\_____/___.-`____.-'== 
#                     `=---=' 
''' 
@Project ：pythonalgorithms  
@File ：doublelinklist.py 
@Author ：不勝人生一場醉 
@Date ：2021/7/13 23:00  
''' 
 
 
class Node(object): 
    def __init__(self, data): 
        self.prev = None 
        self.data = data 
        self.next = None 
 
 
class DoubleLinkList(object): 
    def __init__(self): 
        self.header = None 
        self.currentnum = 0 
 
    def isempty(self): 
        return self.header == None 
 
    def travel(self): 
        tempnode = self.header 
        while tempnode != None: 
            print("{}".format(tempnode.data), end=" ") 
            tempnode = tempnode.next 
        print("\r") 
 
    def add(self, item): 
        node = Node(item) 
        if self.isempty(): 
            self.header = node 
            self.currentnum += 1 
            return 
        node.next = self.header 
        self.header.prev = node 
        self.header = node 
        self.currentnum += 1 
 
    def append(self, item): 
        if self.isempty(): 
            self.add(item) 
            self.currentnum += 1 
            return 
        tempnode = self.header 
        while tempnode.next is not None: 
            tempnode = tempnode.next 
        node = Node(item) 
        node.prev = tempnode 
        tempnode.next = node 
        self.currentnum += 1 
 
    def length(self): 
        length = 0 
        tempnode = self.header 
        while tempnode is not None: 
            length += 1 
            tempnode = tempnode.next 
        return length 
 
    def search(self, item): 
        tempnode = self.header 
        while tempnode != None: 
            if tempnode.data == item: 
                return True 
            else: 
                tempnode = tempnode.next 
        return False 
 
    def update(self, index, item): 
        pass 
 
    def getitem(self, index): 
        if index > self.currentnum or index <= 0: 
            raise IndexError("{} is not find in Linklist".format(index)) 
        tempnode = self.header 
        i = 1 
        while i < index: 
            tempnode = tempnode.next 
            i += 1 
        if tempnode.next == None: 
            return -1 
        else: 
            return tempnode.data 
 
    def getindex(self, item): 
 
        tempnode = self.header 
        i = 0 
        flag = False 
        while tempnode != None: 
            i += 1 
            if tempnode.data == item: 
                flag = True 
                return i 
            else: 
                tempnode = tempnode.next 
        if flag == False: 
            return 0 
 
    def insert(self, item, index): 
        tempnode = self.header 
        if index > self.currentnum + 1 or index <= 0: 
            raise IndexError("{} is not find in Linklist".format(index)) 
        # 指定位置為第一個即在頭部插入 
 
        if index == 1: 
            self.add(item) 
        elif index > self.currentnum - 1: 
            self.append(item) 
        else: 
            node = Node(item) 
            for i in range(1, index - 1): 
                tempnode = tempnode.next 
            node.next = tempnode.next 
            node.prev = tempnode 
            tempnode.next.prev = node 
            tempnode.next = node 
        self.currentnum += 1 
 
    def deletebyitem(self, item): 
        tempnode = self.header 
        while tempnode != None: 
            if tempnode.data == item: 
                self.currentnum -= 1 
                if tempnode == self.header: 
                    self.header = self.header.next 
                    if tempnode.next: 
                        tempnode.next.prev = None 
                    return 
                if tempnode.next is None: 
                    tempnode.prev.next = tempnode.next 
                    return 
                tempnode.prev.next = tempnode.next 
                tempnode.next.prev = tempnode.prev 
                return 
            tempnode = tempnode.next 
 
    def deletebyindex(self, index): 
 
        if index > self.currentnum or index <= 0: 
            raise IndexError("{} is not find in Linklist".format(index)) 
 
        i = 1 
        tempnode = self.header 
 
        if index == 1: 
            self.header = tempnode.next 
            if tempnode.next: 
                tempnode.prev = None 
            self.currentnum -= 1 
            return 
 
        while tempnode.next and i < index: 
            tempnode = tempnode.next 
            i += 1 
        if tempnode.next is None: 
            tempnode.prev.next = tempnode.next 
            self.currentnum -= 1 
            return 
        if i == index: 
            tempnode.prev.next = tempnode.next 
            tempnode.next.prev = tempnode.prev 
            self.currentnum -= 1 
 
 
if __name__ == '__main__': 
    a = DoubleLinkList() 
    a.add(1)  # 1 
    a.travel() 
    a.add(2) 
    a.travel() 
    a.append(4) 
    a.travel() 
    a.append(3) 
    a.travel() 
    print(a.length()) 
    print(a.search(1)) 
    print(a.getindex(4)) 
    print(a.getindex(5)) 
    print(a.getitem(2)) 
    # print(a.getitem(5)) 
    # IndexError: 5 is not find in Linklist 
    a.insert(5, 1) 
    a.travel() 
    a.insert(6, 5) 
    a.travel() 
    a.insert(7, 2) 
    a.travel() 
    a.deletebyitem(7) 
    a.travel() 
    a.deletebyitem(6) 
    a.travel() 
    a.deletebyitem(5) 
    a.travel() 
    a.deletebyindex(2) 
    a.travel() 
    a.deletebyindex(3) 
    a.travel() 
    a.deletebyindex(1) 
    a.travel()

調試了2、3個小時的bug，才跑通。

運行如下：

C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/doublelinklist.py 
1  
2 1  
2 1 4  
2 1 4 3  
4 
True 
3 
0 
1 
5 2 1 4 3  
5 2 1 4 6 3  
5 7 2 1 4 6 3  
5 2 1 4 6 3  
5 2 1 4 3  
2 1 4 3  
2 4 3  
2 4  
4  
 
Process finished with exit code 0

鏈表頭部增加節(jié)點示意圖

責任編輯：武曉燕來源： python與大數據分析

Python 數據結構