数据结构——链表-阿里云开发者社区

原理概要

通过前面对线性顺序表的分析，我们知道当创建顺序表时必须分配一块连续的内存存储空间，而当顺序表内部数组的容量不足时，则必须创建一个新的数组，然后把原数组的的元素复制到新的数组中，这将浪费大量的时间。而在插入或删除元素时，可能需要移动数组中的元素，这也将消耗一定的时间。鉴于这种种原因，于是链表就出场了，链表在初始化时仅需要分配一个元素的存储空间，并且插入和删除新的元素也相当便捷，同时链表在内存分配上可以是不连续的内存，也不需要做任何内存复制和重新分配的操作，由此看来顺序表的缺点在链表中都变成了优势，实际上也是如此，当然链表也有缺点，主要是在访问单个元素的时候需要遍历元素的时间开销上。

从图可以看出线性链表的存储结构是用若干个地址分散的存储单元存放数据元素的，逻辑上相邻的数据元素在物理位置上不一定相邻，因此每个存储单元中都会有一个地址指向域，这个地址指向域指明其后继元素的位置。在链表中存储数据的单元称为结点(Node)，从图中可以看出一个结点至少包含了数据域和地址域，其中数据域用于存储数据，而地址域用于存储前驱或后继元素的地址。前面我们说过链表的插入和删除都相当便捷，这是由于链表中的结点的存储空间是在插入或者删除过程中动态申请和释放的，不需要预先给单链表分配存储空间的，从而避免了顺序表因存储空间不足需要扩充空间和复制元素的过程，提高了运行效率和存储空间的利用率。

实现分析

链表接口:ILinkedList和存储数据的结点类Node

结点类Node

/*** Created by zejian on 2016/10/21.* 单向链表节点*/publicclassNode<T> {
publicTdata;//数据域publicNode<T>next;//地址域publicNode(Tdata){
this.data=data;
    }
publicNode(Tdata,Node<T>next){
this.data=data;
this.next=next;
    }
}

ILinkedList接口

/*** Created by zejian on 2016/10/21.* 链表顶级接口*/publicinterfaceILinkedList<T> {
/*** 判断链表是否为空* @return*/booleanisEmpty();
/*** 链表长度* @return*/intlength();
/*** 获取元素* @param index* @return*/Tget(intindex);
/*** 设置某个结点的的值* @param index* @param data* @return*/Tset(intindex, Tdata);
/*** 根据index添加结点* @param index* @param data* @return*/booleanadd(intindex, Tdata);
/*** 添加结点* @param data* @return*/booleanadd(Tdata);
/*** 根据index移除结点* @param index* @return*/Tremove(intindex);
/*** 根据data移除结点* @param data* @return*/booleanremoveAll(Tdata);
/*** 清空链表*/voidclear();
/*** 是否包含data结点* @param data* @return*/booleancontains(Tdata);
/*** 输出格式* @return*/StringtoString();
}

boolean isEmpty()实现分析需要判断链表是否为空的依据是头结点head是否为null，当head=null时链表即为空链表，因此我们只需判断头结点是否为空即可，isEmpty方法实现如下：

/*** 判断链表是否为空* @return*/@OverridepublicbooleanisEmpty() {
returnthis.head==null;
}

int length()实现分析由于单链表的结点数就是其长度，因此我们只要遍历整个链表并获取结点的数量即可获取到链表的长度。

@Overridepublicintlength() {
intlength=0;//标记长度的变量Node<T>p=head;//变量p指向头结点while (p!=null){
length++;
p=p.next;//后继结点赋值给p，继续访问   }
returnlength;
}

T get(int index)实现分析在单链表中获取某个元素的值是一种比较费时间的操作，需要从头结点开始遍历直至传入值index指向的位置。

/*** 根据index索引获取值* @param index 下标值起始值为0* @return*/@OverridepublicTget(intindex) {
if(this.head!=null&&index>=0){
intcount=0;
Node<T>p=this.head;
//找到对应索引的结点while (p!=null&&count<index){
p=p.next;
count++;
        }
if(p!=null){
returnp.data;
        }
    }
returnnull;
}

T set(int index, T data)实现分析根据传递的index查找某个值并替换其值为data，其实现过程的原理跟get(int index)是基本一样的，先找到对应值所在的位置然后替换即可

