189 8069 5689

5.双链表

1.单链表的缺点:

公司专注于为企业提供成都网站设计、成都网站建设、微信公众号开发、商城网站制作重庆小程序开发,软件按需定制等一站式互联网企业服务。凭借多年丰富的经验,我们会仔细了解各客户的需求而做出多方面的分析、设计、整合,为客户设计出具风格及创意性的商业解决方案,创新互联公司更提供一系列网站制作和网站推广的服务。

(1)remove操作要从头到尾遍历,时间复杂度是O(n)

(2)只能单向遍历,不能反向遍历

2.使用双链表可以克服以上两个缺点

双链表相对于单链表来说,双链表的节点(Node)多了一个指针:

5.双链表

这样一来就能指向前一个节点,而且也可以指向后一个节点。

同样root节点也有一个prev和next,root节点的next指向head节点,head节点的prev指向root节点,这样就能实现一个双端链表。

5.双链表

循环双端链表:

比如要反向遍历的时候,都是从root节点作为一个入口,把root节点的prev反过来指向tail节点,这样就能实现从头向尾节点遍历,然后从root节点的prev反过来指向上一个节点,对比正向遍历从next指向下一个节点,这样就实现循环双端链表。

双链表的属性:

                             

                data {    root          有个根节点

                              maxsize    控制它的最大长度

                              length      记录长度的属性

双链表

                method {    headnode    获取头节点的方法

                                   tailnode       获取尾节点的方法

                                   append        最后添加新节点

                                   appendleft   在头节点前面,根节点后面添加新节点

                                   remove        删除节点,时间复杂度为O(1);

                                                       比如,有3个节点,要删除中间节点,就可以让前面和后面节点互指,最后再del掉中间的节点。

                                   iter_node     遍历节点的操作

                                   iter_node_reverse      反向遍历节点的操作

实现方式:

class Node(object):
    def __init__(self, value=None, prev=None, next=None):
        self.value, self.prev, self.next = value, prev, next

class CircualDoubleLinkedList(object):
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        node =Node()                        #这两行代码,用于构建一个根节点,
        node.next, node.prev = node, node   #这个根节点是自己指向自己的默认是一个闭环。
        self.root = node                    #把node赋值给根节点
        self.length = 0                     #长度属性默认是0,root节点是不计算在链表长度里面的

    def __len__(self):
        return self.length                  #返回长度值

    def headnode(self):                     #定义头节点
        return self.root.next               #也就是root节点的下一个节点

    def tailnode(self):                     #定义尾节点
        return self.root.prev               #也就是root节点的上一个节点

    """
        假设有一条几个节点的链表,插入一个新的节点前,要先构造这个新的节点,
        然后再让链表原来尾节点的next指向新节点,并且新节点的prev指向原来的
        尾节点,root节点的prev也要指向新节点,新节点的next指向root节点,
        这样就形成了一个闭环,实现了append新增节点。
    """
    def append(self, value):
        if self.maxsize is not None \
            and len(self) > self.maxsize:       #判断是否已经超长,如果是就报异常。
            raise Exception("The LinkedList is Full")
        node = Node(value=value)                           #构造新节点
        tailnode = self.tailnode()              #尾节点

        tailnode.next = node                    #尾节点的next指向新节点
        node.prev = tailnode                    #新节点的prev指向尾节点
        node.next = self.root                   #新节点的next指向root节点
        self.root.prev = node                   #root节点的prev指向新节点

        self.length += 1                        #最后将长度+1

    def appendleft(self, vlaue):
        if self.maxsize is not None \
            and len(self) > self.maxsize:       #判断是否已经超长,如果是就报异常。
            raise Exception("The LinkedList is Full")
        node = Node(value=vlaue)
        if self.root.next is self.root:         #判断这个链表是空的情况
            node.next = self.root
            node.prev = self.root               #新节点的next和prev都指向root节点,形成一个闭环。
            self.root.next = node               #同理,将root节点的next指向新节点
            self.root.prev = node               #将root节点的prev指向新节点
        else:                                   #否则,如果链表不是空的话
            headnode = self.root.next           #定义root节点的next节点是链表的头节点
            node.prev = self.root               #将新节点的prev指向root节点
            node.next = headnode                #将新节点的next指向原头节点
            headnode.prev = node                #最后将头节点的prev指向新节点
        self.length += 1                        #链表长度加1

    def remove(self, node):                     #node是要删除的节点,是O(1)的时间复杂度,注意是node不是value
        if node is self.root:                   #如果只有根节点,啥都不返回
            return
        else:                                   #否则是非根节点
            node.prev.next = node.next          #将要删除节点的前一个节点的next指针指向要删除节点的下一个节点
            node.next.prev = node.prev          #将要删除节点的后一个节点的prev指针指向要删除节点的上一个节点
        self.length -= 1                        #链表长度-1
        return node                             #返回删除的节点

    def iter_node(self):                        #遍历节点
        if self.root.next is self.root:         #防止链表是空的
            return
        curnode = self.root.next                #否则,不是空的,从头开始遍历
        while curnode.next is not self.root:    #当curnode不是尾节点
            yield curnode                       #一直把curnode节点给yield出来
            curnode = curnode.next              #更新curnode节点,让curnode一直往下一个节点走
        yield curnode                         #最后别忘了把最后一个curnode给yield出来
                                                #因为遍历到最后一个节点,但并没有去yield这个节点
                                                #当while循环终止时,当前curnode已经到达了tailnode节点,
                                                #所以要把它yield出来才完整。

    def iter_node_reverse(self):
        if self.root.prev is self.root:
            return
        curnode = self.root.prev                #和正向遍历相反,这个是tailnode节点
        while curnode.prev is not self.root:
            yield curnode
            curnode = curnode.prev              #前移
        yield curnode



#单元测试
def test_double_link_list():
    dll = CircualDoubleLinkedList()
    assert len(dll) == 0
    dll.append(0)
    dll.append(1)
    dll.append(2)
    assert list(dll) == [0, 1, 2]
    assert [node.value for node in dll.iter_node_reverse()] == [2, 1, 0]
    assert [node.value for node in dll.iter_node()] == [0, 1, 2]
    headnode = dll.headnode()           #取头节点
    assert headnode.value == 0          #断言头节点的值为0,因为0是第一个被添加的
    dll.remove(headnode)                #O(1)
    assert len(dll) == 2
    assert [node.value for node in dll.iter_node()] == [1, 2]
    dll.appendleft(0)
    assert [node.value for node in dll.iter_node()] == [0, 1, 2]

执行测试:

# pytest double_link_list.py

平均时间复杂度:

循环双端链表操作平均时间复杂度
cdll.append(value)O(1)
cdll.appendleft(value)O(1)
cdll.remove(node),注意这里参数是 nodeO(1)
cdll.headnode()O(1)
cdll.tailnode()O(1)

本文名称:5.双链表
当前地址:http://jkwzsj.com/article/pjspci.html

其他资讯