本文详细介绍了Java线性表中基于的数组、链表的实现逻辑，并附有数组线性表、单链表、静态链表的Java实现案例。

线性表：零个或多个数据元素的有限序列。包括数组、链表、栈空间、队列等结构都属于线性表。

最基本的线性表描述为：线性表的数据对象集合为{a1,a2, ......,an}，除了最后一个元素an外，每一个元素有且只有一个直接后继元素数据，元素之间的关系是一对一的关系。随之数据结构的发展，后续还出现了更加复杂的线性表，它们可能会有其它特性，但是对于上面的基本特性都是遵守的。

上面的线性表是指的一种逻辑数据结构，而对于这种逻辑结构的实现，即物理结构，采用顺序储存结构和线性储存结构都能实现。关于顺序储存结构和线性储存结构以及数据结构的入门，可以看这篇博客：数据结构入门以及分类介绍。

1 线性表的顺序存储结构

1.1 线性表顺序存储结构概述

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表（a1,a2,......,an）的顺序存储示意图如下：

我们可以采用数组来实现线性表的顺序存储结构。把第一个数据元素存到数组下标为0的位置中，这个位置称为索引，接着把线性表相邻的元素存储在数组中相邻的位置。

数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。所谓的扩展一般是指新建一个更大的数组，并将原数组的元素复制到新数组中。

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

1.2 线性表顺序存储结构的查找

存储器中的每个存储单元都有自己的编号，这个编号称为地址。由于数组的储存单元是连续的，并且每一个数组元素的空间是一样大的，因此我们可以以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。

那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

1.3 线性表顺序存储结构的增删

基于数组的线性表的查找非常快，但是如果想在任意位置上添加或者删除数据，那么就很慢了。

向数组中i索引位置添加新数据时：

首先判断如果插入位置不合理，抛出异常；

如果插入后线性表长度大于等于数组长度，则抛出异常或动态增加容量；

遍历i索引处的后面的所有元素，分别将它们都向后移动一个位置；

将要插入元素填入索引i处，表长加1。

向数组中i索引位置删除新数据时：

如果删除位置不合理，抛出异常；

取出删除元素；

遍历i索引处的后面的所有元素，分别将它们都向前移动一个位置；

将原末位元素的值置为null；

表长减1。

从上面的步骤可以看出来，必须把目标位置后面的数据一个个前移或者后移，元素个数为n。

最好的情况，如果元素要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1)，因为不需要移动元素的。

最坏的情况，如果在数组头部添加或者删除元素，那就意味着要向后或者向前移动所有的元素，所以这个时间复杂度为O(n)。

平均的情况，最终平均移动次数和操作最中间的那个元素的移动次数相等，为(n-1)/2。

因此数组的添加、删除元素的时间复杂度为O(n)。

1.4 线性表顺序存储结构的优缺点

1.5 线性表顺序存储结构的简单实现