/*** 根据索引替换对应结点的data* @param index 下标从0开始* @param data* @return 返回旧值*/@OverridepublicTset(intindex, Tdata) {
if(this.head!=null&&index>=0&&data!=null){
Node<T>pre=this.head;
intcount=0;
//查找需要替换的结点while (pre!=null&&count<index){
pre=pre.next;
count++;
        }
//不为空直接替换if (pre!=null){
ToldData=pre.data;
pre.data=data;//设置新值returnoldData;
        }
    }
returnnull;
}

add(int index, T data)实现分析单链表的插入操作分四种情况:

a.空表插入一个新结点，插语句如下：
head=newNode<T>(x,null);
b.在链表的表头插入一个新结点(即链表的开始处)，此时表头head!=null，因此head后继指针next应该指向新插入结点p，而p的后继指针应该指向head原来的结点，代码如下：
//创建新结点
Node<T>p=newNode<T>(x,null);
//p的后继指针指向head原来的结点
p.next=head;
//更新head
head=p;执行过程如下图：
c.在链表的中间插入一个新结点p，需要先找到给定插入位置的前一个结点，假设该结点为front，然后改变front的后继指向为新结点p，同时更新新结点p的后继指向为front原来的后继结点，即front.next，其执行过程如下图所示：
//新结点p
Node<T>p=newNode<T>(x,null);
//更新p的后继指向
p.next=front.next;
//更新front的后继指向
front.next=p;
d.在链表的表尾插入一个新结点(链表的结尾)在尾部插入时，同样需要查找到插入结点P的前一个位置的结点front（假设为front），该结点front为尾部结点，更改尾部结点的next指针指向新结点P，新结点P的后继指针设置为null，执行过程如下：
//front的next指针指向新结点，新结点的next指针设置为null
front.next=newNode<T>(x,null);

整体代码如下：

/*** 根据下标添加结点* 1.头部插入* 2.中间插入* 3.末尾插入* @param index 下标值从0开始* @param data* @return*/@Overridepublicbooleanadd(intindex, Tdata) {
if (data==null){
returnfalse;
        }
//在头部插入if (this.head==null||index<=1){
this.head=newNode<T>(data, this.head);
        }else {
//在尾部或中间插入intcount=0;
Node<T>front=this.head;
//找到要插入结点位置的前一个结点while (front.next!=null&&count<index-1){
front=front.next;
count++;
            }
//尾部添加和中间插入属于同种情况,毕竟当front为尾部结点时front.next=nullfront.next=newNode<T>(data,front.next);
        }
returntrue;
    }
•Tremove(intindex) 删除结点实现分析在单向链表中，根据传递index位置删除结点的操作分3种情况，并且删除后返回被删除结点的数据：代码实现如下：//头部删除，更新head指向head=head.next;代码语句如下：Node<T>r=front.next;
//更新结点指针指向front.next=r.next;
r=null;代码如下：front.next=null;
r=null;

a.删除链表头部（第一个）结点，此时需要删除头部head指向的结点，并更新head的结点指向，执行图示如下：
b.删除链表的中间结点，与添加是同样的道理，需要先找到要删除结点r（假设要删除的结点为r）位置的前一个结点front(假设为front)，然后把front.next指向r.next即要删除结点的下一个结点，执行过程如下：
c.删除链表的最后一个结点，通过遍历操作找到最后一个结点r的前一个结点front，并把front.next设置为null，即可。执行过程如下：

该方法整体代码实现如下：

/*** 根据索引删除结点* @param index* @return*/@OverridepublicTremove(intindex) {
Told=null;
if (this.head!=null&&index>=0){
//直接删除的是头结点if(index==0){
old=this.head.data;
this.head=this.head.next;
            }else {
Node<T>front=this.head;
intcount=0;
//查找需要删除结点的前一个结点while (front.next!=null&&count<index-1) {
front=front.next;
count++;
                }
//获取到要删除的结点Node<T>r=front.next;
if ( r!=null) {
//获取旧值old=r.data;
//更改指针指向front.next=r.next;
//释放r=null;
                }
            }
        }
returnold;
    }

void clear() 实现分析清空链表是一件非常简单的事，只需让head=null即可；代码如下：

/*** 清空链表*/@Overridepublicvoidclear() {
this.head=null;
}

