单链表的简单变形

数据结构之链表变形

一、单链表的简单变形

在前面一节中，我们讨论了链表这种数据结构以及其中的基本操作，但是前面的单链表有一个很明显的缺点：在尾端插入元素的效率非常低，复杂度达到了O(n)，远远大于在首端插入数据。为此，我们为尾端元素也添加一个引用域，![带有尾部结点的单链表]

带有尾部结点的单链表.png

为此，我们，需要设计一个新的链表结构，但是从0开始是不可取的，往往带来的结果是重复造轮子，所以，我们采用在python中常见的继承方式来创建一个类，如所有类都继承自object，所有异常类都继承自基本的异常类一样，往后创建的几乎所有链表结构都继承自前面创建的List_Single类。如果需要加入或者改动基本类中的功能，只需要==新增==或者==重写==即可。

1.1、初始化

class List_Single_Trans(List_Single):
    '''
    加入一个尾部结点
    '''
    def __init__(self):
        List_Single.__init__(self)#继承基类中有的初始化
        self._rear = None#初始化尾结点引用域

1.2、方法重写

1、prepend

这里还有一个问题，由于加入了新的引用域，当链表为空时，新插入的第一个结点也是最后一个结点，所以，prepend（前端插入）方法也需要重新定义：

判断链表是否为空
如果链表不为空：

    def prepend(self,elem):
        '''
        前端插入方法
        '''
        if self._head is None:#链表为空
            self._head = LNode(elem,self._head)
            self._rear = self._head
        else:
            self._head = LNode(elem,self._head)

为了可视化，编者做了两张图

首端插入流程图

原理图

2、append

  def append(self,elem):
        '''
        后端插入结点
        :param elem:新结点的值
        :return:不返回
        '''
        if self._head is None:
            self._head = LNode(elem,self._head)
            self._rear = self._head
        else:
            #将新加入的结点连在现有的尾端结点后
            self._rear.next = LNode(elem)
            #将尾端结点指向新加入的结点
            self._rear = self._rear.next

3、pop_last

删除最后一个结点，并且将尾结点中的元素值返回

判断是否为空表
判断首尾结点是否为一个【尽量保持用已有的类中定义的方法】
找到上一个结点，为o
保存最后一个结点中的值
使上一结点变为最后一个结点，尾端指针指向上一个元素
返回值

    def pop_last(self):
        '''
        删除最后一个结点，并且将尾结点中的元素值返回
        :return: 最后一个结点的元素值
        '''
        if self._head is None:
            raise LinkedListUnderflow('in pop_last')#程序在此结束，不需要else
        p = self._head
        if p.next is None:
            e = p.elem
            self._head = None
            return e#程序在此结束，不需要else
        while p.next.next is not None:#找到最后一个结点的前一个结点，
            # 例如如果最后一个结点为r，那么r.next = None
            # 则换到此处则为 p.next= r 即p.next为下一个结点，那么p即为最后一个结点的上一个结点
            p = p.next

        #存值
        e = p.next.elem
        #使p变为最后一个结点，即使引用域置为None
        p.next = None
        #尾端指针指向最后一个结点的上一个结点，也就是p
        self._rear = p

        return e

4、使用示例

mlist1 = List_Single_Trans()
for i in range(10):
    mlist1.prepend(i)

for i in range(11,20):
    mlist1.append(i)

#继承printall方法
mlist1.printall()#9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 12, 13, 14, 15, 16, 17, 18, 19

for i in range(5):
    mlist1.pop_last()
    
mlist1.printall()#9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 12, 13, 14

二、联系方式

如果在本篇文章中有发现任何错误，或者您有更好的建议或思维方式，欢迎与我联系！

联系方式：psywency@foxmail.com

备用：wency03lk@outlook.com

三、下期预告

下一期是讲循环列表哦！为了打实基础，编者在前期并不会很快，基础的学好了后期各种高能的时候才接得住哇！

今天给你们比两个心❤️:blue_heart:

单链表的简单变形