链表之单向链表

1、结点

结点是链表中一个重要且基本的组成部分，结点的形式是，第一个存储区存储结点元素数据，第二个存储区存储下一个结点的地址。以下采用python定义一个LNode类：

class LNode:
    '''
    这是自我定义的链表，包含了链表的基本结构和方法
    '''
    def __init__(self,elem,next_=None):
        '''
        一个self为一个结点
        第一个元素elem为结点的数值，第二个元素为下一个结点的位置
        :param elem:
        :param next_:
        '''
        self.elem = elem
        self.next = next_

2、单向链表

2.1 定义链表

链表是一个一个结点相连组成的结构，为了避免过于抽象，这里先定义一个单向链表：

class List_Single:
    '''
        这是自我定义单向链表，包含了链表的基本结构和方法
        '''
    def __init__(self):
        self._head = None
    def is_empty(self):
        return self._head is None

2.2列表方法

链表也需要像python的其它官方结构一样，具有可以在头尾端插入数据以及删除数据的功能

1、头部增删结点

• 头部删除结点

 def pop(self):
        '''
        功能：删去链表头部结点，并显示该结点的数据信息
        实现思想：
        首先判断链表本身是否有结点【判断是否为空】，若空则返回异常
        其次：将表头结点的信息用一个变量保存
        最后将指向一个表头结点的self._head地址信息改为该表头结点的指向地址即可
        :return:
        '''
        if self.is_empty():
            raise LinkedListUnderflow('in pop')
        e = self._head.elem#将表头结点的值保存起来
        self._head = self._head.next#将指针移向下一个结点
        return e # 返回删除的表头数据

• 头部增加结点

    def prepend(self,elem):
        '''
        在链表的头部加入一个结点：
        实现思想：
        由于链表只需要找到第一个元素的位置，
        所以只需要将self._head指向新增的结点，而结点指向增加元素前的头部
        传入结点的值
        :param elem:
        :return:
        '''
        self._head = LNode(elem,self._head)

   

2 尾部增删结点

• 尾部删除结点
  在链表的尾部增删数据和在头部有所不同，在尾部删除数据，需要找到最后一个数据的前一个结点，然后将前一结点的第二个元素指针设置为空，这样链表就可以实现删除尾端最后一个数据，代码示例：

    def pop_last(self):
        '''
        函数功能：将链表的最后一个结点删除并且返回结点的值
        功能实现：
        第一步：与pop类似，要确认链表确实有结点，
        Note:如果第一个结点就是最后一个结点，加上一个判断条件会很大程度上减少复杂度

        第二步：采用append类似的方法，遍历结点，然后将他的上一个结点指针指向None【逻辑删除】
        :return:
        '''
        if self.is_empty():#如果是空表，引发异常
            raise LinkedListUnderflow('in pop_last')
        p = self._head#遍历指针
        if p.next is None:#表中只有一个元素
            e = self._head.elem#保存第一个元素的值
            self._head = None#将表变为空表
            return e #返回元素的值
        #开始遍历操作
        while p.next.next is not None:
            #即p为倒数第二个结点,
            # 那么p.next就是最后一个结点，所以p.next.next为None
            p = p.next#p变为p的下一个结点
        #找到了p为最后一个结点
        e = p.next.elem
        p.next = None#将最后一个结点删除，意即倒数第二个结点p的下一个指向为None
        return e

• 尾部增加结点
  在尾端增加数据，也同尾端删除数据一样，需要用到遍历指针p，故复杂度也是O(n)级别，代码示例如下：

    def append(self,elem):
        '''
        功能：在链表尾部加上一个元素
        实现思想：
        需要foreach（遍历）找到self._head.next = None的元素（如果链表为空将会简单很多）
        然后将self._head.next = 要插入的结点地址
        :param elem:
        :return:
        '''
        if self.is_empty():
            self._head = LNode(elem)#直接将表头指向新加入的元素
            return
        p = self._head#用一个中间变量来当作遍历指针
        while p.next is not None:#如果结点指向的下一地址不为空
            p = p.next#那么遍历指针指向下一个结点
        p.next = LNode(elem)#找到最后一个结点后，
        # 将遍历指针代表的结点的next地址指向新增的结点

3 查找功能

• 条件匹配
  第一个方法是设计用于在链表中查找是否有满足一个方法【在这里即设为pred方法】的结点，如果有则返回数据。如果有多个则返回第一个

    def find(self,pred):
        '''
        找出满足pred方法的元素，且该pred方法还有一个参数
        实现方法：同样地，采用链表方式
        :param pred:
        :return:
        '''
        p = self._head
        while p is not None:#p不为空
            if pred(p.elem):#如果满足方法pred的条件
                return p.elem#则返回结点的数据
            p = p.next#将p指向p的下一个元素

4 打印所有结点元素

• 定义
  为了使得链表可视化，设计了这个方法
  ···
  def printall(self):
  p = self._head#将遍历指针p,p指向链表头
  while p is not None:#当链表不为空
  print(p.elem,end = '')
  if p.next is not None:#当p不是最后一个元素
  print(', ',end='')#打印一个'，'，使其格式化

        p = p.next
    print('')#只是换行
  

···

• 打印示例
  如果要调用printall方法来打印，则直接调用即可，下面是调用示例

mlist1 = List_Single()#示例化一个链表结构
for i in range(10):
    mlist1.prepend(i)#往链表的前端加入结点

for i in range(11,20):
    mlist1.append(i)#往链表的尾端加入结点

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

3 总结

今天关于单向链表的基础就到这里结束，可以看出如果需要在链表的尾端增删元素，复杂度都是O(n)，那有没有更为高效的算法呢？我们明天见！

4 联系方式

如果您对本文有意见或者建议，欢迎通过邮箱与我联系：psywency@foxmail.com
比心心​
:heart:​