带头结点的单链表以及循环单链表的实现

带头结点的单链表

前面分析的单链表是不带特殊头结点的，所谓的特殊头结点就是一个没有值的结点即：

//没有带值的头结点
Node<T>head=newNode<T>(null,null);

此时空链表的情况如下：

多了头结点的单向链表有什么好处呢？

通过对没有带头结点的单链表的分析，我们可以知道，在链表插入和删除时都需要区分操作位，比如插入操作就分头部插入和中间或尾部插入两种情况（中间或尾部插入视为一种情况对待即可），如果现在有不带数据的头结点，那么对于单链表的插入和删除不再区分操作的位置，也就是说头部、中间、尾部插入都可以视为一种情况处理了，这是因为此时头部插入和头部删除无需改变head的指向了.

头部插入如下所示：

接着再看看在头部删除的情况：

带头结点遍历从head.next开始：

因此无论是插入还是删除，在有了不带数据的头结点后，在插入或者删除时都无需区分操作位了，好~，到此我们来小结一下带头结点的单链表特点：

a. 空单链表只有一个结点，head.next=null。b. 遍历的起点为p=head.next。c. 头部插入和头部删除无需改变head的指向。

同时为了使链表在尾部插入时达到更加高效，我们可在链表内增加一个尾部指向的结点rear，如果我们是在尾部添加结点，那么此时只要通过尾部结点rear进行直接操作即可，无需从表头遍历到表尾，带尾部结点的单链表如下所示：

从尾部直接插入的代码实现如下：

/*** 尾部插入* @param data* @return*/@Overridepublicbooleanadd(Tdata) {
if (data==null)
thrownewNullPointerException("data can\'t be empty!");
this.rear.next=newNode<T>(data);
//更新末尾指针的指向this.rear=this.rear.next;
returntrue;
}

从代码和图示看来确实只要获取当前的尾部指向的结点rear并把新结点赋值给rear.next，最后更新rear结点的值即可，完全不用遍历操作，但是如果是根据index来插入的还，遍历部分结点还是少不了的，下面看看根据index插入的代码实现，由于有了头结点，头部、中间、尾部插入无需区分操作位都视为一种情况处理。

最后是删除，由于删除和插入的逻辑和之前不带头结点的单链表分析过的原理的是一样的，因此我们这里不重复了，主要注意遍历的起始结点变化就行。

循环单链表

有上述的分析基础，循环单链表(Circular Single Linked List)相对来说就比较简单了，所谓的循环单链表是指链表中的最后一个结点的next域指向了头结点head，形成环形的结构，我们通过图示来理解：

此时的循环单链表有如下特点：a.当循环链表为空链表时，head指向头结点，head.next=head。b.尾部指向rear代表最后一个结点，则有rear.next=head。

在处理循环单链表时，我们只需要注意在遍历循环链表时，避免进入死循环即可，也就是在判断循环链表是否到达结尾时，由之前的如下判断

Node<T>p=this.head;
while(p!=null){
p=p.next;
}
在循环单链表中改为如下判断：Node<T>p=this.head;
while(p!=this.head){
p=p.next;
}

因此除了判断条件不同，其他操作算法与单链表基本是一样的。

单链表的效率分析

由于单链表并不是随机存取结构，即使单链表在访问第一个结点时花费的时间为常数时间，但是如果需要访问第n个结点，需要从头结点head开始遍历部分链表，进行n次的p=p.next操作，这点从上述的图文分析我们也可以看出，这种情况类似于前面计算顺序表需要平均移动元素的总数，也就是说get(i)和set(i,x)的时间复杂度都为O(n)。由于链表在插入和删除结点方面十分高效的，因此链表比较适合那些插入删除频繁的场景使用，单纯从插入操作来看，我们假设front指向的是单链表中的一个结点，此时插入front的后继结点所消耗的时间为常数时间O(1),但如果此时需要在front的前面插入一个结点或者删除结点自己时，由于front并没有前驱指针，单凭front根本无法知道前驱结点，所以必须从链表的表头遍历至front的前一个结点再执行插入或者删除操作，而这个查询操作所消耗的时间为O(n),因此在已知front结点需要插入前驱结点或者删除结点自己时，消耗的时间为O(n)。当然这种情况并不是无法解决的，后面我们要分析到的双链表就可以很好解决这个问题，双链表是每个结点都同时拥有前后继结点的链表，这样的话上面的问题就迎刃而解了。上述是从已知单链表中front结点的情况下讨论的单链表的插入删除效率。我们可能会有个疑问，从前面单链表的插入删除的代码实现上来说，我们并不知道front结点的，每次插入和删除结点，都需要从表头开始遍历至要插入或者删除结点的前一个结点，而这个过程所花费的时间和访问结点所花费的时间是一样的，即O(n)，也就是说从实现上来说确实单链表的插入删除操作花费时间也是O(n)，而顺序表插入和删除的时间也是O(n)，那为什么说单链表的插入和删除的效率高呢？这里我们要明白的是链表的插入和删除之所以是O(N)，是因为查询插入点所消耗的，找到插入点后插入操作消耗时间只为O(1)，而顺序表查找插入点的时间为O(1)，但要把后面的元素全部后移一位，消耗时间为O(n)。问题是大部分情况下查找所需时间比移动短多了，还有就是链表不需要连续空间也不需要扩容操作，因此即使时间复杂度都是O(n)，所以相对来说链表更适合插入删除操作。

