专栏首页python3用Python实现数据结构之链表

用Python实现数据结构之链表

链表

链表与栈,队列不一样,它是由一个个节点构成的,每个节点存储着本身的一些信息,也存储着其他一个或多个节点的引用,可以从一个节点找到其他的节点,节点与节点之间就像是有链连在一起一样,这种数据结构就叫做链表

单向链表

单向链表是链表的最简单形式,链表的第一个节点叫做头结点,最后一个节点叫做尾节点,每个节点都指向下一个节点,尾节点的指向为空,下面是其具体实现

class Empty(Exception):
    pass

class LinkedList():

    class Node():
        def __init__(self,element,next):
            self.element = element
            self.next = next

    def __init__(self):
        self.head = None
        self.size = 0

    def add_head(self,e):
        new = self.Node(e,self.head)
        self.head = new
        self.size +=1

    def remove_first(self):
        if self.size == 0:
            raise Empty('linkedlist is empty')
        self.head = self.head.next
        self.size -= 1

这个链表没有保存尾指针,并且添加与删除只在头部进行,节点类的定义嵌套在了其中

循环链表

循环链表即为单向链表的尾部不再指向空,而是指向头部,这样就不再需要头指针和尾指针了,只需要一个指向尾部的就行,下面是一个用循环链表实现的队列

class CircularQueue():

    """
    使用循环链表实现的队列
    """

    class Node():
        def __init__(self, element, next):
            self.element = element
            self.next = next

    def __init__(self):
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def first(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        return self.tail.next.element

    def dequeue(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        old_head = self.tail.next
        if self.size == 1:
            self.tail = None
        else:
            self.tail.next = old_head.next
        self.size -= 1
        return old_head.element

    def enqueue(self, e):
        new = self.Node(e, None)
        if self.is_empty():
            new.next = new
        else:
            new.next = self.tail.next
            self.tail.next = new
        self.tail = new
        self.size += 1

    def rotate(self):
        """
        将队列的头部变为尾部,循环移动一位
        """
        if self.size > 0:
            self.tail = self.tail.next

这里需要注意些的地方就是队列的插入与删除,因为涉及到节点指向的变换,其实手动画画图的话还是非常容易理解的

双向链表

前边的单向链表,循环链表,都是每一个节点为其后继节点维护一个引用,这样就会导致一些限制,即如果给定链表中的一个节点的引用,我们很难将其删掉,因为它并没有存储前驱节点的引用,对于这样的问题,我们会想到使用一种既存储前驱也存储后继的节点,这就是双向链表

实现的想法

之前的两种链表都是直接存储了头结点的引用,这样使我们在执行某些方法时,必须要判断一下是不是头结点,是不是为节点,为了避免这些特殊情况我们可以在链表的头部与尾部分别追加一个存储为空的头部节点与存储为空的尾部节点,我们叫它头哨兵与尾哨兵,这两个哨兵并不在序列中,并且只占用很少的空间,但却可以简化许多有关节点的操作。

具体实现

class DoubleLinkedList():

    """
    具有头哨兵与尾哨兵的双向链表
    """

    class Node():
        def __init__(self,element,prev,next):
            self.element = element
            self.prev = prev
            self.next = next

    def __init__(self):
        self.head = self.Node(None,None,None)
        self.tail = self.Node(None,None,None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def __len__(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert_between(self,e,predecessor,successor):
        new = self.Node(e,predecessor,successor)
        predecessor.next = new
        successor.prev = new
        self.size += 1
        return new

    def delete_node(self,node):
        predecessor = node.prev
        successor = node.next
        predecessor.next = successor
        successor.prev = predecessor
        element = node.element
        self.size -= 1
        node.prev=node.next=None
        return element

insert_between传入的是元素与前驱节点和后继节点

delete_node传入的是要删除的节点


参考《数据结构与算法Python语言实现》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python中HashMap的一个实现

    py3study
  • 从PEP-8学习Python编码风格

    Python3中应当总是使用UTF-8。(Python2使用ASCII。)在使用了规定编码后不需要再声明文件编码。

    py3study
  • Python要self的理由

    Python的类的方法和普通的函数有一个很明显的区别,在类的方法必须有个额外的第一个参数 (self ),但在调用这个方法的时候不必为这个参数赋值 (显胜于隐 ...

    py3study
  • python中HashMap的一个实现

    py3study
  • Python自建logging模块

    每一个logger对象,都有一个日志级别,它只会输出高于它level的日志。如果一个logger的level是INFO,那么调用logger.debug()是无...

    小破孩的梦想空间
  • 【CV中的Attention机制】BiSeNet中的FFM模块与ARM模块

    语义分割需要丰富的空间信息和相关大的感受野,目前很多语义分割方法为了达到实时推理的速度选择牺牲空间分辨率,这可能会导致比较差的模型表现。

    BBuf
  • Python要self的理由

    Python的类的方法和普通的函数有一个很明显的区别,在类的方法必须有个额外的第一个参数 (self ),但在调用这个方法的时候不必为这个参数赋值 (显胜于隐 ...

    py3study
  • python自学成才之路 类详细用法

    python是一门面向对象编程的语言,python的类和java中的类思想上有很多一样的地方,比如python类也是通过class修饰,里面也有成员属性,成员方...

    我是李超人
  • Python Day7

    是一种新建类的方式,新建的类称为子类,子类会遗传父亲的属性,可以减少代码冗余 在python当中,子类(派生类)可以继承一个或多个父类(基类,超类)

    py3study
  • Python GUI项目实战(一)登录窗体的设计与实现

    前面我们学习了Python GUI 图型化界面Tkinter的基础知识,为了检测我们的学习成果,学以致用。我们从今天开始做一个综合Tkinter案例--基于Tk...

    小雨编程

扫码关注云+社区

领取腾讯云代金券