[数据结构与算法]双链表------pytohn

双链表 增删改查

# -*- codeing = utf-8 -*-
# @Time :2022/3/9 23:13
# @Author : 刘念卿
# @File : 双向链表.py
# @Software : PyCharm
class Two_Way_Link_List_Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class Two_Way_Link_List:
    def __init__(self):
        self._head = None

    def Is_Empty(self):
        """
        判空
        :return:
        """
        return self._head == None

    def Get_Length(self):
        """
        返回链表长度
        :return:
        """
        if self.Is_Empty():
            print('链表为空')
            return 0
        else:
            num = 0
            cur = self._head
            while cur:
                num += 1
                cur = cur.next
            return num

    def Add_To_Head(self, Data):
        """
        头插
        :param Data: 插入的值
        :return:
        """
        # 创建新节点
        node = Two_Way_Link_List_Node(Data)
        if self.Is_Empty():
            self._head = node
        else:
            node.next = self._head
            self._head.prev = node
            # 更新头节点
            self._head = node

    def Add_TO_Tail(self, Data):
        """
        尾插
        :param Data: 插入的值
        :return:
        """
        if self.Is_Empty():
            self.Add_To_Head(Data)
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            node = Two_Way_Link_List_Node(Data)
            cur.next = node
            node.prev = cur

    def Del_Data(self, pos):
        """
        删除指定位置的元素，并返回其值
        :param pos: 位置
        :return:
        """
        if self.Is_Empty():
            print('链表为空！')
        elif pos <= 1:
            self._head = self._head.next
            self._head.prev = None
        elif pos >= self.Get_Length():
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.prev.next = None
            cur.prev = None
        else:
            cur = self._head
            n = 0
            while cur and pos - 1 != n:
                n += 1
                cur = cur.next
            cur.prev.next = cur.next
            cur.next.prev = cur.prev
            return cur.data

    def Traversal_List(self):
        """
        遍历链表
        :return:
        """
        if self.Is_Empty():
            print("链表为空！")
        else:
            cur = self._head
            while cur:
                if cur == self._head:
                    print(cur.data,end=' ')
                else:
                    print('-> ', cur.data, end=' ')
                cur = cur.next
            print('')

    def Alter(self, Data, pos):
        """
        修改指定位置的数值
        :param Data:
        :param pos:
        :return:
        """
        if self.Is_Empty():
            print("链表为空")
        else:
            if pos in range(1, self.Get_Length() + 1):
                num = 0
                cur = self._head
                while cur and num != pos - 1:
                    num += 1
                    cur = cur.next
                cur.data = Data
            else:
                print("超出范围!")

if __name__ == '__main__':
    Li = Two_Way_Link_List()
    print(Li.Is_Empty())
    Li.Add_To_Head(2)
    Li.Add_To_Head(1)
    Li.Add_TO_Tail(3)
    Li.Traversal_List()
    print(Li.Get_Length())
    print('delete:',Li.Del_Data(2))
    Li.Alter(55,1)
    Li.Traversal_List()