疯狂java笔记之线性表

从数据的逻辑结构来分，数据元素之间存在的关联关系被称为数据的逻辑结构。归纳起来，应用程序中的数据大致哟如下四种基本的逻辑结构。

• 集合：数据元素之间只有“同属于一个集合”的关系
• 线性结构：数据元素之间存在一个对一个的关系
• 树形结构：数据元素之间存在一个对多个的关系
• 图状结构或网状结构：数据元素之间存在多个对多个关系 对于数据不同的逻辑结构，在底层通常有两种物理存储结构。
• 顺序存储结构
• 链式存储结构

线性表的定义及逻辑结构

线性表（LinearList）是由n(n>=0)个数据元素(节点)a1,a2,a3,...,an组成的有限序列。

线性表中每个元素必须具有相同的结构(即拥有相同的数据项).线性表是线性结构中最常用而又最简单的一种数据结构。

线性表中每个数据元素其实可以包含若千个数据项，例如，使用ai来代表线性表中的第i个元素，其中ai元素可以包含若千个数据项。关干线性表还可以有如下定义。

• 线性表中包含的数据元素个数n被称为表的长度，当线性表的长度为0是该表也被称为空表。
• 当n>0时，表可以表示为(a1,a2,a3,...,an)

对于一个非空，有限的线性表而言，它总具有如下特征。

• 总存在唯一的“第一个”数据元素。
• 总存在唯一的“最后一个”数据元素。
• 除第一个数据元素外，集合中的每一个数据元素都只有一个前驱的数据元素。
• 除了最后一个数据元素外，集合中的每个数据元素都只有一个后继的数据元素。

线性表的基本操作

如果需要实现一个线性表，程序首先需要确定该线性表的每个数据元素。接下来，应该为该线性表实现如下基本操作。

• 初始化：通常是一个构造器，用于创建一个空的线性表
• 返回线性表的长度：该方法用于返回线性表中的数据元素
• 获取指定索引处的元素:根据索引返回线性表的数据元素
• 按值查找数据元素的位置：如果线性表中存在一个或多个与查找值相等的数据元素，那么该方法返回一个搜索到的值相等的数据元素的索引，否则返回-1.
• 直接插入数据元素：向线性表的头部插入一个数据元素，线性表长度+1；
• 向指定位置插入数据元素:向线性表的指定索引处插入一个数据元素，线性表长度+1.
• 直接删除数据元素：删除线性表头部的数据元素，线性表长度-1.
• 删除线性表中指定位置的数据元素：删除线性表中指定索引处的数据元素，线性表长度-1.
• 判断线性表是否为空：该方法判断线性表是否为空，如果线性表为空，则返回true,否则返回false
• 清空线性表：将线性表清空

顺序存储结构

线性表的顺序存储结构是指用一组地址连续的存储单元依次存放线性表的元素。当程序采用顺序存储结构来实现线性表时，线性表中相邻元素的两个元素ai和ai+1对应的存储地址loc(ai)和loc(ai+1)也是相邻的。

换句话说，顺序结构线性表中数据元素的物理关系和逻辑关系是一致的，线性表中数据元素的存储地址可按如下公式计算。

loc(ai)=loc(a0)+i*b(0<i<n)

上面公式中b代表每个数据元素的存储单元。从上面公式可以看出，程序获取线性表中每个元素的存储起始地址的时间相同，读取表中数据元素的时间也相同。而且顺序表中每个元素都可随机存取，因此顺序存储的线性表时一种随机存取的存储结构。

为了使用顺序结构实现线性表，程序通常会采用数组来保存线性表中的数据元素。

线性表的插入运算是指表的第i(0<=i<n)个位置插入一个新的数据元素x,是长度为n的线性表：

a0,...,ai-1,ai,...,an-1

变成长度为n+1的线性表：

a0,...,ai-1,x,ai,...,an-1 向顺序结构的线性表插入元素，如图所示：

linear.PNG

这里有一个要考虑的问题。由于顺序结构线性表底层采用数组来存储数据元素，因此插入数据元素是必须保证不会超出底层属猪的容量。如果线性表中元素的个数超出了底层数据的长度，那么就必须为该线性表扩充底层数据的长度。

线性表的删除运算是指将表的第i(0<=i<n)个位置的数据元素删除，使长度为n的线性表：

a0,...,ai-1,ai,ai+1,...,an-1

变成长度为n-1的线性表：

a0,...,ai-1,ai+1,...,an-1

从顺序结构的线性表中删除元素，如下图：

linear2.PNG

链式存储结构

链式存储结构的线性表（简称为链表）将采用一组地址任意的存储单元存放线性表中的数据元素。链式存储结构的线性表不会按线性的逻辑顺序来保存数据元素，他需要在每个数据元素里保存一个引用下一个数据元素的引用（或者叫指针）。

由于不是必须按顺序存储，链表在插入，删除数据元素时比顺序线性表块的多，当时查找一个节点或者访问特点节点编号的节点则比顺序线性表慢得多。

使用链表结构可以克服顺序线性表(基于数组)需要预先知道数据大小的缺点，链表结构可以充分利用计算机的内存空间，实现灵活的内存动态管理。但是链表结构失去了数组随机存取的优点，同时链表由于增加了节点的指针域，空间开销比较大。

对于链表存储结构的线性表而言，它的每个节点都必须包含数据元素本身和一个或两个用来引用上一个/下一个节点的引用。也就是说，有如下公式：

节点=数据元素+引用下一个节点的引用+引用上一个节点的引用

如下图是双向链表节点示意图，其中每个节点中的prev代表前一个节点的引用，只有双向链表的节点才存在prev引用。

