链表 简介

链表（linked list）作为一种常见的数据结构，通常由数据和指针组合而成。在一些没有指针结构的程序语言中，如 python、java等,指针被引用所代替。链表中的每个节点通过指针或引用相连接，你可以通过指针或者引用来遍历节点。

下图为单个节点的构成：

链表也有很多种形式，有 单链表 、循环链表、双向链表，下面我们介绍一种常用的单链表：

在单链表中，每个节点包括指向下一个节点的指针。但是单链表的首尾节点却特立独行，头结点只有指针，却没有数据；尾节点恰好相反，只有数据，没有指针，也就是提示我们链表后面不再有其他的节点。当我们找到第一个节点的时候，我们可以很轻松的获取链表其余节点。

这就像小时候玩游戏，一群小伙伴排成一排，手拉着手。左手被别人握紧，右手也紧紧握住别人的左手。左手就代表数据，右手代表指针。从第一个同学开始，这种通过左右手建立的联系，使我们很轻松的就找到了每一个人的位置。如果有一个小伙伴要加入，他会被分配在自己最好的朋友的前面，姑且将其记作“友人A”，我们就从第一个小伙伴开始遍历，如果找到了一个右手握住“友人A”的同学，姑且记作“同学B”，我们就停下来。先让这个小伙伴紧紧抓住“友人A”的右手，再让“同学B”握住他的左手。这样，这位小伙伴就找了自己的归宿。如果走遍了这条长长的队伍，还有没有找到属于自己的联系，那就稍稍有些寂寞了。如果有的人最好的”朋友C”变心了，他要出局了。我们还是要从第一个人开始遍历这条长长的队伍，一旦我们找到这个人前面的“同学D”，让“同学D”握住”朋友C“的手，然后再断开这个人与”朋友C“之间的羁绊，这个人重又恢复了自由身，尽管有少许的寂寞。

下面我们用 python 实现简单的单链表：

创建一个节点

建立一个节点很简单，我们只要给节点对象的数据和指针属性赋值即可。头结点和尾节点稍稍有些不同，头结点数据为 None，尾节点指针为 None。

拿上面的例子说，就是没有人握住第一个小朋友的左手，所以说他的数据为空；最后一个小朋友也无法握住别人的左手，所以说他的指向为空。而其他小朋友，左手被别人紧紧握住，右手则紧紧握住别人，即数据与指向都不为空。

   class    node  ( object ):  
   def   __init__  ( self , data, pointer)  : 
  self .data = data 
  self . next  = pointer 
 
 # 构建了只有首尾结点的链表  
node = Node( 12 ,None) 
head = Node(None,node)  

创建单链表

创建链表，就是在链表的尾部增加一个新的尾节点。首先要创建一个新的尾节点，代码为 node = Node(value,None) 。其次将前面的节点 tail 指向新创建的尾节点，即 tail 的 next 属性要指向新创建的节点，代码为 tail.next = node 。

形象点说，要想在那条队伍后面再加上一个小朋友，只要让末尾的握住新来的左手，那么这条队伍就增加了一名成员。

   class   SingleLinkedList ( object ):  
   def   __init__  ( self )  : 
  self .head = Node(None, None) 
  self .point =  self .head 
  
   def   append  ( self , data)  : 
  # 末尾追加节点  
 new_node = Node(data, None) 
  self .point. next  = new_node 
  self .point = new_node  

插入节点

在特定节点前面插入数据：新建一个节点，然后找到特定节点的前驱结点，然后让新节点的 next 指向特定节点，而前驱结点也要指向新节点。

但是有些新来的人不甘心站在队伍的末尾，因为末尾的人没有”珍贵之物“（右手没有紧紧握住的对象），他想在队伍中找到命中之人。他就从头一个一个的寻找，直到发现有一个人握住了他的意中人。他就握住意中人的左手，再让前一个人握住他的左手。

   def   insert  ( self , data, find)  : 
  # 插入数据(前向插入数据)  
  if   not   self .head. next:  
 print( '链表为空' ) 
  return  None 
 new_node = Node(data, None) 
  self .point =  self .head 
  while   self .point. next .data !=  find:  
  self .point =  self .point. next  
  if   self .point. next  is  None:  
 print( '没有找到该元素' ) 
  return  None 
 
 new_node. next  =  self .point. next  
  self .point. next  = new_node  

头后插节点

head 节点之后插入节点，如果 head 后没有节点，那么就直接让 head 节点指向新建节点；否则的话，就让新节点指向 head 后一个节点，而 head 再指向新节点。

形象点说，如果第一个人就孤零零的站着，就直接握住新朋友的手就好了。如果第一个人已经有朋友了，就让新朋友握住他的旧朋友的手，他再顺势握住新朋友的手。

   def   insert_after_head  ( self , data)  : 
 node = Node(data, None) 
  if   not   self .head. next:  
  self .head. next  = node 
  return  None 
 node. next  =  self .head. next  
  self .head. next  = node  

