最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

双向链表

来源:博客园


(资料图片仅供参考)

双向链表既可以向前,也可以向后,其节点是由两个指针域,一个指向上一个节点,一个指向下一个节点,和一个数据域构成的。第一个节点的指向前一个指针为None,最后一个节点指向下一个为None

代码实现:

# -*- coding = utf-8 -*-# @Author: Wchime# @time: 2023/1/20 20:34# @file: 双向链表.pyclass Nodes(object):    """双向链表节点"""    def __init__(self, item):        self.item = item        self.next = None        self.prev = Noneclass DoubleLinkList(object):    """    双向链表    """    def __init__(self, node=None):        self.__link = node    def is_empty(self):        # 链表是否为空        return self.__link is None    def get_length(self):        """        获取链表长度        :return:        """        cur = self.__link        count = 0        while cur is not None:            count += 1            cur = cur.next        return count    def append(self,item):        """        添加节点, 当链表不是空链表时,需要找到最后一个节点        :param item:        :return:        """        node = Nodes(item)        if self.is_empty():            self.__link = node        else:            cur = self.__link            while cur.next is not None:                cur = cur.next            cur.next = node            node.prev = cur    def insert(self, index, item):        """        在指定位置插入节点,插入在第n个时,需要将第m-n+1个元素向后移动位置        :param index: 位置下标        :param item: 插入值        :return:        """        if index <=0:            node = Nodes(item)            node.next = self.__link            self.__link = node            node.next.prev = node        elif index > self.get_length()-1:            self.append(item)        else:            cur = self.__link            count = 0            while count < index:                count += 1                cur = cur.next            node = Nodes(item)            node.next = cur            node.prev = cur.prev            cur.prev.next = node            cur.prev = node    def remove(self, item):        """        根据值删除节点        :param item:        :return:        """        cur = self.__link        while cur is not None:            if cur.item == item:                if cur == self.__link:                    self.__link = cur.next                    if cur.next:                        # 判断链表是否只有一个节点                        cur.next.prev = None                else:                    cur.prev.next = cur.next                    if cur.next:                        cur.next.prev = cur.prev                break            else:                cur = cur.next    def search(self, item):        """        查找节点是否存在        :param item:        :return:        """        cur = self.__link        while cur is not None:            if cur.item == item:                return True            else:                cur = cur.next        return False    def travel(self):        """        链表遍历        :return:        """        cur = self.__link        while cur is not None:            print(cur.item, end="  ")            cur = cur.next        print("")if __name__ == "__main__":    singlelist = DoubleLinkList()    singlelist.append(1)    singlelist.append(7)    singlelist.append(5)    singlelist.travel()    singlelist.insert(1, 66)    singlelist.travel()    length = singlelist.get_length()    print(length)    print(singlelist.search(66))    singlelist.remove(66)    singlelist.travel()    print(singlelist.is_empty())

关键词: 双向链表 是否存在 是否为空