1.数组
数组能够顺序存储相同类型的多个数据，每个数据都有自己对应的索引。
在声明数组的时候需要制定数组的名称和它含有的数据的类型,创建数组的时候需要制定数组的长度：
double[] a;//声明
a = new double[10];//创建
1.1数组的扩容
数组一旦被创建，它的长度就是固定的,所以向数组中添加元素的时候，为了防止异常，往往都需要检测数组是否已经填满了，如果填满了需要对数组进行扩容，扩容一般分为两步：
- 1.新建一个数组，长度要大于旧数组。
- 2.将旧数组中的元素复制到新数组中。
以Android中的ArrayList为例：
ArrayList底层数据结构是数组，每次add的时候都会检测是否需要扩容，如下所示：
@Override public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
每次新创建一个ArrayList的时候，它的数组默认是EmptyArray.OBJECT（一个空数组），还有一个最小增长数MIN_CAPACITY_INCREMENT
/**
* The minimum amount by which the capacity of an ArrayList will increase.
* This tuning parameter controls a time-space tradeoff. This value (12)
* gives empirically good results and is arguably consistent with the
* RI's specified default initial capacity of 10: instead of 10, we start
* with 0 (sans allocation) and jump to 12.
*/
private static final int MIN_CAPACITY_INCREMENT = 12;
每次add的时候，如果s == a.length，就会新建一个数组，新数组的扩容规则是
- 1.如果当前长度s<6,则newLength = oldLength + 6
- 2.如果当前长度s>6,则本次增加的长度是s>>1,比如s = 8，则增加长度是:1000 >> 1 = 0100 =4
1.2数组的查找
数组的查找因为有角标的存在，非常快速
1.3数组在中间增删元素
数组从非头尾部分增删元素比较耗费性能，它会将数组分成两部分然后在拼装起来，还是以ArrayList为例：
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}
2.链表
链表是一种递归的数据结构，它或者为null，或者指向下一个结点（node）的引用。该结点含有一个泛型元素和一个指向另一条链表的引用。
Node结构如下：
class Node{
Item item;
Node next;
}
2.1 构造链表
Node first = new Node();
first.item = "to";
Node second = new Node();
second.item = "be";
Node third = new Node();
third.item = "or"
first.next = second;
second.next = third;
此时third.next指向null，所以third是一个空链表。
如果third.next = first，那就是一条循环链表。
2.2 链表基本操作
2.2.1在表头插入结点
Node oldFirst = first;
first = new Node();
first.item = "not";
first.next = oldFirst;
可以看到，所需的时间和链表的长度无关
2.2.2从表头删除结点
first = first.next;
所需的时间依然和链表的长度无关
2.2.3在表尾插入结点
类似于从表头，也需要维护一个last结点。
2.2.4遍历
for（Node x = first; x != null; x = x.next）{
}
3.双向链表
上面并没有讲到在列表的任意位置插入和删除结点和在队尾删除结点，因为如果是单向链表的话，我们只能遍历整条链表找到该结点再进行操作，它所需要的时间和链表的长度成振正比，实现任意插入和删除操作的标准解决方案是双向链表，其中每个结点都含有两个链接，分别指向前后，如下所示
Node{
Item item;
Node previous;
Node next;
}
3.1 简单双向链表的实现
package com.wangzhen.simplechart;
import java.util.NoSuchElementException;
public class DoubleNodeList<E> {
//transient只能修饰成员变量，代表该成员不需要序列化
transient Node<E> first;
transient Node<E> last;
int size = 0;
//Node类
public static final class Node<ET> {
ET item;
Node previous, next;
public Node(ET o, Node<ET> p, Node<ET> n) {
this.item = o;
this.previous = p;
this.next = n;
}
}
public DoubleNodeList() {
}
public void addFirst(E object) {
//1.获取当前的first结点
Node<E> oldFirst = first;
//2.创建一个新的结点，并将新结点的next置为oldFirst
Node<E> newNode = new Node<E>(object, null, oldFirst);
//3.当前的first指向新结点
first = newNode;
//4.判断链表为null的情况
if (first == null) {
//链表为null，first = last；
last = newNode;
} else {
//5.当前first的next指向上一个first结点
first.next = oldFirst;
}
size++;
}
public void addLast(E object) {
//1.获取当前的last结点
Node<E> oldLast = last;
//2.创建一个新的结点，并将新结点的previous置为oldLast
Node<E> newNode = new Node<E>(object, oldLast, null);
//3.当前的last指向新结点
last = newNode;
//4.判断链表为null的情况
if (oldLast == null) {
//链表为null，first = last；
first = last;
} else {
//5.上一个last结点的next指向新结点
oldLast.next = newNode;
}
size++;
}
public E removeFirst() {
Node<E> currentFirst = first;
if (currentFirst == null) {
throw new NoSuchElementException();
} else {
//1.取出要返回的currentFirst中的数据
E item = currentFirst.item;
//2.更换first
Node<E> currFirstNext = currentFirst.next;
//currentFirst 已经是个游离对象了，内部成员置为null
currentFirst.item = null;
currentFirst.next = null;
first = currFirstNext;
//removeFirst后为null了，将last也置为null
if (currFirstNext == null) {
last = null;
} else {
//currFirstNext 已经是first了，previous应该是null
currFirstNext.previous = null;
}
--size;
return item;
}
}
public E removeLast() {
Node<E> currentLast = last;
if (last == null) {
throw new NoSuchElementException();
} else {
E item = currentLast.item;
Node currLastPre = last.previous;
last = currLastPre;
currentLast.item = null;
currentLast.previous = null;
if (currLastPre == null) {
first = null;
} else {
last.next = null;
}
--size;
return item;
}
}
public E get(int location) {
Node<E> result = getNode(location);
if (result != null) {
return result.item;
} else {
return null;
}
}
public Node getNode(int location) {
Node<E> result = null;
if (location >= 0 && location < size) {
//如果位于左区间就正向遍历，否则逆向遍历
if (location < (size / 2)) {
result = first;
for (int i = 0; i <= location; i++) {
result = result.next;
}
} else {
result = last;
for (int i = size; i > location; i--) {
result = result.previous;
}
}
return result;
}
throw new IndexOutOfBoundsException();
}
private void addBefore(E object, Node<E> currLocationNode) {
Node<E> preNode = currLocationNode.previous;
Node<E> newNode = new Node<E>(object, preNode, currLocationNode);
currLocationNode.previous = newNode;
if (preNode == null) {
first = newNode;
} else {
preNode.next = newNode;
}
size++;
}
public void addBefore(E object, int location) {
if (location == size) {
addLast(object);
} else {
this.addBefore(object, getNode(location));
}
}
/**
* 删除某个特定结点
* @param o
* @return
*/
public boolean remove(E o) {
if (o == null) {
//遍历比对，找出相应的节点，断开与链表的连接
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//遍历比对，找出相应的节点，断开与链表的连接
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* 断开结点node
*
* @param node
* @return
*/
E unlink(Node<E> node) {
E item = node.item;
Node<E> n = node.next;
Node<E> pre = node.previous;
//如果是头结点
if (pre == null) {
first = n;
} else {
pre.next = n;
node.previous = null;
}
if (n == null) {
last = node.previous;
} else {
n.previous = pre;
node.next = null;
}
node.item = null;
size--;
return item;
}
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
int location = 1;
for (Node<E> x = first; x != null; x = x.next) {
if (x != null) {
stringBuffer.append("location" + location + ":" + x.item);
stringBuffer.append("\n");
location++;
}
}
return stringBuffer.toString();
}
}
测试如下：
public static void main(String[] arg){
DoubleNodeList<String> doubleNodeList = new DoubleNodeList<>();
doubleNodeList.addLast("1");
doubleNodeList.addLast("2");
doubleNodeList.addLast("3");
doubleNodeList.addLast("4");
doubleNodeList.addBefore("3_new",3);
System.out.print("addBefore 3====\n");
System.out.print(doubleNodeList.toString());
System.out.print("remove last====\n");
doubleNodeList.removeLast();
System.out.print(doubleNodeList.toString());
}
打印如下：
测试结果.png
4.总结
通过双向链表的实现代码我们发现，链表删除某个结点只需要断开这个结点，然后将该结点的previous和next链接起来即可，耗费的时间与链表的长度无关，但是在查找某个值所对应的结点的时候最多需要遍历链表长度的一半，耗费的时间和链表的长度成正比，所以链表增删快，查找慢。
而数组的查找非常快，只要返回对应的index的值即可，但是向数组中的x位置插入某个元素的时候却比较麻烦，需要移动length-x个元素，所以数组查找快，插入慢。
