本文共 5522 字，大约阅读时间需要 18 分钟。

class DoubleLinkedNode(object):    def __init__(self, data):        self.data = data        self.next = None        self.prev = Noneclass DoubleLinkedList(object):    def __init__(self):        self.head = DoubleLinkedNode("头结点")    def GetLength(self):        """获取双链表长度        """        currentNode = self.head.next        length = 0        while currentNode != None:            length += 1            currentNode = currentNode.next        return length    def IsEmpty(self):        """判断链表是否为空        """        if self.GetLength() == 0:            print("该链表为空！")            return True        else:            return False    def Traval(self):        """遍历双链表        """        if self.IsEmpty():            return        currentNode = self.head        print("当前链表为：")        while currentNode != None:            print(currentNode.data, end="<->")            currentNode = currentNode.next        print("")    def Create(self):        data = input("请输入元素：")        cNode = self.head        while data != '#':            nNode = DoubleLinkedNode(data)            cNode.next = nNode            nNode.prev = cNode            cNode = nNode            data = input("请输入元素：")        self.Traval()    def InsertElementInTail(self):        """尾插法        """        element = input("待从尾部插入的结点的数据:")        if element == "#":            return        currentNode = self.head        newNode = DoubleLinkedNode(element)        while currentNode.next != None:            currentNode = currentNode.next        currentNode.next = newNode        newNode.prev = currentNode        self.Traval()    def InsertElementInHead(self):        """头插法        """        element = input("待从头部插入的结点的数据：")        if element == "#":            return        currentNode = self.head        newNode = DoubleLinkedNode(element)        newNode.next = currentNode.next        currentNode.next = newNode        newNode.prev = currentNode        self.Traval()    def InsertElementInSpecifiedPosition(self):        """在指定位置插入结点        """        Pos = 0        currentNode = self.head        element, position = input("结点的数据 待插入的结点在双链表中的位置").split(" ")        newNode = DoubleLinkedNode(element)        if int(position) < 1 or int(position) > self.GetLength()+1:            print("位置不合法！请重新确定位置！")            return        while currentNode.next != None:            Pos += 1            if Pos == int(position):                newNode.next = currentNode.next                currentNode.next = newNode                newNode.prev = currentNode                self.Traval()                return            else:                currentNode = currentNode.next    def FindElement(self):        """查找所有有指定数据的结点的位置        """        Position = []        Pos = 0        currentNode = self.head        element = input("待查找的数据：")        if self.IsEmpty():            print("当前双链表为空！无法查找！")            return        while currentNode.next != None:            currentNode = currentNode.next            Pos += 1            if currentNode.data == element:                Position.append(Pos)        if Position:            print("查找成功，值为", element, "的结点位于该双链表的第", Position, "位。")        else:            print("查找失败！当前双链表中不存在含有", element, "的结点")    def DeleteElementInSpecifiedPosition(self):        """在指定位置删除结点        """        print("在指定位置删除结点")        Pos = 0        currentNode = self.head        position = int(input("待删除的位置:"))        if self.IsEmpty():            print("当前双链表为空！无法删除结点！")            return        if position < 1 or position > self.GetLength():            print("位置不合法！请重新确定位置！")            return        while currentNode.next != None:            removedNode = currentNode.next            Pos += 1            if Pos == position:                currentNode.next = removedNode.next                if removedNode.next == None:                    del removedNode                else:                    removedNode.next.prev = currentNode                    del removedNode            else:                currentNode = currentNode.next        self.Traval()    def DeleteElement(self):        """删除所有有指定数据的结点        """        if self.IsEmpty():            print("当前双链表为空！")            return        element = input('请输入待删除结点的值：')        currentNode = self.head        while currentNode.next != None:            removedNode = currentNode.next            if removedNode.data == element:                currentNode.next = removedNode.next                if currentNode.next == None:                    del removedNode                else:                    removedNode.next.prev = currentNode                    del removedNode            else:                currentNode = currentNode.next        print("成功删除所有含值为", element, "的结点")        self.Traval()    def Destory(self):        print("正在销毁该链表...")        del self.head        print("已销毁该双链表！")dl = DoubleLinkedList()dl.Create()dl.InsertElementInTail()dl.InsertElementInHead()dl.InsertElementInSpecifiedPosition()dl.FindElement()dl.DeleteElementInSpecifiedPosition()dl.DeleteElement()-----------------------------------------------------------------------请输入元素：1请输入元素：2请输入元素：3请输入元素：4请输入元素：#当前链表为：头结点<->1<->2<->3<->4<->待从尾部插入的结点的数据:4当前链表为：头结点<->1<->2<->3<->4<->4<->待从头部插入的结点的数据：0当前链表为：头结点<->0<->1<->2<->3<->4<->4<->结点的数据 待插入的结点在双链表中的位置100 1当前链表为：头结点<->100<->0<->1<->2<->3<->4<->4<->待查找的数据：4查找成功，值为 4 的结点位于该双链表的第 [6, 7] 位。在指定位置删除结点待删除的位置:1当前链表为：头结点<->0<->1<->2<->3<->4<->4<->请输入待删除结点的值：4成功删除所有含值为 4 的结点当前链表为：头结点<->0<->1<->2<->3<->

带头结点的双链表的实现与带头结点的单链表的实现也有相当高的相似性，最大的区别就是前者会多一个结点指针域指向前一个结点的操作。

转载地址：http://jnzrz.baihongyu.com/