算法：数组和链表-理论
我们先看看百度百科关于数组和链表的介绍吧。
数组
所谓数组，是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。
数组
既然我们刚刚讲到了算法的时间复杂度。
数组访问的时间复杂度是多少呢！O(1）。
数组插入和删除的时间复杂度呢！
下标保持，变量改变
插入：平均O(n)。
删除：平均O(n)。
Java的数组是怎么实现
那既然我们在学Java，那看看Java的数组是怎么实现的吧。
java.lang.reflect.Array类
可以看到，Array类构造方法是私有的，剩下的大部分是未实现的静态方法。
那我们看看有没有什么类继承Array类，找找API，发现并没有？
???三个问号，怎么没有呢！那我们Google看看。
先上链接，自己看会。我得到的信息是，这是一个java的规范，
Java里数组不是类，所以也没有对应的Class文件。数组类型是由JVM从元素类型合成出来的。
下面是个人猜测
我们知道，一个Java程序的运行，先要经过编译器生成字节码文件，JVM再读取字节码，生成机器码，最后到计算机运行。
int[] array = new int[n];既然数组不是一个类，那么生成字节码是
。。。
int[] list1;
descriptor: [I
flags:
。。。那么告诉JVM的是 int 一个整型数据类型，[] 是要一个连续的内存空间 。再把int值存入这个连续的存储空间中，这样就产生了一个常用数组。
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表
简单讲，就是一个当前的对象中，保存有下一个对象的引用。下一个对象保存有下下一个对象的引用。
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}Java的链表是怎么实现
LinkedList继承结构图
根据源码可以大概知道，我们先看看添加的方法。下面代码有注释，就不一一说了。
public class LinkedList<E>{
//添加
public boolean add(E e) {
linkLast(e);
return true;
}
//实际添加的方法
void linkLast(E e) {
final Node<E> l = last;//获取上一个节点
final Node<E> newNode = new Node<>(l, e, null);//获取当前添加元素的节点
last = newNode;//预先把当前节点保存为上一节点。 相当首节点的概念
if (l == null)//判断上一个节点是否为空/
first = newNode;
else//节点不为空
l.next = newNode;//设上一节点的下一个节点为当前添加的节点
size++;
modCount++;
}
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
transient Node<E> first;
transient Node<E> last;
transient int size = 0;
}这一篇文章为数组和链表的理论
数组和链表算法的实战为 ： 算法：数组和链表-实战