单链表的节点包含元素域和链接域，链接域指向链表中的下一个节点，而尾节点则指向空

image.pngimage.png

  1. 表元素域elem用来存放具体的数据
  2. 链表next用来存放下一个节点的位置
  3. 变量p指向链表的头结点的位置，从p出发找到表中的任意节点

单链表的操作

方法名 说明
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos,item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在

构造节点

  1. # 封装节点类
  3. #构造节点
  5. class Node(object):
  6.     def __init__(self,elem):#构造函数初始化
  7.         self.elem=elem  #创建一个数据
  8.         self.next=None  #链接区指向空

链表的构造

  1. #构造链表
  2. class SingleLinkList(object):
  4.     def __init__(self,node=None):
  5.         self.__head=node#定义__head指针指向头节点node

单链表 - 图3

  1. 创建初单链表类，初始化单链表的对象
  2. 传入node节点，并初始化，防止用户不传节点
  3. 创建一个__head指针，指向None
  4. __head=None：设头节点为私有属性，对外不需要知道其属性
  5. __head=node：传入头节点；当用户不传节点，则指向空

1.判断链表是否为空

  1.         if self.__head==None:
  2.             return True
  3.         else:
  4.             return False
  1.   #判断是否为空
  2.     def is_empty(self):
  3.         return(self.__head==None)
  1. 当__head指针指向空就是空链表
  2. 利用return可直接返回True或False

2.计算链表长度

  1. 定义一个cur游标（指针）用来遍历节点，并把__head指向的数据赋值给游标

单链表 - 图4

  1. 定义一个计数器count用于计数
  2. 设置count的值为0（可以处理链表为空的情况）
  3. 设置循环语句，让count一直加+1
  4. 设置循环语句的结束
    1. 当count设置为1时，设置结束条件为cur.next==None（需要考虑链表为空的情况）一般不使用
    2. 当count设置为0时，设置结束条件为cur==None
  5. 当计数器count+1，cur指向下一个节点cur.next

单链表 - 图5

  1. 最后返回计数器的值，即链表节点的个数，就是链表的长度
  1.     #单链表的长度
  2.     def length(self):
  4.         cur = self.__head#头节点所指赋给cur
  6.         #创建count为0，可以不用考虑链表为空的情况
  7.         count = 0           #创建一个计数器，来记录链表的长度
  9.           while cur != None:     #创建循环，并设置当游标指向尾结点的None时，停止循环
  11.             count += 1
  12.             cur = cur.next  #当计数器加1，那么游标就指向下一个游标的next，即下个数的地址，就是下一个数
  14.         return count        #返回结果count

3.遍历链表

与length方法的算法类似，只不过要把指向的数给打印出来

  1. 把头节点所指的节点赋值给游标
  2. 创建循环
  3. 打印出游标的值elem
  4. 游标就指向节点游标的next
  1.      #遍历单链表
  2.     def travel(self):
  3.     #与length方法的算法类似，只是要把指向的数给打印出来
  5.         cur=self.__head #游标指向头节点
  7.         while cur != None: #创建循环，当游标指向尾结点None时，停止循环
  9.             print(cur.elem)#遍历就是每次，打印出游标的值elem
  11.             cur = cur.next#游标就指向节点游标的next，就是下一个数

4.尾部添加元素

  1. 传入元素值item
  2. 根据值创建节点
  3. 把__head所指的节点(头节点)赋值给游标

单链表 - 图6

  1. 游标循环指向尾结点的next域

单链表 - 图7

  1. 断开None，链接传入的节点

单链表 - 图8

  1.     #传入元素值item
  2.     def append(self,item):
  3.         #创建节点
  4.         node=Node(item)
  6.         #创建游标
  7.         cur=self.__head
  9.         #用cur找到最后一个节点
  10.         while cur.next != None:
  11.             cur=cur.next
  13.         cur.next=node#传入节点

特殊情况

当链表为空时，cur=self.__head头节点为None，没有cur.next,发生错误。

所以要判断链表是为空if self.__head==None:

但是为了方便查看，我们通常调用方法is_empty(),来判断链表是否为空

  1. 创建节点
  2. 判断节点是否为空
    1. 为空：将节点传给头节点
    2. 不为空：将尾结点指向的None断开，指向node
  1.     def append(self,item):
  2.         node=Node(item)#调用class Node类创建
  4.         if self.is_empty(): #当节点为空，就把节点传给头节点
  5.             node=self.__head
  7.         else:               #否则找到尾结点，插入
  8.             cur=self.__head
  9.             while cur.next != None:
  10.                 cur=cur.next
  11.             cur.next=node