enty.PNG

链表是多个相互引用的节点的集合，这个链表总是从头节点开始，然后依次向后指向每个节点。

空链表就是头节点为null的链表

单链表上的基本运算

单链表指定是每个节点保留一个引用，改引用指向当前节点的下一个节点，没有引用指向头节点，尾节点的next引用为null.单链表示意图如下：

one_linked.PNG

对于单链表，系统建立单链表的过程就是不断添加节点的过程。动态添加单链表有以下两种方式。

• 头插法建表：该方法从一个空表开始，不断地创建新节点，将数据元素存入节点的data域中，然后不断地以新节点为头节点，让新节点指向原有的头节点
• 尾插法建表：该方法是将新节点插入到当前链表的表尾上，因此需要为链表定义一个引用变量来保存链表的最后一个节点。

头插法建立链表虽然算法简单，但生成的链表中节点的次序和输入的顺序相反:若希望二者次序一致，则应该采用尾插法来建立链表。

对于单链表而言，常用的操作有：

1. 查找
2. 插入
3. 删除

1.查找操作

单链表的查找操作可以分为以下两种：

• 按序号查找第index个节点:从header节点依次向下在单链表中查找第index个节点口算法为，设header为头，current为当前节点(初始时current从heade，开始)，0为头节点序号，i为计数器，则可使current依次下移寻找节点，并使i同时递增记录节点序号，直到返回指定节点。
• 在链表中查找指定的element元素:查找是否有等于给定值element的节点。若有，则返回首次找到的其值为element的节点的索引;否则，返回-l。查找过程从开始节点出发，顺着链表逐个将节点的值和给定值element做比较。

2.插入操作

插入操作时将值为element的新节点插入到链表的第index个节点的位置上。因此，首先找到索引的index-1的节点，然后生成一个数据域为element的新节点newNode，并令idnex-1处节点的next引用新节点，新节点的next引用原来index处的节点。

向i索引处插入节点的示意图。

insert_linked.PNG

3.删除操作

删除操作是将链表的第index个节点删去。因为在单链表中，第index个节点是有index-1处的节点引用的，因此删除index处节点将先获取index-1处节点，然后index-1处节点的next引用到原index+1处的节点，并释放index处节点即可。

delete_linked.PNG

循环链表

循环链表是一种首尾相接的链表。将单链表的尾节点next指针改为引用单链表header节点，这个单链表就成了循环链表。

循环链表具有一个显著特征：链表的任一个节点出发均可找到表中的其他所有节点，因此，循环链表可以被视为“无头无尾”,如下图：

recycler_linked.PNG

循环链表中的第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得它实现了很多方法时会更容易，在这样的链表上设计算法会比普通链表更加容易。

新加入的节点应该是在第一个节点之前（采用头插法插入），还是最后一个节点之后（采用尾插法插入），可以根据实际要求灵活处理，具体的实现区别不大。

双向链表

如果为每个节点保留两个引用prev和next,让prev指向当前节点的上一个节点，让next指向当前节点的下一页节点，此时的链表既可以向后依次访问每个节点，也可以向前依次访问节点，这种形式的链表被称为双向链表。示意图如下：

double_linked.PNG

双向链表是一种对称结构，它克服了单链表上指针单向性的缺点，其中每个节点既可以向前引用，也可以向后引用，这样可以更方便地插入、删除数据元素。

与单链表类似的是，如果将链表的header节点与tail节点链在一起就构成了双向循环链表。

双向链表的查找

由于双向链表既可以从header节点开始依次向后搜索每个节点，也可以从tail节点开始依次向前搜索每个节点，因此当程序试图从双向链表中搜索指定索引处的节点时，既可以从该链表的header节点开始搜索，也可以从该链表的tail节点开始搜索。至于到底应该从header开 始搜索，还是应该从tail开始搜索，则取决于被搜索节点是更靠近header，还是更靠近tail.

一般来说，可以通过被搜索index的值来判断它更靠近header还是更靠近tail.如果index<size/2，则可判断该位置更靠近header，应从header开始搜索;反之，则可判断该位置更靠近tail，那就应从tail开始搜索口

双向链表的插入

双向链表的插入操作更复杂，向双向链表中插入一个新节点必须同时修改两个方向的指针（即引用）。如下图所示：

insert_double_linked.PNG

双向链表的删除

在双向链表中，删除一个节点需要同时修改两个方向的指针，双向链表中删除节点的操作，如下图所示：

delete_double_linked.PNG

线性表的分析

线性表的顺序的顺序和链式两种实现各有优势：如下

线性表的功能

线性的本质上是一个充当容器的工具类，当程序有一组结构相同的数据元素需要保存时，就可以考虑使用线性表来保存它们。

从某种程度来说，线性表是数组的加强，线性表比数据多了如下几个功能：

• 线性表的长度可以动态改变，而java数组的长度是固定的 -线性表可以插入元素，而数组无法插入元素
• 线性表可以删除元素，而数组无法删除元素，数组只能将指定元素赋为null,但各种元素依然存在
• 线性表提供方法来搜索指定元素的位置，而数组一般不提供该方法
• 线性表提供方法来清空所有元素的位置，而数组一般不提供该方法

从上面线性表的实现能发珑线性表比数组功能强大的理由是，顺序结构的线性表可以说是包装过的数组，自然会提供更多额外的方法来简化操作。

对于大部分,Java程序员来说，其实经常在使用线性表List. Java的List接口就代表了线性表，线性表的两种实现分别是ArrayList和LinkedList其中LinkedList还是一个双向链表。JDK提供的线性表有如下图：

listtype.PNG