一、线性表的顺序存储设计与实现（顺序表）

1.1   顺序存储结构的设计原理概要

顺序存储结构底层是利用数组来实现的，而数组可以存储具有相同数据类型的元素集合，，当我们创建一个数组时，计算机操作系统会为该数组分配一块连续的内存块，这也就意味着数组中的每个存储单元的地址都是连续的，因此只要知道了数组的起始内存地址就可以通过简单的乘法和加法计算出数组中第n-1个存储单元的内存地址，就如下图所示：

  通过上图可以发现为了访问一个数组元素，该元素的内存地址需要计算其距离数组基地址的偏移量，即用一个乘法计算偏移量然后加上基地址，就可以获得数组中某个元素的内存地址。其中c代表的是元素数据类型的存储空间大小，而序号则为数组的下标索引。

整个过程需要一次乘法和一次加法运算，因为这两个操作的执行时间是常数时间，所以我们可以认为数组访问操作能再常数时间内完成，即时间复杂度为O(1)，这种存取任何一个元素的时间复杂度为O(1)的数据结构称之为随机存取结构。而顺序表的存储原理正如上图所示，因此顺序表的定义如下（引用）：

线性表的顺序存储结构称之为顺序表(Sequential List),它使用一维数组依次存放从a0到an-1的数据元素(a0,a1,…,an-1)，将ai(0< i <> n-1)存放在数组的第i个元素，使得ai与其前驱ai-1及后继ai+1的存储位置相邻，因此数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。

1.2 顺序存储结构的实现分析

接着我们来分析一下顺序表的实现，先声明一个顺序表接口类SeqList，然后实现该接口并实现接口方法的代码，SeqList接口代码如下：

我们创建ArraySeqList一个顺序表实现这个接口。

private final Object[]EMPTY_ELEMENTDATA = {};

