python实现双向链表

Dear 丶 2022-01-23 09:15 236阅读 0赞

## 双向链表的定义 ##

数据节点包含两个指针,一个指向前一个元素,一个指向后一个元素,因此需要定义一个双链表的数据结构  
完整代码如下:

# 数据结构定义
    
    class Node:
        """
        双向链表,每个节点除了指向下一个元素之外,还需要指向前一个元素
        1---->2<=====>3<====>4---->None
        """
        def __init__(self, value):
            self.value = value
            self.prev = None  # 前一个节点
            self.next = None  # 后一个节点
    
    
    # 链表功能的实现
    
    class DeLinkList:
    
        def __init__(self):
            self.__head = None
    
        def range(self):
            """
            遍历
            :return:
            """
            head = self.__head
            while head:
                print(head.value)
                head = head.next
    
        def isEmpty(self):
            """
            判断是否为空
            :return:
            """
            return self.__head is None
    
        def length(self):
            """
            获取长度
            :return:
            """
            count = 0
            head = self.__head
            while head:
                count += 1
                head = head.next
    
            return count
    
        def add(self, value):
            """
            往头部添加元素
            :param value:
            :return:
            """
            head = self.__head
            newNode = Node(value)
            if head is None:
                self.__head = newNode
            else:
                newNode.next = head
                newNode.next.prev = newNode
                self.__head = newNode
    
        def append(self, value):
            """
            往尾部添加,添加完以后,需要指向前一个元素
            :param value:
            :return:
            """
            head = self.__head
            newNode = Node(value)
            if self.isEmpty():
                self.__head = newNode
            else:
                while head.next:
                    head = head.next
                head.next = newNode
                newNode.prev = head
    
        def insert(self, index, value):
            """
            插入指定位置
            :param index:
            :param value:
            :return:
            """
            if index <= 0:
                self.add(value)
            elif index > self.length():
                self.append(value)
            else:
                newNode = Node(value)
                head = self.__head
                count = 0
                while count < (index - 1):
                    count += 1
                    head = head.next
                head.next.prev = newNode
                newNode.next = head.next
                newNode.prev = head
                head.next = newNode
    
        def delete(self, value):
            """
            删除元素
            :param value:
            :return:
            """
            head = self.__head
            if head is None:
                return
            if value == head.value:
                self.__head = head.next
            else:
                while head:
                    # 找到了,修改它前面的指向
                    if head.value == value:
                        head.prev.next = head.next
                        # 后面还存在节点的情况
                        if head.next:
                            head.next.prev = head.prev
                        break
                    else:
                        head = head.next
    
    
    if __name__ == "__main__":
        delink = DeLinkList()
        delink.add(0)
        delink.append(1)
        delink.append(2)
        delink.add(3)
        delink.insert(20, 8)
        delink.insert(0, 11)
        delink.insert(1, 5)
        delink.delete(2)
        delink.range()