datas

数据结构⼀线性表（顺序表、单链表、双链表）

版权声明：本⽂为openXu原创⽂章，未经博主允许不得以任何形式转载

⽂章⽬录

1、线性表及其逻辑结构

  线性表是最简单也是最常⽤的⼀种数据结构。英⽂字母表（A、B、…、Z）是⼀个线性表，表中每个英⽂字母是⼀个数据元素；成绩单

是⼀个线性表，表中每⼀⾏是⼀个数据元素，每个数据元素⼜由学号、姓名、成绩等数据项组成。

1.1线性表的定义

  线性表是具有相同特性的数据元素的⼀个有限序列。线性表⼀般表⽰为：

      L=(a1,a2,…,ai,ai+1,…,an)

  线性表中元素在位置上是有序的，这种位置上有序性就是⼀种线性关系，⽤⼆元组表⽰：

L=(D,R)

D={ai|1≤i≤n,n≥0}

R={r}

r={|1≤i≤n-1}

1.2线性表的抽象数据类型描述

  将线性表数据结构抽象成为⼀种数据类型，这个数据类型中包含数据元素、元素之间的关系、操作元素的基本算法。对于基本数据类型

（int、float、boolean等等）java已经帮我们实现了⽤于操作他们的基本运算，我们需要基于这些基本运算，为我们封装的⾃定义数据类

型提供操作它们的算法。⽐如数组就是⼀种被抽象出来的线性表数据类型，数组⾃带很多基本⽅法⽤于操作数据元素。

  Java中的List我们经常会使⽤到，但是很少关注其内部实现，List是⼀个接⼝，⾥⾯定义了⼀些抽象的⽅法，其⽬的就是对线性表的抽

象，其中的⽅法就是线性表的⼀些常⽤基本运算。⽽对于线性表的不同存储结构其实现⽅式就有所不同了，⽐如ArrayList是对线性表顺序

存储结构的实现，LinkedList是线性表链式存储结构的实现等。存储结构没有确定我们就不知道数据怎么存储，但是对于线性表这种逻辑结

构中数据的基本操作我们可以预知，⽆⾮就是获取长度、获取指定位置的数据、插⼊数据、删除数据等等操作，可以参考List。

  对于本系列⽂章，只是对数据结构和⼀些常⽤算法学习，接下来的代码将选择性实现并分析算法。对线性表的抽象数据类型描述如下：

/**

*autour:openXu

*date:2018/7/1315:41

*className:IList

*version:1.0

*description:线性表的抽象数据类型

*/

publicinterfaceIList{

/**

*判断线性表是否为空

*@return

*/

booleanisEmpty();

/**

*获取长度

*@return

*/

intlength();

/**

/**

*将结点添加到指定序列的位置

*@paramindex

*@paramdata

*@return

*/

booleanadd(intindex,Tdata);

/**

*将指定的元素追加到列表的末尾

*@paramdata

*@return

*/

booleanadd(Tdata);

/**

*根据index移除元素

*@paramindex

*@return

*/

Tremove(intindex);

/**

*移除值为data的第⼀个结点

*@paramdata

*@return

*/

booleanremove(Tdata);

/**

*移除所有值为data的结点

*@paramdata

*@return

*/

booleanremoveAll(Tdata);

/**

*清空表

*/

voidclear();

/**

*设置指定序列元素的值

*@paramindex

*@paramdata

*@return

*/

Tt(intindex,Tdata);

/**

*是否包含值为data的结点

*@paramdata

*@return

*/

booleancontains(Tdata);

/**

*根据值查询索引

*@paramdata

*@return

*/

intindexOf(Tdata);

/**

*根据data值查询最后⼀次出现在表中的索引

*@paramdata

*@return

*/

intlastIndexOf(Tdata);

/**

*获取指定序列的元素

*@paramindex

*@paramindex

*@return

*/

Tget(intindex);

/**

*输出格式

*@return

*/

StringtoString();

}

2、线性表的顺序存储结构

2.1顺序表

  把线性表中的所有元素按照其逻辑顺序依次存储在计算机存储器中指定存储位置开始的⼀块连续的存储空间中。在Java中创建⼀个数组

对象就是分配了⼀块可供⽤户使⽤的连续的存储空间，该存储空间的起始位置就是由数组名表⽰的地址常量。线性表的顺序存储结构是利⽤

数组来实现的。

在Java中，我们通常利⽤下⾯的⽅式来使⽤数组：

int[]array=newint[]{1,2,3};//创建⼀个数组

(array,0);//获取数组中序列为0的元素