private final Object[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

private static final int DEFAULT_CAPACITY =10;

/*** * 元素的个数 */

private int size;

ArraySeqList的构造方法

无参构造方法，我们默认是空数组，有参构造构造方法中，我们新建一个长度为size的空数组。

get(int index) 实现分析 

从顺序表中获取值是一种相当简单的操作并且效率很高，这是由于顺序表内部采用了数组作为存储数据的容器。因此只要根据传递的索引值，然后直接获取数组中相对应下标的值即可，代码实现如下：

set(int index, T data) 实现分析

在顺序表中替换值也是非常高效和简单的，只要根据传递的索引值index找到需要替换的元素，然后把对应元素值替换成传递的data值即可，代码如下：

add(int index, T data)和add(T data)实现分析

在顺序表中执行插入操作时，如果其内部数组的容量尚未达到最大值时，可以归结为两种情况：一种是在头部插入或者中间插入，这种情况下需要移动数组中的数据元素，效率较低；另一种是在尾部插入，无需移动数组中的元素，效率高。

但是当顺序表内部数组的容量已达到最大值无法插入时，则需要申请另一个更大容量的数组并复制全部数组元素到新的数组，这样的时间和空间开销是比较大的，也就导致了效率更为糟糕了。

因此在插入频繁的场景下，顺序表的插入操作并不是理想的选择。下面是顺序表在数组容量充足下头部或中间插入操作示意图（尾部插入比较简单就不演示了）：

顺序表在数组容量充足下头部或中间插入操作示意图

顺序表在数组容量不充足的情况下头部或中间插入操作示意图

理解了以上几种顺序表的插入操作后，我们通过代码来实现这个插入操作如下。

每次插入元素之前，我们都应该判断数组是否够用，如果数组长度够用，就将index以后 的元素右移一位，然后将新元素添加到下标为index的位置。元素个数size++

数组长度不够的时候，元素的个数大于当前数组的长度时，我们就应该扩容数组。代码如下：

remove(int index) 实现分析

顺序表的删除操作和前的插入操作情况是类似的，如果是在中间或者头部删除顺序表中的元素，那么在删除位置之后的元素都必须依次往前移动，效率较低，如果是在顺序表的尾部直接删除的话，则无需移动元素，此情况下删除效率高。如下图所示在顺序表中删除元素ai时，ai之后的元素都依次往前移动：

删除操作的代码实现如下：

remove(E e) 实现分析

在顺序表中根据数据data找到需要删除的数据元素和前面分析的根据index删除顺序表中的数据元素是一样的道理，因此我们只要通过比较找到与data相等的数据元素并获取其下标，然后调用前面实现的remove(int index)方法来移除即可。代码实现如下：

源码实现：源码

1.3 顺序存储结构的效率分析

数组的访问操作能在常数时间内完成，即顺序表的访问操作(获取和修改元素值)的时间复杂为O(1)。

对于在顺序表中插入或者删除元素，从效率上则显得不太理想了，由于插入或者删除操作是基于位置的，需要移动数组中的其他元素，所以顺序表的插入或删除操作，算法所花费的时间主要是用于移动元素，如在顺序表头部插入或删除时，效率就显得相当糟糕了。若在最前插入或删除，则需要移动n（这里假设长度为n）个元素；若在最后插入或删除，则需要移动的元素为0。这里我们假设插入或删除值为第i(0）。

也就是说，在等概率的情况下，插入或者删除一个顺序表的元素平均需要移动顺序表元素总量的一半，其时间复杂度是O(n)。当然如果在插入时，内部数组容量不足时，也会造成其他开销，如复制元素的时间开销和新建数组的空间开销。

因此总得来说顺序表有以下优缺点：

优点

使用数组作为内部容器简单且易用；

在访问元素方面效率高；

数组具有内存空间局部性的特点，由于本身定义为连续的内存块，所以任何元素与其相邻的元素在物理地址上也是相邻的。

缺点

内部数组大小是静态的，在使用前必须指定大小，如果遇到容量不足时，需动态拓展内部数组的大小，会造成额外的时间和空间开销

在内部创建数组时提供的是一块连续的空间块，当规模较大时可能会无法分配数组所需要的内存空间

顺序表的插入和删除是基于位置的操作，如果需要在数组中的指定位置插入或者删除元素，可能需要移动内部数组中的其他元素，这样会造成较大的时间开销，时间复杂度为O(n)

二、线性表的链式存储设计与实现（链表）

2.1 链表的链式存储结构设计原理概要

通过前面对线性顺序表的分析，我们知道当创建顺序表时必须分配一块连续的内存存储空间，而当顺序表内部数组的容量不足时，则必须创建一个新的数组，然后把原数组的的元素复制到新的数组中，这将浪费大量的时间。而在插入或删除元素时，可能需要移动数组中的元素，这也将消耗一定的时间。

鉴于这种种原因，于是链表就出场了，链表在初始化时仅需要分配一个元素的存储空间，并且插入和删除新的元素也相当便捷，同时链表在内存分配上可以是不连续的内存，也不需要做任何内存复制和重新分配的操作，由此看来顺序表的缺点在链表中都变成了优势，实际上也是如此，当然链表也有缺点，主要是在访问单个元素的时间开销上，这个问题留着后面分析，我们先通过一张图来初步认识一下链表的存储结构，如下：

从图可以看出线性链表的存储结构是用若干个地址分散的存储单元存放数据元素的，逻辑上相邻的数据元素在物理位置上不一定相邻，因此每个存储单元中都会有一个地址指向域，这个地址指向域指明其后继元素的位置。在链表中存储数据的单元称为结点(Node)，从图中可以看出一个结点至少包含了数据域和地址域，其中数据域用于存储数据，而地址域用于存储前驱或后继元素的地址。

前面我们说过链表的插入和删除都相当便捷，这是由于链表中的结点的存储空间是在插入或者删除过程中动态申请和释放的，不需要预先给单链表分配存储空间的，从而避免了顺序表因存储空间不足需要扩充空间和复制元素的过程，提高了运行效率和存储空间的利用率。

2.2 单链表的储结构实现分析

同样地，先来定义一个顶级的链表接口:ILinkedList和存储数据的结点类Node，该类是代表一个最基本的存储单元，Node代码如下：

接着顶级的链表接口ILinkedList，该接口声明了我们所有需要实现的方法。

boolean isEmpty()实现分析

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

int length()实现分析

获取链表的长度，我们提供2种方法，第一种就是增加一个变量size，用它俩记录链表的长度。

第二种方法，因此我们只要遍历整个链表并获取结点的数量即可获取到链表的长度。遍历链表需要从头结点HeadNode开始，为了不改变头结点的存储单元，声明变量p指向当前头结点和局部变量length，然后p从头结点开始访问，沿着next地址链到达后继结点，逐个访问，直到最后一个结点，每经过一个结点length就加一，最后length的大小就是链表的大小。实现代码如下：

E get(int index)实现分析

在单链表中获取某个元素的值是一种比较费时间的操作，需要从头结点开始遍历直至传入值index指向的位置，其查询获取值的过程如下图所示：

代码如下：

T set(int index, T data)实现分析 

根据传递的index查找某个值并替换其值为data，其实现过程的原理跟get(int index)是基本一样的，先找到对应值所在的位置然后删除即可，不清晰可以看看前面的get方法的图解，这里直接给出代码实现：

add(int index, T data)实现分析 

单链表的插入操作分四种情况: 

a.空表插入一个新结点，插语句如下：

head=new Node(x,null);

b.在链表的表头插入一个新结点(即链表的开始处)，此时表头head!=null，因此head后继指针next应该指向新插入结点p，而p的后继指针应该指向head原来的结点，代码如下：

以上代码可以合并为如下代码：

执行过程如下图：

c.在链表的中间插入一个新结点p，需要先找到给定插入位置的前一个结点，假设该结点为front，然后改变front的后继指向为新结点p，同时更新新结点p的后继指向为front原来的后继结点，即front.next，其执行过程如下图所示：

代码实现如下：

d.在链表的表尾插入一个新结点(链表的结尾)在尾部插入时，同样需要查找到插入结点P的前一个位置的结点front（假设为front），该结点front为尾部结点，更改尾部结点的next指针指向新结点P，新结点P的后继指针设置为null，执行过程如下：

具体代码如下：

T remove(int index) 删除结点实现分析

在单向链表中，根据传递index位置删除结点的操作分3种情况，并且删除后返回被删除结点的数据：

a.删除链表头部（第一个）结点，此时需要删除头部head指向的结点，并更新head的结点指向，执行图示如下：

代码如下：

b.删除链表的中间结点，与添加是同样的道理，需要先找到要删除结点r（假设要删除的结点为r）位置的前一个结点front(假设为front)，然后把front.next指向r.next即要删除结点的下一个结点，执行过程如下：

代码如下：

void clear() 实现分析

清空链表是一件非常简单的事，直接将所有的节点置空。代码如下：

ok~,到此单链表主要的添加、删除、获取值、设置替换值、获取长度等方法已分析完毕，其他未分析的方法都比较简单这里就不一一分析了，单链表的整体代码最后会分享到github给大家。

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

带头结点的单链表

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

此时空链表的情况如下：

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

代码如下所示：

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

代码如下：

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

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

a.空单链表只有一个结点，head.next=null。

b.遍历的起点为p=head.next。

c.头部插入和头部删除无需改变head的指向。

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

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

下面看看根据index插入的代码实现，由于有了头结点，头部、中间、尾部插入无需区分操作位都视为一种情况处理。

代码如下：

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

ok~，关于带头结点的单向链表就分析到这，这里贴出实现源码，同样地，稍后在github上也会提供。。文章末尾提供下载地址。

循环单链表

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

此时的循环单链表有如下特点： 

a.当循环链表为空链表时，head指向头结点，head.next=head。 

b.尾部指向rear代表最后一个结点，则有rear.next=head。 

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

//从head.next开始遍历

Node item=head.next;

while (item!=null){

    item=item.next;

}

在循环单链表中改为如下判断：

Node p=head;

while (p!=head){

p=p.next;

}

具体代码实现，详见github地址，文章末尾给出。

查找CircleHeadILinkedList.java文件。

2.3 单链表的效率分析

由于单链表并不是随机存取结构，即使单链表在访问第一个结点时花费的时间为常数时间，但是如果需要访问第i(0），也就是说get(i)和set(i,x)的时间复杂度都为O(n)。

由于链表在插入和删除结点方面十分高效的，因此链表比较适合那些插入删除频繁的场景使用。如果是单链表的话，插入和删除的时间复杂度都是O(n)。

问题是大部分情况下查找所需时间比移动短多了，还有就是链表不需要连续空间也不需要扩容操作，因此即使时间复杂度都是O(n)，所以相对来说链表更适合插入删除操作。

GitHup源码地址

参考文章：顺序表和链表的深入分析。