线性表的双向链表的代码实现（python语言）

╰+哭是因爲堅強的太久メ 2022-05-24 03:46 157阅读 0赞

![70][]

# 单链表
    class ListNode:  # 定义链表节点类
        def __init__(self, elem_1, next_1):
            self.elem = elem_1  # 节点的值
            self.next = next_1  # 指向下一个节点的链接
    
    
    class TwoListNode(ListNode):  # 定义一个双向链表的节点类
        def __init__(self, previous, elem, next):
            ListNode.__init__(self, elem, next)  # next是双链表的节点的尾指针
            self.previous = previous  # previous是双链表的节点的头指针
    
    
    class LDList(LoopList_1):  # 基于带尾节点引用的单链表派生一个双链表类
        def __init__(self):
            LoopList_1.__init__(self)
    
    
    def prepend(self, elem):  # 在双向链表的头部加入新节点
        p = TwoListNode(None, elem, self.head)  # p指向新插入结点的值项
        self.head = p  # 双链表的头部的head指向新插入的p节点
        if self.rear is None:  # 双链表的判空
            self.rear = p  # 为空时双链表的头部的rear指向新插入的p节点的值项
        else:
            p.next.previous = p  # 双链表原本不为空时，让原双链表的首节点的previous指向新插入的p节点
    
    
    def append(self, elem):  # 在双向链表的尾部加入新节点
        p = TwoListNode(self.rear, elem, None)  # p指向新插入结点的值项
        self.rear = p  # 双链表的头部的rear指向新插入的p节点
        if self.head is None:  # 双链表的判空
            self.head = p  # 双链表为空时，双链表的头部的head指向新增节点
        else:
            p.previous.next = p  # 双链表不为空时，原双链表的尾节点指向新增的p节点
    
    
    def pop(self):  # 删除双链表的头结点
        if self.head is None:  # 双链表的判空
            raise ValueError  # 双链表为空时产生价值错误
        e = self.head.elem  # e指向双链表的头部的head指向的elem
        self.head = self.head.next  # 双链表的头部的head指向双链表的原链表首节点的下一个节点
        if self.head is None:  # 如果双链表原本只有一个节点
            self.rear = None  # 双链表的头部的rear指向空（双链表原本只有一个节点，删除后为空双链表）
        else:
            self.head.previous = None  # 双链表的原首节点的下一节点的head重置为空
        return e  # 返回删除的节点的值
    
    
    def pop_last(self):  # 删除双链表的尾节点
        if self.head is None:  # 双链表的判空
            raise ValueError  # 双链表为空时产生价值错误
        e = self.rear.elem  # e指向双链表的头部的rear指向的elem
        self.rear = self.rear.previous  # 双链表的头部的rear指向双链表的原链表尾节点的上一个节点
        if self.rear is None:  # 如果双链表原本只有一个节点
            self.head = None  # 双链表的头部的head指向空（双链表原本只有一个节点，删除后为空双链表）
        else:
            self.rear.next = None  # 双链表的原尾节点的上一节点的rear重置为空
        return e  # 返回删除的节点的值

[70]: /images/20220524/3a90fbac0a1a4d77bb8531ccf3a508cd.png