共计 1383 个字符，预计需要花费 4 分钟才能阅读完成。
既然咱们这一节要说的是线性表与链表的内容，那么必定要对数据结构的概念有一个意识。首先，数据结构个别分为逻辑构造、物理构造，逻辑构造指的是数据对象元素之间的互相关系，物理构造个别指的是数据的存储构造。逻辑构造次要包含汇合构造、线性构造、树形构造、图形构造，物理构造次要有链式存储和线性存储。在数据结构的剖析过程中，逻辑构造和物理构造是一种相辅相成的关系。
线性表的数据存储地位都是独立的、并且一个地位紧跟着下一个地位，在第 0 个地位上存储的数据是 a1、第一个地位上是 a2、以此类推，直到最初一个数据 an。如果说，要删除其中的一个数据 a2、那么紧接着 a3 就会挪动到原来 a2 的地位、a4 就会挪动到 a3 的地位，以至于最初 a2 之后的每一个数据都要向前挪动一位，这也就使得线性存储的数据在删除的过程中效率会变得比拟低。反之，线性存储构造存储数据时都是顺序存储的，没有指针对地位的指引操作，它的查问速度是绝对比拟快的。
和线性存储构造不同的是，链式存储构造能够在自身的数量中附加变量、利用附加变量指向前一个或者后一个数据，在进行插入、删除操作时只有扭转数据的附加变量的指向就能够实现而不必扭转前后数据的存储地址。比方：如果同样是删除 a2 数据的状况，在删除 a2 数据后 a1 的向后附加变量就会指向 a3、a3 的向前附加变量就会指向 a1，这样一来并没有扭转 a2 数据当前的数据地位，只是扭转了 a1、a3 的附加变量的数据地位指向。
在 Java 语言中，比拟显著的线性表、链式表别离是 ArrayList、LinkedList，钻研过 JDK 源码应该晓得，这两种表别离都有的各自的增加、删除、查询方法，其两种表在实现这三种办法时也是截然不同的。上面咱们别离拿出 ArrayList、LinkedList 的 add() 办法进行比拟一下。留神：这里实例用的是 JDK1.8 源码展现。
// ArrayList 实现 add() 办法
public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// add() 办法没有指定增加的数据对象的地位
// 实现也比较简单，间接将数据对象赋值到数组中 // LinkedList 实现 add() 办法
public void add(int index, E element) {checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
} 本节就说到这里，免得大家视觉疲劳、源码局部有趣味的猿童鞋能够本人深入研究。下一节咱们看一下栈与队列的数据结构，记得关注后续更新、哈哈！
更多精彩微信公众号【老王说编程】>>>