数据结构：线性表

线性表的定义案例线性表的存储结构顺序存储结构链式存储结构 总结

线性表的定义

线性表（List）：零个或多个数据元素的有限序列。

数学定义：若将线性表记为（$a_1,a_2,\cdots ,a_{i-1},a_i,a_{i+1},\cdots ,a_n$）,则表中$a_{i-1}$领先于$a_i$，$a_i$领先于$a_{i+1}$, 称$a_{i-1}$是$a_i$的直接前驱元素，$a_{i+1}$是$a_i$的直接后继元素。当i=1,2,⋯,n-1时，$a_i$有且仅有一个直接后继，当i=2,3,⋯,n时,$a_i$有且仅有一个直接前驱。

案例

A B C D E

上图为一个线性表，其中长度为5，注意当一个线性表长度为0的时候，成为空表。

鼠 牛 虎 兔

在复杂的线性表中，一个数据元素可以由若干个数据项组成。如上图，每种动物都有自己的特点，都有自己的数据项。

线性表的存储结构

顺序存储结构

线性表的顺序存储结构：用一段连续的地址存储单元，依次的把线性表的数据元素存储起来的的结构。 在Java中，ArrayList就是用到了这种结构： 先看声明的变量

//存储空间的初始分配量 private static final int DEFAULT_CAPACITY = 10; //初始化存储空间，默认空表 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //当前数组，用来存储数据元素。说明ArrayList底层就是一个数组。 transient Object[] elementData; //线性表当前长度或者数组当前长度 private int size;

线性表顺序存储结构的插入