5.头部添加元素

单链表 - 图9

单链表 - 图10

  1. 创建节点
  2. 把__head指向的节点变成node指向
  3. __head指针指向创建的节点，作为头节点
  1.    def add(self,item):
  2.         node=Node(item)
  4.         node.next=self.__head
  6.         self.__head=node

6.指定位置添加元素

在指定位置插入元素，我们需要用户传入，插入的位置以及插入的节点，所以定义的方法为：

def(self,pos,item)

基本思路：

  1. 定义一个pre指针，用于找到插入的位置
  2. 把pre指向__head所指向的头节点

单链表 - 图11

  1. 传入一个节点，把节点的next区指向prev的next区

单链表 - 图12

  1. 把pre的next指向这个节点

单链表 - 图13

步骤思路：

  1. 创建pre指向头节点
  2. 创建计数器，来记录链表长度，并赋值为0
  3. 利用循环语句来移动指针pre
  4. 当计数器，即链表的个数等于插入位置的前一个数，就可以退出循环

单链表 - 图14

  1. 当循环退出后，进行基本步骤的插入

单链表 - 图15

  1. class SingleLinkList(object):
  2.     def __init__(self,node=None):
  3.         self.__head=node
  5.     def insert(self,pos,item):
  7.         pre=self.__head#创建指针pre
  9.         node=Node(item)#创建节点
  11.         count=0
  13.         while count<(pos-1):
  14.             count+=1
  15.             pre=pre.next#循环找pos-1
  17.         node.next=pre.next  #插入节点
  18.         pre.next=node

特殊情况

  • 空链表满足条件

  • 当插入的数为负数pos<=0

    • 调用头插法self.add()

  • 当插入的数大于链表的长度（尾节点）pos>length()-1【0开始，长度为length-1】

    • 注意位置≠链表长度【pos=length()-1：就代表时pos-1处断开节点】
    • 调用尾插法self.append()
  1.  def insert(self,pos,item):
  3.         pre=self.__head#创建指针pre
  4.         node=Node(item)#创建节点
  5.         count=0
  6.         if pos<=0:
  7.             self.add(item)
  8.         elif pos>(self.length()-1):
  9.             self.append(item)
  11.         else:
  12.             while count < (pos - 1):
  13.                 count += 1
  14.                 pre = pre.next  # 循环找pos-1
  15.             node.next = pre.next  # 插入节点
  16.             pre.next = node

7.查找元素

  1. 创建指针cur，遍历链表

  2. 当cur=None时结束循环【如果=cur.next，cur指向节点还没有比较】

    1. def search(self,item):
    3.  cur=self.__head()
    5.  while cur != None:
    6.      if cur.elem==item:#判断是否与要找的值相等
    7.          return True
    8.      else:
    9.          cur = cur.next#继续找
    11.  return False#一直没找到

8.删除节点

基本思路：
  1. 创建两个指针，前驱pre指向None，cur后继指向头节点

单链表 - 图16

单链表 - 图17

  1. 前驱pre指向变化的cur，后继往后移，指向下一个节点cur.next

单链表 - 图18
单链表 - 图19

  1. 将节点的前一个节点的next指向节点的next域（后一个节点）

单链表 - 图20

步骤思路：

  1. 创建指针cur指向头节点，pre指向空
  2. 找删除的节点，while循环遍历，只要cur节点不为None，就一直找
    1. 如果cur指向的值为传入的节点值，就按基本思路删除
    2. 否则就继续找下一个
  1.     def remove(self,item):
  3.         cur=self.__head
  4.         pre=None
  6.         while cur != None:
  8.             if cur.elem==item:
  9.                 pre.next=cur.next
  10.                 break  #删除完后，退出循环
  12.             else:
  13.                 pre=cur
  14.                 cur=cur.next

特殊情况
  • 删除的是首节点_：直接_head=cur.next

单链表 - 图21

  2. if cur.elem==item:
  4.     if cur==self.__head:
  5.         self.__head=cur.next
  6.     else:
  7.         pre.next=cur.next
  8.     break #删除完后，退出循环
  10. else:
  11.     pre=cur
  12.     cur=cur.next