/***线性表的顺序储存结构的简单数组实现,为了演示方便,设计为不可扩展。*/publicclassMyFinalArrayList<E>{/***底层使用数组来存储数据*/privatefinalObject[]elements;/***当前存储的元素个数*/privateintsize;/***总容量,数组长度*/privatefinalintcapcity;/***构造器中初始化数组**@paramcapcity*/publicMyFinalArrayList(intcapcity){this.capcity=capcity;elements=newObject[capcity];}/***新增一个元素,默认加在线性表末位**@paramelement添加的元素*@return添加成功返回true，添加失败返回false*/publicbooleanadd(Eelement){//线性表是否容量已满if(size==capcity){//添加失败返回falsereturnfalse;}//添加元素到size索引，并且size自增1elements[size++]=element;//返回true，添加成功returntrue;}/***删除一个元素,默认删除线性表的首位**@return返回被删除的元素或者返回null*/publicEdelete(){//如果链表为空,则返回空if(size==0){returnnull;}//需要移动的元素的数量intlength=size-1;//将要被删除的元素Objecte=elements[0];//移动后续的全部元素System.arraycopy(elements,1,elements,0,length);//原最后一个元素的位置置空elements[--size]=null;return(E)e;}/***删除首个与输入元素相同的元素*/publicbooleandelete(Objectelement){if(size>0){for(intindex=0;index<size;index++){if(element==null){if(elements[index]==null){intnumMoved=size-index-1;System.arraycopy(elements,index+1,elements,index,numMoved);elements[--size]=null;returntrue;}}else{if(element.equals(elements[index])){intnumMoved=size-index-1;System.arraycopy(elements,index+1,elements,index,numMoved);elements[--size]=null;returntrue;}}}}returnfalse;}/***根据索引删除某个索引处的元素*/publicEdelete(intindex){rangeCheck(index);Ee=(E)elements[index];intnumMoved=size-index-1;if(numMoved>0){System.arraycopy(elements,index+1,elements,index,numMoved);}elements[--size]=null;returne;}/***更新某个索引的元素值*/publicvoidset(intindex,ObjectnewElement){rangeCheck(index);elements[index]=newElement;}/***是否包含某个元素**@paramelement元素*@returnfalse不包含true包含*/publicbooleancontains(Objectelement){if(size>0){for(intindex=0;index<size;index++){if(element==null){if(elements[index]==null){returntrue;}}else{if(element.equals(elements[index])){returntrue;}}}}returnfalse;}/***获取指定索引的元素**@paramindex指定索引*@return指定索引的元素*/publicEget(intindex){//检查索引越界rangeCheck(index);return(E)elements[index];}/***返回第一个元素**@return第一个元素,或者null没有元素*/publicEget(){if(size>0){return(E)elements[0];}returnnull;}/***返回指定元素出现的的首个位置索引**@paramelement制定元素*@return返回索引,或者-1,未找到该元素*/publicintindexOf(Objectelement){if(size>0){for(intindex=0;index<size;index++){if(element==null){if(elements[index]==null){returnindex;}}else{//默认通过equals比较元素是否相等if(element.equals(elements[index])){returnindex;}}}}//未找到元素,返回-1return-1;}/***返回线性表元素数量**@return线性表元素数量*/publicintsize(){returnsize;}/***重写了toString方法**@return*/@OverridepublicStringtoString(){if(size==0){return"[]";}StringBuilderstringBuilder=newStringBuilder();stringBuilder.append("[");for(inti=0;i<size;i++){stringBuilder.append(elements[i]);if(i!=size-1){stringBuilder.append(",");}}stringBuilder.append("]");returnstringBuilder.toString();}/***检查索引*/privatevoidrangeCheck(intindex){if(index>=size){//throw抛出异常thrownewIndexOutOfBoundsException("索引越界:"+index);}}}

1.5.1 测试

System.out.println("初始化线性表,容量为6===============>");MyFinalArrayList<Object>objectMyFinalList=newMyFinalArrayList<>(6);System.out.println("插入元素===============>");objectMyFinalList.add(null);objectMyFinalList.add(2);objectMyFinalList.add("3");objectMyFinalList.add("3");objectMyFinalList.add(null);objectMyFinalList.add("3");//尝试添加第七个元素,不会添加成功objectMyFinalList.add("6");//输出内部的元素System.out.println(objectMyFinalList);System.out.println("获取第一个元素===============>");//获取第一个元素Objecto=objectMyFinalList.get();System.out.println(o);System.out.println("获取size===============>");//获取sizeintsize1=objectMyFinalList.size();System.out.println(size1);System.out.println("删除第一个为null的元素===============>");booleandelete=objectMyFinalList.delete(null);System.out.println(delete);System.out.println("再次获取size===============>");intsize2=objectMyFinalList.size();System.out.println(size2);System.out.println("删除指定索引元素===============>");Objectdelete1=objectMyFinalList.delete(1);//索引越界//objectMyFinalList.delete(7);System.out.println(delete1);System.out.println("再次获取size===============>");intsize3=objectMyFinalList.size();System.out.println(size3);System.out.println("设置指定索引的元素值===============>");objectMyFinalList.set(0,"设置值1");System.out.println("获取该索引的元素值验证===============>");Objecto2=objectMyFinalList.get();System.out.println(o2);System.out.println("获取指定值所在的第一个索引===============>");intindex=objectMyFinalList.indexOf("3");System.out.println(index);System.out.println("输出全部元素===============>");System.out.println(objectMyFinalList);System.out.println("再次获取size===============>");intsize4=objectMyFinalList.size();System.out.println(size4);System.out.println("是否包含===============>");System.out.println(objectMyFinalList.contains(null));

2 线性表的链式存储结构

2.1 线性表链式存储结构概述

由于顺序存储结构元素相邻的特性，中间不能有空闲的内存空间。因此在插入和删除时为了保证元素相邻，就会涉及到大量元素的移动，这显然就需要耗费时间。 因此为了降低增删元素的时间复杂度，我们可以考虑链式存储结构。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元在内存空间中可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

但是为了保证不连续空间中的元素能够找到它们的前驱和后继，在链式结构元素的构成中，除了要存数据元素信息外，还要存储它的后继或者前驱元素的存储地址。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素的存储映像，称为结点。

n个结点链结成一个线性表，也称为链表。

如果链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

链表很好的解决了数组增、删元素的不足，因为当要在某个位置增删元素是，只需要修改相邻元素的指针指向新增加的元素就行了，不需要移动元素的位置。

2.2 单链表

下面先介绍最简单的单链表的操作。

2.2.1 单链表的查找

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。但在单链表中，因为数据都是分散存储的，所以如果想要访问数据，只能从第1个数据开始，顺着指针的指向一一往下访问（这便是顺序访问）。因此，对于单链表实现获取第i个元素的数据的操作，在算法上，相对要麻烦一些。

获得链表第i个索引数据的算法思路：

先判断i是否越界，i<0 || i>size ，如果越界则抛出异常。

然后声明一个变量f指向链表第一个结点，在循环中初始化j从0开始；

当j<i时，就遍历链表，让的指针向后移动，不断指向下一结点，即f=f.next，同时j自增1；

当循环结束，变量f指向的就是我们要找的第i个索引的数据。

说白了，就是从头开始找，直到第i+1个结点为止。我们把链表中的数据量记成n，由于这个算法的时间复杂度取决于i的位置，当i=0时，则不需遍历，第一个就取出数据了，而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。这样的查找也称为（线性查找）。

2.2.2 单链表的增删

在指定索引i处插入数据

先判断i是否越界，i<0 || i>size ，如果越界则抛出异常。

然后通过查找，找到原索引i的元素x，以及原索引i的前驱元素y。

构建一个新的节点z，新节点的后继元素指向原索引元素z.next=x

原索引i的前驱元素y的后继指向新的元素，y.next=z

在指定索引i处删除数据

先判断i是否越界，i<0 || i>size ，如果越界则抛出异常。

然后通过查找，找到原索引i的元素x，以及原索引i的前驱元素y，以及原索引i的后继元素z。

让y的next指向z，y.next=z

回收x

分析一下上面的单链表插入和删除算法，我们发现，它们其实都是由两部分组成：第一部分就是遍历查找i索引结点；第二部分就是插入和删除结点。

我们把链表中的数据量记成n，插入和删除数据只需要更改两个指针的指向，所以耗费的时间与n 无关。如果已经到达了添加数据的位置，那么添加操作只需花费O(1) 的时间。删除数据同样也只需O(1) 的时间。

虽然需要前期的查找时间，但是我们假设需要在索引i出插入10个元素，那么对于顺序存储结构意味着，每一次插入都需要移动n-i-1个结点，时间复杂度每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，针对插入和删除这两个操作，链表的时间复杂度都是O(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

2.2.3 单链表的简单实现

/***线性表的链式储存结构的简单单链表实现*/publicclassMySingleLinkedList<E>{/***空构造器,内部的节点均没有初始化,在第一次添加时才会初始化。*/publicMySingleLinkedList(){}/***元素个数*/privateintsize;/***指向头结点的引用*/privateNode<E>first;/***单链表内部的节点*/privatestaticclassNode<E>{//下一个结点的引用Node<E>next;//结点数据Edata;//节点构造器publicNode(Edata,Node<E>next){this.data=data;this.next=next;}}/***默认添加元素到单链表尾部*/publicvoidadd(Ee){//创建新节点Node<E>newNode=newNode<>(e,null);//如果头结点不为空if(first!=null){/*寻找尾节点*/Nodef=first;while(f.next!=null){f=f.next;}f.next=newNode;}else{//如果头结点为空,那么新节点就是第一个节点,就是头结点。first=newNode;}size++;}/***默认删除单链表头部元素*/publicEremove(){if(first==null){thrownewNoSuchElementException();}//如果头结点不为空Ee=first.data;first=first.next;size--;returne;}/***添加元素到单链表指定索引位置，原索引节点链接为next*/publicvoidadd(Ee,intindex){checkPositionIndex(index);//如果index等于0if(index==0){first=newNode<>(e,first);size++;return;}//如果index等于1if(index==1){first.next=newNode<>(e,first.next);size++;return;}if(index==size){add(e);return;}//暂时是头结点,循环结束后指向index索引节点Node<E>x=first;//index索引的前一个节点Node<E>y=null;for(inti=0;i<index;i++){x=x.next;if(i==index-2){y=x;}}//原index索引的前驱节点的next指向新节点,新节点的next节点指向原index索引节点y.next=newNode<>(e,x);size++;}/***删除单链表指定索引位置的元素*/publicEremove(intindex){checkElementIndex(index);if(index==0){returnremove();}//如果index等于1if(index==1){Ee=first.next.data;first.next=first.next.next;size--;returne;}//暂时是头结点,循环结束后指向index索引的节点的next节点Node<E>x=first;//index索引的前一个节点Node<E>y=null;//index索引的节点Node<E>z=null;for(inti=0;i<=index;i++){x=x.next;if(i==index-2){y=x;}if(i==index-1){z=x;}}y.next=x;Ee=z.data;size--;z=null;returne;}/***获取元素数量*/publicintsize(){returnsize;}@OverridepublicStringtoString(){StringBuilderstringBuilder=newStringBuilder();if(size>0){Node<E>f=first;stringBuilder.append("[");for(inti=0;i<size;i++){stringBuilder.append(f.data.toString());if(i!=size-1){stringBuilder.append(",");}f=f.next;}stringBuilder.append("]");returnstringBuilder.toString();}return"[]";}/***检查索引是否越界，用在删除、获取*/privatevoidcheckElementIndex(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException("索引越界");}}/***检查索引是否越界，用在添加*/privatevoidcheckPositionIndex(intindex){if(index<0||index>size){thrownewIndexOutOfBoundsException("索引越界");}}}

2.2.3.1 测试

MySingleLinkedList<Object>objectMySingleLinkedList=newMySingleLinkedList<>();objectMySingleLinkedList.add(111);objectMySingleLinkedList.add(222);objectMySingleLinkedList.add(333);System.out.println(objectMySingleLinkedList.remove(0));objectMySingleLinkedList.add(444,0);System.out.println(objectMySingleLinkedList);

2.3 静态链表

2.3.1 静态链表的概述

对于一些高级语言比如C，具有指针，Java、C#具有对象引用间接的实现了指针，因此可以使用指针或者对象引用建的实现单链表，但是对于如Basic、Fortran等早期的编程高级语言，由于没有指针/对象引用，链表结构按照前面我们的办法，它就没法实现了。

可以用对象数组代替指针实现链式存储结构，我们说链式存储结构的特点在于，存储位置可以不相邻，数据间的逻辑关系可以被描述，只要我们利用数组实现这两个需求，就可以达到用数组实现链式存储结构的目的。

对象数组中的对象就是链表中的节点，该节点包含两部分：数据域和指针域。数据域就是存放对象的，而这个“指针域”实际上存放的是下一个节点所在的数组元素的下标索引，利用数组的下标索引巧妙地当作指针，来查找下一个元素的位置，非常的巧妙。

为了实现类似单链表的申请、释放结点的功能，可以将这个数组分为两部分，一部分用来存储数据，另一部分作为备用空闲链表，这都是“逻辑上的链表”。备用链表，即连接各个空闲位置的链表，当存放数据时，从空闲列表的第一个空闲位置开始存放；当删除数据时，把指定索引处的数据删除。之后只需要修改“指针”——下标索引即可，不必再移动其他元素。

为了保存数组“数据链表”和“空闲链表”的“头指针”——起始索引，我们需要两个额外变量来存储。

2.3.2 静态链表的简单实现

/***静态链表的简单实现,为了简单,该实现的底层数组设计为不可扩展*/publicclassMyStaticLinkedList<E>{/***采用数组实现链式存储*/privatefinalNode<E>[]elements;/***容量*/privatefinalintcapcity;/***数据链表的头结点索引*/privateintdatafirst;/***空闲链表的头结点索引*/privateintfreefirst;/***元素个数*/privateintsize;/***构造器*/publicMyStaticLinkedList(intcapcity){if(capcity<=0){thrownewIllegalArgumentException("IllegalCapacity:"+capcity);}this.capcity=capcity;this.elements=newNode[capcity];}/***单链表内部的节点*/privatestaticclassNode<E>{//下一个结点的引用,这里采用数组下标索引来表示Integernext;//结点数据Edata;//节点构造器privateNode(Edata,Integernext){this.data=data;this.next=next;}@OverridepublicStringtoString(){return"Node{"+"next="+next+",data="+data+'}';}}/***默认添加元素到单链表尾部*@parame要添加的元素*@returntrue添加成功false添加失败*/publicbooleanadd(Ee){if(checkCapcity()){returnfalse;}//创建新节点Node<E>newNode=newNode(e,null);if(size==0){elements[freefirst]=newNode;freefirst=1;}else{//寻找尾节点Node<E>firstNode=elements[datafirst];while(firstNode.next!=null){firstNode=elements[firstNode.next];}firstNode.next=freefirst;elements[freefirst]=newNode;//寻找下一个空闲链表头部findFreeFirst();}size++;returntrue;}/***默认删除单链表头部元素*@return被删除的元素*/publicEremove(){if(size==0){returnnull;}else{Node<E>first=elements[datafirst];Ee=first.data;IntegernextIndex=first.next;if(nextIndex==null){datafirst=0;freefirst=0;elements[datafirst]=null;}else{elements[datafirst]=null;datafirst=nextIndex;//寻找下一个空闲链表头部findFreeFirst();}size--;returne;}}/***添加元素到链表指定索引位置，原索引节点链接为next*@parame要添加的元素*@paramindex指定索引*@returntrue添加成功false添加失败*/publicbooleanadd(Ee,intindex){checkPositionIndex(index);if(checkCapcity()){returnfalse;}if(index==size){add(e);}elseif(index==0){//新建节点elements[freefirst]=newNode<>(e,datafirst);//更新数据链表的头结点datafirst=freefirst;//寻找下一个空闲链表的头结点findFreeFirst();}else{//寻找指定节点的前一个节点Node<E>preNode=getNode(index-1);//新建节点elements[freefirst]=newNode<>(e,preNode.next);//改变"索引"preNode.next=freefirst;//寻找下一个空闲链表头部findFreeFirst();}size++;returntrue;}/***删除链表指定索引元素**@paramindex指定索引*@return被删除的元素*/publicEremove(intindex){checkElementIndex(index);if(size==0){returnnull;}elseif(index==0){returnremove();}else{//获取被删除元素的前一个前驱元素Node<E>preNode=getNode(index-1);//获取当前元素的索引IntegernodeIndex=preNode.next;Node<E>node=elements[nodeIndex];Edata=node.data;//改变"指针"preNode.next=node.next;//被删除的元素位置置空,让GC来回收elements[nodeIndex]=null;//调整空闲链表的头结点索引if(nodeIndex<freefirst){freefirst=nodeIndex;}size--;returndata;}}/***获取指定链表索引的元素**@paramindex索引*@return索引处的元素*/publicEget(intindex){checkElementIndex(index);returngetNode(index).data;}@OverridepublicStringtoString(){if(size==0){return"[]";}else{StringBuilderstringBuilder=newStringBuilder();Node<E>node=elements[datafirst];stringBuilder.append(node.data).append(",");while(node.next!=null){node=elements[node.next];stringBuilder.append(node.data);if(node.next!=null){stringBuilder.append(",");}}returnstringBuilder.toString();}}/****增强toString,用于测试*/publicStringtoStringAll(){StringBuilderstringBuilder=newStringBuilder();stringBuilder.append("[");for(inti=0;i<elements.length;i++){Node<E>node=elements[i];if(node!=null){stringBuilder.append(node.toString());}else{stringBuilder.append("null");}if(i!=elements.length-1){stringBuilder.append(",");}}stringBuilder.append("]");stringBuilder.append("{freefirst:").append(freefirst);stringBuilder.append(",datafirst:").append(datafirst);stringBuilder.append(",size:").append(size).append("}");returnstringBuilder.toString();}/***寻找下一个空闲链表头部*/privatevoidfindFreeFirst(){for(inti=0;i<elements.length;i++){if(elements[i]==null){freefirst=i;break;}}}/***获取指定位置的节点**@paramindex指定索引*@return节点*/privateNode<E>getNode(intindex){/*寻找节点*/Node<E>firstNode=elements[datafirst];for(inti=0;i<index;i++){firstNode=elements[firstNode.next];}returnfirstNode;}/***检查索引是否越界，用在删除、获取*/privatevoidcheckElementIndex(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException("索引越界");}}/***检查索引是否越界，用在添加*/privatevoidcheckPositionIndex(intindex){if(index<0||index>size){thrownewIndexOutOfBoundsException("索引越界");}}/***检查容量*/privatebooleancheckCapcity(){returnsize==capcity;}}

2.3.2.1 测试

MyStaticLinkedList<Object>objectMyStaticLinkedList=newMyStaticLinkedList<>(6);booleanadd2=objectMyStaticLinkedList.add(22);booleanadd3=objectMyStaticLinkedList.add(33);objectMyStaticLinkedList.remove();System.out.println(objectMyStaticLinkedList);booleanadd4=objectMyStaticLinkedList.add(44);System.out.println(objectMyStaticLinkedList);booleanadd5=objectMyStaticLinkedList.add("55");booleanadd6=objectMyStaticLinkedList.add("66");booleanadd7=objectMyStaticLinkedList.add("77");booleanadd8=objectMyStaticLinkedList.add("88");System.out.println(objectMyStaticLinkedList);objectMyStaticLinkedList.remove();System.out.println(objectMyStaticLinkedList);booleanadd9=objectMyStaticLinkedList.add("99");System.out.println(objectMyStaticLinkedList);objectMyStaticLinkedList.remove();System.out.println(objectMyStaticLinkedList);System.out.println(objectMyStaticLinkedList.get(3));System.out.println(objectMyStaticLinkedList.get(0));System.out.println(objectMyStaticLinkedList);objectMyStaticLinkedList.add(1,1);System.out.println(objectMyStaticLinkedList);Objectremove=objectMyStaticLinkedList.remove(0);System.out.println(remove);System.out.println(objectMyStaticLinkedList);Objectremove2=objectMyStaticLinkedList.remove(3);System.out.println(remove2);System.out.println(objectMyStaticLinkedList);System.out.println(objectMyStaticLinkedList.toStringAll());

2.4 循环链表

我们也可以在单链表尾部使用指针，并且让它指向链表头部的数据，将链表变成环形。这便是“循环链表”，也叫“环形链表”。循环链表没有头和尾的概念。想要保存数量固定的最新数据时通常会使用这种链表。

循环链表可以解决了一个很麻烦的问题：如何从当中一个结点出发，访问到链表的全部结点。

循环链表和单链表的主要差异就在于循环的判断条件上，单链表判断循环结束为：node->next==NULL;而循环链表判断循环结束为：（node->next）等于头结点。实际上循环链表是没有头结点的，这里的头结点只是人为设置的，相当于一个标记，当从“头结点”开始遍历，如果又回到了“头结点”，那么该循环链表就算遍历完毕了。

为了更方便的遍历循环链表，我们可以把指针指向“尾节点“，而不是“头结点”。

这样就能在O(1)时间内访问到,链表的头尾节点。

循环链表实际上还是比较简单的，再次就不给出实现案例了。

2.5 双向链表

在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度为O(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头开始遍历查找。

为了克服单向性这一缺点，我们可以把一个节点拥有的指针设定为两个，并且让它们分别指向该节点的前驱节点和后继节点，这就是“双向链表”。使用这种链表，不仅可以从前往后，还可以从后往前遍历数据，十分方便。

但是，双向链表存在两个缺点：一是指针数的增加会导致存储空间需求增加；二是添加和删除数据时需要改变更多指针的指向。

我们Java中的LinkedList集合就是双向链表，因此再次不在实现双向链表了。该结构也是比较简单的，去看LinkedList的源码就能很快知道怎么实现了。

单向循环链表则被用来解决约瑟夫环的问题。双向链表也可以有循环链表的变种，但是很少用到：头结点的prev指针指向尾节点，尾节点的next指针指向头结点。

3 总结

本次主要讲解了线性表的顺序 存储结构和链式存储结构的基本原理,并且均有相应的实现案例，比如采用数组实现线性表、单链表的实现、静态链表的实现，由于Linkedlist就是采用的双向链表实现的，因此并未给出双向链表的实现。可以看出来，线性表还算是一种非常简单的数据结构了，此外，还有栈、队列等特殊的线性表在本文中还未讲解，留待下次讲解。

作者：刘Java