双链表的设计与实现

双链表的主要优点是对于任意给的结点，都可以很轻易的获取其前驱结点或者后继结点，而主要缺点是每个结点需要添加额外的next域，因此需要更多的空间开销，同时结点的插入与删除操作也将更加耗时，因为需要更多的指针指向操作。双链表的结构图如下：

创建HeadDoubleILinkedList类并实现IlinekedList接口

/*** Created by zejian on 2016/10/23.* 双链表的实现,带头结点(不带数据)的双链表,为了更高的效率该类包含指向尾部的指针tail*/publicclassHeadDoubleILinkedList<T>implementsILinkedList<T> {
protectedDNode<T>head; //不带数据的头结点protectedDNode<T>tail; //指向尾部的指针publicHeadDoubleILinkedList(){
//初始化头结点this.head=this.tail=newDNode<>();          
    }
//先省略其他代码    ........
}
结点类结构如下：packagecom.zejian.structures.LinkedList.doubleLinked;
/*** Created by zejian on 2016/10/23.* 双链表结点*/publicclassDNode<T> {
publicTdata;
publicDNode<T>prev, next;//前继指针和后继指针publicDNode(Tdata, DNode<T>prev, DNode<T>next)
    {
this.data=data;
this.prev=prev;
this.next=next;
    }
publicDNode(Tdata)
    {
this(data, null, null);
    }
publicDNode()
    {
this(null, null, null);
    }
publicStringtoString()
    {
returnthis.data.toString();
    }
}

双链表的插入操作分析与实现我们先来看看双链表的插入，虽然有不带数据的头结点，但是由于是双向链表，所以在插入双链表时需分两种情况，一种是在插入空双链表和尾部插入，另一种是双链表的中间插入，如下图在空双链表插入值x：

从图可以看出（a）和（b）属于同种情况，需要注意front.next != null的情况，否则就会抛空指针，而（c）的情况属于中间插入无需无需理会front.next != null的条件，因为中间插入时无论如何其后继结点时不会为null的，插入方法的实现代码如下：

/*** 插入结点* @param index* @param data* @return*/@Overridepublicbooleanadd(intindex, Tdata) {
if(index<0||data==null)
thrownewNullPointerException("index < 0 || data == null");
intj=0;
DNode<T>front=this.head;
//查找要插入结点位置的前一个结点while (front.next!=null&&j<index) {
j++;
front=front.next;
          }
//创建需要插入的结点,并让其前继指针指向front,后继指针指向front.nextDNode<T>q=newDNode<T>(data, front, front.next);
//空双链表插入和尾部插入，无需此操作if(front.next!=null) {
//更改front.next的前继指针front.next.prev=q;
          }
//更改front的后继指针front.next=q;
//在尾部插入时需要注意更新tail指向if(front==this.tail){
this.tail=q;
          }
returntrue;
  }

双链表的删除操作分析与实现双链表的删除操作与插入操作原理上是相似的，我们可以看出（a）（b）是属于同种情况，需要防止 p.next.prev抛空指针的情况，而对于（c）情况则无需关系 p.next.prev的值，删除的具体实现如下：