删除节点

我们从单链表头部开始遍历，先找到要删除节点的前置节点 p，再新建一个节点 q 指向要删除节点，接着将 p 节点指向要删除节点的下一个节点，最后将 q 节点删除。

形象地说，在队伍中找到这个被”抛弃”之人，让他前面的人撇开他，接着握住他后面的人的左手。然后这个稍微有些可怜的人就被系统判定“出局了”。

   def   delete  ( self , find)  : 
  # 删除节点  
  # 判断是否为空链表  
  if   not   self .head. next:  
 print( '链表为空' ) 
  return  None 
  self .point =  self .head 
  while   self .point. next .data !=  find:  
  self .point =  self .point. next  
 pointer =  self .point. next  
  self .point. next  =  self .point. next . next  
 del pointer  

数据排序

这个长长的队伍要开始按照身高次序排序了，高个子在后，矮个子在前，即升序的顺序。从第一个人开始，依次问右手边的人，“我比你高吗？”，如果是的话，两个人就交换位置，这一轮下来，最高的人站在了队伍的最后。也就是说，至少有一个人的位置已经确定。紧接着，我们再开始同样的游戏，但这次我们只需要到倒数第二个人就好了，因为已经确定一个人的顺序了。当然如果有一轮下来，我们发现没有人交换位置，说明大家已经按照高矮排好了顺序，就可以结束游戏了。

   def   sort  ( self )  : 
  # get_size()改变了 self.point 的指向  
 length =  self .get_size() 
 i, j =  0 ,  0  
 flag =  1  
  while  i <  length:  
  self .point =  self .head. next  
  while  j < length - i -  1 : 
  if   self .point.data >  self .point. next . data:  
 temp =  self .point.data 
  self .point.data =  self .point. next .data 
  self .point. next .data = temp 
  self .point =  self .point. next  
 j +=  1  
 flag =  0  
  if   flag:  
   break   
 i +=  1  
 j =  0   

求中间节点 只允许遍历一次

如果可以多次遍历的话，我们大可以求出链表的大小，再算出中间节点。但只让遍历一次的话，我们就要用到快慢指针的方法了。形象地说，就是有两个同学在操场上跑步，记为A,B。A 同学跑步速度是 B 同学的二倍，也就是说，A 同学跑完一圈的时候，B 同学刚好跑完半圈。同理，我们用快慢指针来遍历链表，快指针到达尾节点时，慢指针正好指向了中间节点。 代码中体现为，快指针每次前进两个节点，而慢指针只前进一个节点。当快指针指向尾节点时，停止遍历。

  # 求中间节点 只允许遍历一次  
  def   quick_middle  ( self )  : 
 slow_point =  self .head 
 fast_point =  self .head 
  while  fast_point. next . next:  
 slow_point = slow_point. next  
 fast_point = fast_point. next . next  
  if   not  fast_point. next:  
  break  
  if  fast_point. next:  
 slow_point = slow_point. next  
  return  slow_point.data  

逆置

新建一个链表，遍历旧链表中的元素。将旧链表中的每一个元素插入到新链表头结点的后面。这样，先插入的数据反而被后插入的数据挤到了后面，原先最前面的数据节点变成了新链表尾节点，而原先的尾节点却变成了新链表最前面的数据节点。风水轮流转，这样就完成了链表的逆置操作。

   def   reverse  ( self )  : 
 local_list = SingleLinkedList() 
  self .point =  self .head 
 count =  0  
  while   self .point. next:  
 count +=  1  
  self .point =  self .point. next  
 data =  self .point.data 
 local_list.insert_after_head(data) 
  

打印节点

遍历节点，打印数据。

   def   print  ( self )  : 
  # 打印结点  
  self .point =  self .head 
  while   self .point. next:  
  self .point =  self .point. next  
 print( '{} ->' .format( self .point.data),  end = ' ' ) 
 print( '' )  

删除尾节点

根据链表大小，找到尾节点，然后类似删除节点的操作。

   def   delete_by_tail  ( self , num)  : 
 size =  self .get_size() 
 assert (num <= size) 
 assert (num >  0 ) 
 pos = size - num 
 count =  0  
  self .point =  self .head 
  while  count <  size:  
 count +=  1  
  self .point =  self .point. next  
  if  count ==  pos:  
 pointer =  self .point. next  
  self .point. next  =  self .point. next . next  
 del pointer  

我犯的错误

head 的 next 就指向 node 节点，再让 node 节点指向 head.next，就相当于 node 节点指向了自身，所以循环打印时，永远跳不出循环。

 # 典型错法： 
# 自身指向自身 打印值时出不去 
node = Node( 4 ,None) 
head = Node( 4 ,node) 
node. next  = head. next  
i =  0  
 while  node.nex t:  
 i +=  1  
  print (node.data) 
  if  i >  12 : 
  break   

这就是本节的全部内容了，看完了要多多用编程巩固一下哦。