/** * 把element的数据元素插入到index的下标中 */ public void add(int index, E element) { //如果下标大于最大和长度或者下标小于0抛异常。 if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); //计算是否要扩容 ensureCapacityInternal(size + 1); //将elementData数组的index的下表开始，把size - index个数据复制到elementData的index+1开始的下标上。 System.arraycopy(elementData, index, elementData, index + 1, size - index); //用数组下标赋值，即插入数组 elementData[index] = element; size++;//长度加一 }

线性表顺序存储结构的删除

/** * 删除下标为index的元素，并返回移除的元素 * */ public E remove(int index) { //如果下标大于长度，抛异常 if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); //计数器 modCount++; //获取数组中下标为index的元素 E oldValue = (E) elementData[index]; //要copy的数组的长度 int numMoved = size - index - 1; if (numMoved > 0) //将elementData数组的index+1的下表开始，把numMoved个数据复制到elementData的index开始的下标上。 System.arraycopy(elementData, index+1, elementData, index,numMoved); //把最后的下标置为空 elementData[--size] = null; // clear to let GC do its work //最后返回移除的数据 return oldValue; }

线性表顺序存储结构的删除

//根据下标直接返回数组元素 public E get(int index) { if (index < 0 || index >= this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); if (ArrayList.this.modCount != this.modCount) throw new ConcurrentModificationException(); return (E) ArrayList.this.elementData[offset + index]; }

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

优点缺点1、无须为表中的逻辑关系增加额外的存储空间1、插入与删除需要移动大量的元素2、可以快速的插入与删除2、当线性表长度变化较大的时候，难以确定存储空间的容量3、造成存储空间的“碎片”

链式存储结构

对数据元素$a_i$来说，除 了有本身的数据域外，还需要存储一个直接指向后继的存储位置的指示器。这个指示器叫指针。

包含数据域跟指针的数据元素称为节点。

由n个节点连接成一个链表，称为线性表的链式存储结构，每个节点包含两个指针，一个指向前驱节点，一个指向后继节点的链表称为双向链表。

在Java中LinkList就是用到了这种结构：

节点

/** * LinkedList<E> 中的内部类定义的节点 **/ private static class Node<E> { E item;//数据域 LinkedList.Node<E> next;//指向上一个节点的指针 LinkedList.Node<E> prev;//指向下一个节点的指针 Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) { this.item = var2;//数据域 this.next = var3;//指向后继节点的指针 this.prev = var1;//指向前驱节点的指针 } }

双向链表定义

transient int size;//两边长度 transient LinkedList.Node<E> first;//链表的头节点 transient LinkedList.Node<E> last;//链表的尾节点

双向链表插入

/** * 把数据var2 插入到 链表的var1位置上 **/ public void add(int var1, E var2) { //检查插入的位置是否合适>0,并且<size this.checkPositionIndex(var1); if (var1 == this.size) { //插入末尾 this.linkLast(var2); } else { //插入中间 this.linkBefore(var2, this.node(var1)); } } //要把var1的节点插入到var2后 void linkBefore(E var1, LinkedList.Node<E> var2) { //获取var2的前一节点并赋值var3 LinkedList.Node var3 = var2.prev; //创建数据域为var1的节点var4 ，并把指针var3作为前驱节点，var2作为后继节点 LinkedList.Node var4 = new LinkedList.Node(var3, var1, var2); //var2的前驱节点为var4 var2.prev = var4; //var3 为空，表示var2为头结点，则新节点var4就作为头结点 if (var3 == null) { this.first = var4; } else { //var3的后继节点为var4 var3.next = var4; } //链表长度加1 ++this.size; //计数器加1 ++this.modCount; }

如下图 双向链表删除

//移除链表中为var1的元素，返回是否移除成功标识 public boolean remove(Object var1) { LinkedList.Node var2; //如果移除的元素为空 if (var1 == null) { //从头结点开始遍历 for(var2 = this.first; var2 != null; var2 = var2.next) { //数据域为空移除 if (var2.item == null) { this.unlink(var2); return true; } } } else { //从头结点开始遍历 for(var2 = this.first; var2 != null; var2 = var2.next) { //数据域为空移除 if (var1.equals(var2.item)) { //移除 this.unlink(var2); return true; } } } return false; } //移除var1节点 E unlink(LinkedList.Node<E> var1) { Object var2 = var1.item;//获取数据域 LinkedList.Node var3 = var1.next;//获取节点的后继节点 LinkedList.Node var4 = var1.prev;//获取前驱节点 //如果前驱节点为空，这表示var1就是头结点，这时要把var1移除的话，就把var1的后继节点var3 当做头结点。 if (var4 == null) { this.first = var3; } else { var4.next = var3;//把原节点var1的前驱元素var4的后继节点不再指向var1而是指向var1的后继节点var3。 var1.prev = null;//把原节点var1的前驱节点置为空。 } //如果后继节点为空，这表示var1就是尾结点，这时要把var1移除的话，就把var1的后继节点var4 当做尾结点。 if (var3 == null) { this.last = var4; } else { var3.prev = var4;//把原节点var1的后继元素var3的前驱节点不再指向var1而是指向var1的前驱节点var4。 var1.next = null;//把原节点var1的后继节点置为空。 } //把原节点var1的数据域置为空 var1.item = null; --this.size;//长度减一 ++this.modCount;//计数器加一 return var2;//返回原节点var1的数据域 }

如下图所示 线性表链式存储结构查找

//获取下表为var1的节点 public E get(int var1) { //检查下标异常情况 this.checkElementIndex(var1); //返回节点的数据域 return this.node(var1).item; } //根据下标查找节点 LinkedList.Node<E> node(int var1) { LinkedList.Node var2; int var3; //二分法思想，下标在0到size/2之间则从链表头开始遍历 if (var1 < this.size >> 1) { var2 = this.first; for(var3 = 0; var3 < var1; ++var3) { var2 = var2.next; } return var2; } else { var2 = this.last; //二分法思想，下标在size/2到size之间则从链表尾开始遍历 for(var3 = this.size - 1; var3 > var1; --var3) { var2 = var2.prev; } return var2; } }

线性表链式存储结构的优缺点：

优点缺点在插入和删除的操作时，只需要修改指针，不需要移动其他元素，效率高不需要提前分配空间，但查找元素需要遍历整个链表，效率低

总结

若线性表需要频繁查找，很少插入与删除的操作时，应该使用顺序存储结构（ArrayList）。若需要频繁插入或者删除时，应该考虑链式存储结构（LinkList）。 当线性表中的元素个数变化较大或者根本不知道多大时，最好使用链式存储结构，这样就不需要考虑存储空间的大小问题。

本文主要参考《大话数据结构》

下一节 数据结构：栈