/*** 根据下标删除结点* 1.头删除* 2.中间删除* 3.尾部删除,更新tail指向* @param index 下标起始值为0* @return*/@OverridepublicTremove(intindex) {
intsize=length();
Ttemp=null;
if(index<0||index>=size||isEmpty()){
returntemp;
       }
DNode<T>p=this.head;
intj=0;
//头删除/尾删除/中间删除,查找需要删除的结点(要删除的当前结点因此i<=index)while (p!=null&&j<=index){
p=p.next;
j++;
       }
//当双链表只有一个结点时或尾部删除时,无需此步if(p.next!=null){
p.next.prev=p.prev;
       }
p.prev.next=p.next;
//如果是尾结点if (p==this.tail) {
this.tail=p.prev;//更新未结点的指向       }
temp=p.data;
returntemp;
   }

其他操作与单链表基本是一样的

循环双链表的设计与实现

如果双链表的最后一个结点的next指针域指向头结点，而头结点的prev指针指向头最后一个结点，则构成了双链表（Circular Doubly LinkedList），其结构如下图示：

在循环双链表中我们不再需要尾指向结点，因为整个链表已构成循环，在头结点head的位置也可以轻松获取到尾部结点的位置。对于循环双链表的插入、删除操作也无需区分位置操作的情况，这是由于循环双链表的本身的特殊性，使p.next.pre永远不可能为null，因此我们在插入和删除时代码实现相对简单些。下面我们先分析一下循环双链表的插入操作，图示如下：

我们可以看出（a）（b）（c）三种情况都无需关系位置插入的区别，其代码实现如下：

/*** 根据index插入* 循环链表中无论是prev还是next都不存在空的情况,因此添加时* 无论是头部还是尾部还是中,都视为一种情况对待* @param index* @param data* @return*/@Overridepublicbooleanadd(intindex, Tdata) {
intsize=length();
if(data==null||index<0||index>=size)
returnfalse;
intj=0;
DNode<T>p=this.head;
//寻找插入点的位置while (p.next!=head&&j<index){
p=p.next;
j++;
    }
//创建新结点,如果index=3,那么插入的位置就是第4个位置DNode<T>q=newDNode<>(data,p,p.next);
p.next=q;
p.next.prev=q;
returntrue;
}

循环双链表的删除操作图示如下：

同样地，从图中我们也可以发现由于循环双链表的特性，（a）（b）（c）三种情况都无需区分操作位置，其代码实现如下：

@OverridepublicTremove(intindex) {
Told=null;
intsize=length();
if (index<0||index>=size)
returnold;
intj=0;
DNode<T>p=this.head.next;
while (p!=head&&j<index)
    {
j++;
p=p.next;
    }
if (p!=head)
    {
old=p.data;
p.prev.next=p.next;
p.next.prev=p.prev;
    }
returnold;
}

排序循环双链表的实现

所谓的排序循环双链表指的是在插入元素时，不再根据index标志，而是根据值的大小寻找插入位置，但是有个插入值data必须是T或者T的父类而且实现了Comoarable接口。排序循环双链表的实现比较简单，我们只需继承前面的循环双链表并重写add方法即可，主要代码实现如下：

publicclassSortLoopHeadDIlinkedList<TextendsComparable<?extendsT>>extendsLoopHeadDILinkedList<T> {
/*** 顺序插入* @param data* @return*/@Overridepublicbooleanadd(Tdata) {
if(data==null||!(datainstanceofComparable))
thrownewNullPointerException("data can\'t be null or data instanceof Comparable must be true");
Comparablecmp=data;//这里需要转一下类型,否则idea编辑器上检验不通过.//如果data值比最后一个结点大,那么直接调用父类方法,在尾部添加.if(this.isEmpty() ||cmp.compareTo(this.head.prev.data) >0){
returnsuper.add(data);
      }
DNode<T>p=this.head.next;
//查找插入点while (p!=head&&cmp.compareTo(p.data)>0)
p=p.next;
DNode<T>q=newDNode<>(data,p.prev,p);
p.prev.next=q;
p.prev=q;
returntrue;
  }
publicstaticvoidmain(String[] args){
SortLoopHeadDIlinkedList<Integer>list=newSortLoopHeadDIlinkedList<>();
list.add(50);
list.add(40);
list.add(80);
list.add(20);
System.out.println("init list-->"+list.toString());
  }
}