(array,0,1);//设置序列为0的元素值为1

  这种⽅式创建的数组是固定长度的，其容量⽆法修改，当array被创建出来的时候，系统只为其分配3个存储空间，所以我们⽆法对其

进⾏添加和删除操作。Array这个类⾥⾯提供了很多⽅法⽤于操作数组，这些⽅法都是静态的，所以Array是⼀个⽤于操作数组的⼯具类，这

个类提供的⽅法只有两种：get和t，所以只能获取和设置数组中的元素，然后对于这两种操作，我们通常使⽤array[i]、array[i]=0的简

化⽅式，所以Array这个类⽤的⽐较少。

  另外⼀种数组ArrayList，其内部维护了⼀个数组，所以本质上也是数组，其操作都是对数组的操作，与上述数组不同的是，ArrayList

是⼀种可变长度的数组。既然数组创建时就已经分配了存储空间，为什么ArrayList是长度可变的呢？长度可变意味着可以从数组中添加、

删除元素，向ArrayList中添加数据时，实际上是创建了⼀个新的数组，将原数组中元素⼀个个复制到新数组后，将新元素添加进来。如果

ArrayList仅仅做了这么简单的操作，那他就不应该出现了。ArrayList中的数组长度是⼤于等于其元素个数的，当执⾏add()操作时⾸先会

检查数组长度是否够⽤，只有当数组长度不够⽤时才会创建新的数组，由于创建新数组意味着⽼数据的搬迁，所以这个机制也算是利⽤空间

换取时间上的效率。但是如果添加操作并不是尾部添加，⽽是头部或者中间位置插⼊，也避免不了元素位置移动。

2.2顺序表基本运算的实现

/**

*autour:openXu

*date:2018/7/1110:45

*className:LinearArray

*version:1.0

*description:线性表的顺序存储结构（顺序表），是由数组来实现的

*/

publicclassLinearArrayimplementsIList{

privateObject[]datas;

/**

*通过给定的数组建⽴顺序表

*@paramobjs

*@return

*/

publicstaticLinearArraycreateArray(T[]objs){

LinearArrayarray=newLinearArray();

LinearArrayarray=newLinearArray();

=newObject[];

for(inti=0;i<;i++)

[i]=objs[i];

returnarray;

}

privateLinearArray(){

}

@Override

publicbooleanisEmpty(){

==0;

}

@Override

publicintlength(){

;

}

/**

*获取指定位置的元素

*分析：时间复杂度O(1)

*从顺序表中检索值是简单⾼效的，因为顺序表内部采⽤数组作为容器，数组可直接通过索引值访问元素

*/

@Override

publicTget(intindex){

if(index<0||index>=)

thrownewIndexOutOfBoundsException();

return(T)datas[index];

}

/**

*为指定索引的结点设置值

*分析：时间复杂度O(1)

*/

@Override

publicTt(intindex,Tdata){

if(index<0||index>=)

thrownewIndexOutOfBoundsException();

ToldValue=(T)datas[index];

datas[index]=data;

returnoldValue;

}

/**

*判断是否包含某值只需要判断该值有没有出现过

*分析：时间复杂度O(n)

*/

@Override

publicbooleancontains(Tdata){

returnindexOf(data)>=0;

}

/**

*获取某值第⼀次出现的索引

*分析：时间复杂度O(n)

*/

@Override

publicintindexOf(Tdata){

if(data==null){

for(inti=0;i<;i++)

if(datas[i]==null)

returni;

}el{

for(inti=0;i<;i++)

if((datas[i]))

returni;

}

return-1;

}

}

/**

*获取某值最后⼀次出现的索引

*分析：时间复杂度O(n)

*/

@Override

publicintlastIndexOf(Tdata){

if(data==null){

for(inti=-1;i>=0;i--)

if(datas[i]==null)

returni;

}el{

for(inti=-1;i>=0;i--)

if((datas[i]))

returni;

}

return-1;

}

/**

*指定位置插⼊元素

*分析：时间复杂度O(n)

*在数组中插⼊元素时，需要创建⼀个⽐原数组容量⼤1的新数组，

*将原数组中(0,index-1)位置的元素拷贝到新数组，指定新数组index位置元素值为新值，

*继续将原数组(index,length-1)的元素拷贝到新数组

*@paramindex

*@paramdata

*@return

*/

@Override

publicbooleanadd(intindex,Tdata){

if(index>||index<0)

thrownewIndexOutOfBoundsException();

Objectdestination[]=newObject[+1];

opy(datas,0,destination,0,index);

destination[index]=data;

opy(datas,index,destination,index

+1,-index);

datas=destination;

returntrue;

}

/**

*在顺序表末尾处插⼊元素

*分析：时间复杂度O(n)

*同上⾯⼀样，也需要创建新数组

*@paramdata

*@return

*/

@Override

publicbooleanadd(Tdata){

Objectdestination[]=newObject[+1];

opy(datas,0,destination,0,);

destination[]=data;

datas=destination;

returntrue;

}

/**

*有序表添加元素

*@paramdata

*@return

*/

publicbooleanaddByOrder(intdata){

intindex=0;

//找到顺序表中第⼀个⼤于等于data的元素

while(index<&&(int)datas[index]

while(index<&&(int)datas[index]

index++;

if((int)datas[index]==data)//不能有相同元素

returnfal;

Objectdestination[]=newObject[+1];

opy(datas,0,destination,0,index);

//将datas[index]及后⾯元素后移⼀位

opy(datas,index,destination,index+1,-index);

destination[index]=data;

datas=destination;

returntrue;

}

/**

*移除指定索引的元素

*分析：时间复杂度O(n)

*此处由于数组元素数量-1，所以需要创建新数组。

*ArrayList由于是动态数组（()≠），所以只需要将删除的元素之后的前移⼀位

*@paramindex

*@return

*/

@Override

publicTremove(intindex){

if(index>=||index<0)

thrownewIndexOutOfBoundsException();

ToldValue=(T)datas[index];

fastRemove(index);

returnoldValue;

}

/**

*删除指定值的第⼀个元素

*@paramdata

*@return

*/

@Override

publicbooleanremove(Tdata){

if(data==null){

for(intindex=0;index<;index++)

if(datas[index]==null){

fastRemove(index);

returntrue;

}

}el{

for(intindex=0;index<;index++)

if((datas[index])){

fastRemove(index);

returntrue;

}

}

returnfal;

}

/**

*移除指定序列的元素

*@paramindex

*/

privatevoidfastRemove(intindex){

Objectdestination[]=newObject[-1];

opy(datas,0,destination,0,index);

opy(datas,index+1,destination,index,

-index-1);

datas=destination;

}

@Override

publicbooleanremoveAll(Tdata){

returnfal;

}

@Override

publicvoidclear(){

datas=newObject[]{};

}

@Override

publicStringtoString(){

if(isEmpty())

return"";

Stringstr="[";

for(inti=0;i<;i++){

str+=(datas[i]+",");

}

str=ing(0,dexOf(","));

returnstr+"]";

}

}

算法分析：

插⼊元素：

删除元素：

3、线性表的链式存储结构

  顺序表必须占⽤⼀整块事先分配⼤⼩固定的存储空间，这样不便于存储空间的管理。为此提出了可以实现存储空间动态管理的链式存储

⽅式–链表。

3.1链表

  在链式存储中，每个存储结点不仅包含元素本⾝的信息（数据域），还包含元素之间逻辑关系的信息，即⼀个结点中包含有直接后继结

点的地址信息，这称为指针域。这样可以通过⼀个结点的指针域⽅便的找到后继结点的位置。

  由于顺序表中每个元素⾄多只有⼀个直接前驱元素和⼀个直接后继元素。当采⽤链式存储时，⼀种最简单也最常⽤的⽅法是：

  在每个结点中除包含数据域外，只设置⼀个指针域⽤以指向其直接后继结点，这种构成的链接表称为线性单向链接表，简称单链表。

  另⼀种⽅法是，在每个结点中除包含数值域外，设置两个指针域，分别⽤以指向直接前驱结点和直接后继结点，这样构成的链接表称为

线性双向链接表，简称双链表。

  单链表当访问⼀个结点后，只能接着访问它的直接后继结点，⽽⽆法访问他的直接前驱结点。双链表则既可以依次向后访问每个结点，

也可以依次向前访问每个结点。

单链表结点元素类型定义：

publicclassLNode{

protectedLNodenext;//指针域，指向直接后继结点

protectedObjectdata;//数据域

}

双链表结点元素类型定义：

publicclassDNode{

protectedDNodeprior;//指针域，指向直接前驱结点

protectedDNodenext;//指针域，指向直接后继结点

protectedObjectdata;//数据域

}

  在顺序表中，逻辑上相邻的元素，对应的存储位置也相邻，所以进⾏插⼊或删除操作时，通常需要平均移动半个表的元素，这是相当费

时的操作。

  在链表中，每个结点存储位置可以任意安排，不必要求相邻，插⼊或删除操作只需要修改相关结点的指针域即可，⽅便省时。对于单链

表，如果要在结点p之前插⼊⼀个新结点，由于通过p并不能找到其前驱结点，我们需要从链表表头遍历⾄p的前驱结点然后进⾏插⼊操作，

这样时间复杂度就是O(n)，⽽顺序表插⼊删除结点时间复杂度也是O(n)，那为什么说链表插⼊删除操作更加⾼效呢？因为单链表插⼊删除

操作所消耗的时间主要在于查找前驱结点，这个查找⼯作的时间复杂度为O(n)，⽽真正超如删除时间为O(1)，还有顺序表需要移动结点，

移动结点通常⽐单纯的查找更加费时，链表不需要连续的空间，不需要扩容创建新表，所以同样时间复杂度O(n)，链表更适合插⼊和删除操

作。对于遍历查找前驱结点的问题，在双链表中就能很好的解决，双链表在已知某结点的插⼊和删除操作时间复杂度是O(1)。

  由于链表的每个结点带有指针域，从存储密度来讲，这是不经济的。所谓存储密度是指结点数据本⾝所占存储量和整改结点结构所占存

储量之⽐。

3.2单链表基本运算的实现

/**

*autour:openXu

*date:2018/7/1115:48

*className:LinkList

*version:1.0

*description:单链表基本实现

*/

publicclassLinkListimplementsIList{

publicLNodehead;//单链表开始结点

/**

*1.1创建单链表（头插法：倒序）

*解：遍历数组，创建新结点，新结点的指针域指向头结点，让新结点作为头结点

*时间复杂度O(n)

*@paramarray

*@return

*/

publicstaticLinkListcreateListF(T[]array){

LinkListllist=newLinkList();

if(array!=null&&>0){

for(Tobj:array){

LNodenode=newLNode();

=obj;

=;

=node;

}

}

returnllist;

}

/**

*1.2创建单链表（尾插法：顺序）

*解：

*时间复杂度O(n)

*@paramarray

*@return

*/

publicstaticLinkListcreateListR(T[]array){

LinkListllist=newLinkList();

if(array!=null&&>0){

=newLNode();

=array[0];

LNodetemp=;

for(inti=1;i<;i++){

LNodenode=newLNode();

=array[i];

=node;

temp=node;

}

}

returnllist;

}

/**

*判断单链表是否为空表

*时间复杂度O(1)

*@return

*/

@Override

publicbooleanisEmpty(){

returnhead==null;

}

/**

*4获取单链表长度

*时间复杂度O(n)

*@return

*/

@Override

publicintlength(){

if(head==null)

return0;

intl=1;

LNodenode=head;

while(!=null){

l++;

node=;

}

returnl;

}

@Override

publicvoidclear(){

head=null;

}

@Override

publicTt(intindex,Tdata){

returnnull;

}

@Override

publicbooleancontains(Tdata){

returnfal;

}

@Override

publicTget(intindex){

returngetNode(index).data;

}

/**

*6.1获取指定索引的结点

*时间复杂度O(n)

*@paramindex

*@return

*/

publicLNodegetNode(intindex){

LNodenode=head;

intj=0;

while(j

j++;

node=;

}

returnnode;

}

/**

*6.2获取指定数据值结点的索引

*时间复杂度O(n)空间复杂度O(1)

*@paramdata

*@return

*/

@Override

publicintindexOf(Tdata){

if(head==null)

return-1;//没有此结点

LNodenode=head;

intj=0;

while(node!=null){

if((data))

returnj;

j++;

node=;

}

return-1;

}

@Override

publicintlastIndexOf(Tdata){

if(head==null)

return-1;

intindex=-1;

LNodenode=head;

intj=0;

while(node!=null){

if((data)){

index=j;

}

j++;

node=;

}

returnindex;

}

/**

*6.3单链表中的倒数第k个结点（k>0）

*解：先找到顺数第k个结点，然后使⽤前后指针移动到结尾即可

*时间复杂度O(n)空间复杂度O(1)

*@paramk

*@return

*/

publicLNodegetReNode(intk){

if(head==null)

returnnull;

intlen=length();

if(k>len)

returnnull;

LNodetarget=head;

LNodenext=head;

for(inti=0;i

next=;

while(next!=null){

target=;

next=;

}

returntarget;

}

/**

*6.4查找单链表的中间结点

*时间复杂度O(n)空间复杂度O(1)

*@return

*/

publicLNodegetMiddleNode(){

if(head==null||==null)

returnhead;

LNodetarget=head;

LNodetemp=head;

while(temp!=null&&!=null){

target=;

temp=;

}

returntarget;

}

/**

*2.1将单链表合并为⼀个单链表

*解：遍历第⼀个表，⽤其尾结点指向第⼆个表头结点

*时间复杂度O(n)

*@return

*/

publicstaticLNodemergeList(LNodehead1,LNodehead2){

if(head1==null)returnhead2;

if(head2==null)returnhead1;

LNodeloop=head1;

while(!=null)//找到list1尾结点

loop=;

=head2;//将list1尾结点指向list2头结点

returnhead1;

}

/**

*2.1通过递归，合并两个有序的单链表head1和head2

*

*解：两个指针分别指向两个头结点，⽐较两个结点⼤⼩，

*⼩的结点指向下⼀次⽐较结果（两者中较⼩），最终返回第⼀次递归的最⼩结点

*@paramhead1

*@paramhead2

*@return

*/

publicstaticLNodemergeSortedListRec(LNodehead1,LNodehead2){

if(head1==null)returnhead2;

if(head2==null)returnhead1;

if(((int))>((int))){

=mergeSortedListRec(,head1);

returnhead2;

}el{

=mergeSortedListRec(,head2);

returnhead1;

}

}

/**

*3.1循环的⽅式将单链表反转

*时间复杂度O(n)空间复杂度O(1)

*/

publicvoidreverListByLoop(){

if(head==null||==null)

return;

LNodepre=null;

LNodenex=null;

while(head!=null){

nex=;

=pre;

pre=head;

head=nex;

}

head=pre;

}

/**

*3.2递归的⽅式将单链表反转,返回反转后的链表头结点

*时间复杂度O(n)空间复杂度O(n)

*/

publicLNodereverListByRec(LNodehead){

if(head==null||==null)

returnhead;

LNodereHead=reverListByRec();

=head;

=null;

returnreHead;

}

/**

*5.1获取单链表字符串表⽰

*时间复杂度O(n)

*/

@Override

publicStringtoString(){

if(head==null)

return"";

LNodenode=head;

StringBufferbuffer=newStringBuffer();

while(node!=null){

(+"->");

node=;

}

ng();

}

publicstaticStringdisplay(LNodehead){

if(head==null)

return"";

LNodenode=head;

StringBufferbuffer=newStringBuffer();

while(node!=null){

("->"+);

node=;

}

ng();

}

/**

*5.2⽤栈的⽅式获取单链表从尾到头倒叙字符串表⽰

*解：由于栈具有先进后出的特性，现将表中的元素放⼊栈中，然后取出就倒序了

*时间复杂度O(n)空间复杂度O(1)

*@return

*/

publicStringdisplayReverStack(){

if(head==null)

return"";

Stackstack=newStack<>();//堆栈先进先出

LNodehead=;

while(head!=null){

(head);

head=;

head=;

}

StringBufferbuffer=newStringBuffer();

while(!y()){

//pop()移除堆栈顶部的对象，并将该对象作为该函数的值返回。

("->"+().data);

}

ng();

}

/**

*5.3⽤递归的⽅式获取单链表从尾到头倒叙字符串表⽰

*@return

*/

publicvoiddisplayReverRec(StringBufferbuffer,LNodehead){

if(head==null)

return;

displayReverRec(buffer,);

("->");

();

}

/**

*7.1插⼊结点

*解：先找到第i-1个结点，让创建的新结点的指针域指向第i-1结点指针域指向的结点，

*然后将i-1结点的指针域指向新结点

*时间复杂度O(n)空间复杂度O(1)

*@paramdata

*@paramindex

*/

@Override

publicbooleanadd(intindex,Tdata){

if(index==0){//插⼊为头结点

LNodetemp=newLNode();

=head;

returntrue;

}

intj=0;

LNodenode=head;

while(j

j++;

node=;

}

if(node==null)

returnfal;

LNodetemp=newLNode();//创建新结点

=data;

=;//新结点插⼊到Index-1结点之后

=temp;

returntrue;

}

@Override

publicbooleanadd(Tdata){

LNodenode=head;

while(node!=null&&!=null)//找到尾结点

node=;

LNodetemp=newLNode();//创建新结点

=data;

=temp;

returnfal;

}

@Override

publicTremove(intindex){

LNodenode=deleteNode(index);

returnnode==null?null:;

returnnode==null?null:;

}

/**

*7.2删除结点

*解：让被删除的结点前⼀个结点的指针域指向后⼀个结点指针域

*时间复杂度O(n)空间复杂度O(1)

*@return

*/

publicLNodedeleteNode(intindex){

LNodenode=head;

if(index==0){//删除头结点

if(node==null)

returnnull;

head=;

returnnode;

}

//⾮头结点

intj=0;

while(j

j++;

node=;

}

if(node==null)

returnnull;

LNodedelete=;

if(delete==null)

returnnull;//不存在第index个结点

=;

returndelete;

}

@Override

publicbooleanremove(Tdata){

returnfal;

}

@Override

publicbooleanremoveAll(Tdata){

returnfal;

}

/**

*7.3给出⼀单链表头指针head和⼀节点指针delete，要求O(1)时间复杂度删除节点delete

*解：将delete节点value值与它下个节点的值互换的⽅法，

*但是如果delete是最后⼀个节点，需要特殊处理，但是总得复杂度还是O(1)

*@return

*/

publicstaticvoiddeleteNode(LNodehead,LNodedelete){

if(delete==null)

return;

//⾸先处理delete节点为最后⼀个节点的情况

if(==null){

if(head==delete)//只有⼀个结点

head=null;

el{

//删除尾结点

LNodetemp=head;

while(!=delete)

temp=;

=null;

}

}el{

=;

=;

}

return;

return;

}

/**

*8.1判断⼀个单链表中是否有环

*解：使⽤快慢指针⽅法，如果存在环，两个指针必定指向同⼀结点

*时间复杂度O(n)空间复杂度O(1)

*@return

*/

publicstaticbooleanhasCycle(LNodehead){

LNodep1=head;

LNodep2=head;

while(p1!=null&&p2!=null){

p1=;//⼀次跳⼀步

p2=;//⼀次跳两步

if(p2==p1)

returntrue;

}

returnfal;

}

/**

*8.2、已知⼀个单链表中存在环，求进⼊环中的第⼀个节点

*利⽤hashmap，不要⽤ArrayList，因为判断ArrayList是否包含某个元素的效率不⾼

*@paramhead

*@return

*/

publicstaticLNodegetFirstNodeInCycleHashMap(LNodehead){

LNodetarget=null;

HashMapmap=newHashMap<>();

while(head!=null){

if(nsKey(head)){

target=head;

break;

}el{

(head,true);

head=;

}

}

returntarget;

}

/**

*8.3、已知⼀个单链表中存在环，求进⼊环中的第⼀个节点,不⽤hashmap

*⽤快慢指针，与判断⼀个单链表中是否有环⼀样，找到快慢指针第⼀次相交的节点，

*此时这个节点距离环开始节点的长度和链表头距离环开始的节点的长度相等

*参考/fankongkong/p/

*@paramhead

*@return

*/

publicstaticLNodegetFirstNodeInCycle(LNodehead){

LNodefast=head;

LNodeslow=head;

while(fast!=null&&!=null){

slow=;

fast=;

if(slow==fast)

break;

}

if(fast==null||==null)

returnnull;//判断是否包含环

//相遇节点距离环开始节点的长度和链表投距离环开始的节点的长度相等

slow=head;

while(slow!=fast){

slow=;

fast=;

fast=;

}//同步⾛

returnslow;

}

/**

*9、判断两个单链表是否相交,如果相交返回第⼀个节点，否则返回null

*①、暴⼒遍历两个表，是否有相同的结点(时间复杂度O(n²))

*②、第⼀个表的尾结点指向第⼆个表头结点，然后判断第⼆个表是否存在环，但不容易找出交点（时间复杂度O(n)）

*③、两个链表相交，必然会经过同⼀个结点，这个结点的后继结点也是相同的（链表结点只有⼀个指针域，后继结点只能有⼀个），

*所以他们的尾结点必然相同。两个链表相交，只能是前⾯的结点不同，所以，砍掉较长链表的差值后同步遍历，判断结点是否相同，相同的就是交点了

。

*时间复杂度（时间复杂度O(n)）

*@paramlist1

*@paramlist2

*@return交点

*/

publicstaticLNodeisInterct(LinkListlist1,LinkListlist2){

LNodehead1=;

LNodehead2=;

if(head1==null||head2==null)returnnull;

intlen1=();

intlen2=();

//砍掉较长链表的差值

if(len1>=len2){

for(inti=0;i

head1=;

}

}el{

for(inti=0;i

head2=;

}

}

//同步遍历

while(head1!=null&&head2!=null){

if(head1==head2)

returnhead1;

head1=;

head2=;

}

returnnull;

}

}

算法分析

判断⼀个单链表中是否有环（尾结点指向过往结点）：

  我们可以通过HashMap判断，遍历结点，将结点值放⼊HashMap，如果某⼀刻发现当前结点在map中已经存在，则存在环，并且此

结点正是环的⼊⼝，此算法见8.2⽅法。但是有⼀种问法是不通过任何其他数据结构怎么判断单链表是否存在环。

  这样我们可利⽤的就只有单链表本⾝，⼀种解法是通过快慢指针，遍历链表，⼀个指针跳⼀步（慢指针步长为1），另⼀个指针跳两步

（快指针步长为2），如果存在环，这两个指针必将在某⼀刻指向同⼀结点，假设此时慢指针跳了n步，则快指针跳的步数为n/2步：

判断两个单链表是否相交：

  由于单链表的特性（只有⼀个指针域），如果两个表相交，那必定是Y形相交，不会是X形相交，如图所⽰。两个单链表后⾯的结点相

同，不同的部分只有前⾯，砍掉较长的链表的前⾯部分，然后两个链表同步遍历，必将指向同⼀个结点，这个结点就是交点：

3.3双链表

  双链表中每个结点有两个指针域，⼀个指向其直接后继结点，⼀个指向其直接前驱结点。

  建⽴双链表也有两种⽅法，头插法和尾插法，这与创建单链表过程相似。在双链表中，有些算法如求长度、取元素值、查找元素等算法

与单链表中相应算法是相同的。但是在单链表中，进⾏结点插⼊和删除时涉及前后结点的⼀个指针域的变化，⽽双链表中结点的插⼊和删除

操作涉及前后结点的两个指针域的变化。java中LinkedList正是对双链表的实现，算法可参考此类。

双链表基本运算的实现

/**

*autour:openXu

*date:2018/7/1115:48

*className:LinkList

*version:1.0

*description:双链表基本实现

*/

publicclassDLinkListimplementsIList{

transientDNodefirst;//双链表开始结点

transientDNodelast;//双链表末端结点

privateintsize;//结点数

/**

*创建单链表（头插法：倒序）

*时间复杂度O(n)

*@paramarray

*@return

*/

publicstaticDLinkListcreateListF(T[]array){

DLinkListdlist=newDLinkList();

if(array!=null&&>0){

=;

for(Tobj:array){

DNodenode=newDNode();

=obj;

=;

if(!=null)

=node;//相⽐单链表多了此步

=node;//相⽐单链表多了此步

el

=node;

=node;

}

}

returndlist;

}

/**

*1.2创建单链表（尾插法：顺序）

*时间复杂度O(n)

*@paramarray

*@return

*/

publicstaticDLinkListcreateListR(T[]array){

DLinkListdlist=newDLinkList();

if(array!=null&&>0){

=;

=newDNode();

=array[0];

=;

for(inti=1;i<;i++){

DNodenode=newDNode();

=array[i];

=node;

=;//相⽐单链表多了此步

=node;

}

}

returndlist;

}

@Override

publicbooleanisEmpty(){

returnsize==0;

}

@Override

publicintlength(){

returnsize;

}

/**2添加结点*/

@Override

publicbooleanadd(intindex,Tdata){

if(index<0||index>size)

thrownewIndexOutOfBoundsException();

DNodenewNode=newDNode();

=data;

if(index==size){//在末尾添加结点不需要遍历

finalDNodel=last;

if(l==null)//空表

first=newNode;

el{

=newNode;

=l;

}

last=newNode;

size++;

}el{

//其他位置添加结点需要遍历找到index位置的结点

DNodeindexNode=getNode(index);

DNodepred=;

=pred;

=indexNode;

=newNode;

if(pred==null)

first=newNode;

el

=newNode;

size++;

}

returnfal;

}

@Override

publicbooleanadd(Tdata){

returnadd(size,data);

}

/**3删除结点*/

@Override

publicTremove(intindex){

if(index<0||index>=size)

thrownewIndexOutOfBoundsException();

returnunlink(getNode(index));

}

@Override

publicbooleanremove(Tdata){

if(data==null){

for(DNodex=first;x!=null;x=){

if(==null){

unlink(x);

returntrue;

}

}

}el{

for(DNodex=first;x!=null;x=){

if(()){

unlink(x);

returntrue;

}

}

}

returnfal;

}

@Override

publicbooleanremoveAll(Tdata){

booleanresult=fal;

if(data==null){

for(DNodex=first;x!=null;x=){

if(==null){

unlink(x);

result=true;

}

}

}el{

for(DNodex=first;x!=null;x=){

if(()){

unlink(x);

result=true;

}

}

}

returnresult;

}

/**

*将指定的结点解除链接

*@paramx

*@return

*/

privateTunlink(DNodex){

//asrtx!=null;

finalTelement=;

finalDNodenext=;

finalDNodeprev=;

if(prev==null){

first=next;

}el{

=next;

=null;

}

if(next==null){

last=prev;

}el{

=prev;

=null;

}

=null;

size--;

returnelement;

}

/**

*清空

*/

@Override

publicvoidclear(){

for(DNodex=first;x!=null;){

DNodenext=;

=null;

=null;

=null;

x=next;

}

first=last=null;

size=0;

}

/**

*设置结点值

*@paramindex

*@paramdata

*@return

*/

@Override

publicTt(intindex,Tdata){

if(index<0||index>=size)

thrownewIndexOutOfBoundsException();

DNodex=getNode(index);

ToldVal=;

=data;

returnoldVal;

}

/**

*判断是否存在结点值

*@paramdata

*@return

*/

@Override

publicbooleancontains(Tdata){

returnindexOf(data)!=-1;

}

/**

*检索结点值

*@paramdata

*@return

*/

@Override

publicintindexOf(Tdata){

intindex=0;

if(data==null){

for(DNodex=first;x!=null;x=){

if(==null)

returnindex;

index++;

}

}el{

for(DNodex=first;x!=null;x=){

if(())

returnindex;

index++;

}

}

return-1;

}

@Override

publicintlastIndexOf(Tdata){

intindex=size;

if(data==null){

for(DNodex=last;x!=null;x=){

index--;

if(==null)

returnindex;

}

}el{

for(DNodex=last;x!=null;x=){

index--;

if(())

returnindex;

}

}

return-1;

}

@Override

publicTget(intindex){

if(index<0||index>=size)

thrownewIndexOutOfBoundsException();

returngetNode(index).data;

}

/**

*获取指定索引的结点

*解：由于双链表能双向检索，判断index离开始结点近还是终端结点近，从近的⼀段开始遍历

*时间复杂度O(n)

*@paramindex

*@return

*/

privateDNodegetNode(intindex){

if(index<(size>>1)){

DNodex=first;

for(inti=0;i

x=;

returnx;

}el{

DNodex=last;

for(inti=size-1;i>index;i--)

x=;

returnx;

}

}

/**

*倒序

*遍历每个结点，让=;=(此值需要体现保存);

*/

publicvoidrever(){

last=first;//反转后终端结点=开始结点

DNodenow=first;

DNodenext;

while(now!=null){

next=;//保存当前结点的后继结点

=;

=next;

first=now;

now=next;

}

}

@Override

publicStringtoString(){

if(size==0)

return"";

DNodenode=first;

StringBufferbuffer=newStringBuffer();

("");

while(node!=null){

(+"->");

node=;

}

("nextnpre");

node=last;

intstart=();

LogUtil.i(getClass().getSimpleName(),"buffer长度："+());

while(node!=null){

(start,"<-"+);

node=;

}

ng();

}

}

算法分析

  双链表与单链表不同之处在于，双链表能从两端依次访问各个结点。单链表相对于顺序表优点是插⼊、删除数据更⽅便，但是访问结点

需要遍历，时间复杂度为O(n)；双链表就是在单链表基础上做了⼀个优化，使得访问结点更加便捷（从两端），这样从近的⼀端出发时间复

杂度变为O(n/2)，虽然不是指数阶的区别，但也算是优化。双链表在插⼊、删除结点时逻辑⽐单链表稍⿇烦：

3.4循环链表

  循环链表是另⼀种形式的链式存储结构，它的特点是表中尾结点的指针域不再是空，⽽是指向头结点，整个链表形成⼀个环。由此，从

表中任意⼀结点出发均可找到链表中其他结点。如图所⽰为带头结点的循环单链表和循环双链表：

4、有序表

  所谓有序表，是指所有结点元素值以递增或递减⽅式排列的线性表，并规定有序表中不存在元素值相同的结点。

  有序表可以采⽤顺序表和链表进⾏存储，若以顺序表存储有序表，其算法除了add(Tdata)以外，其他均与前⾯说的顺序表对应的运算

相同。有序表的add(Tdata)操作不是插⼊到末尾，⽽需要遍历⽐较⼤⼩后插⼊相应位置。

publicbooleanaddByOrder(intdata){

intindex=0;

//找到顺序表中第⼀个⼤于等于data的元素

while(index<&&(int)datas[index]

index++;

if((int)datas[index]==data)//不能有相同元素

returnfal;

Objectdestination[]=newObject[+1];

opy(datas,0,destination,0,index);

//将datas[index]及后⾯元素后移⼀位

opy(datas,index,destination,index+1,-index);

destination[index]=data;

datas=destination;

returntrue;

}