总览数据结构的内容
- 线性表：零个或多个数据元素的有序序列
- 队列：只允许在一端插入，而在另一端进行删除操作的线性表
- 堆栈：栈是限定仅在表尾进行插入删除操作的线性表
- 树：树是n个节点的有序集。节点可以像树一样越向叶子节点就没有交集
- 图论：由顶点的有穷空集合和顶点之间边的集合组成
- 排序和查找算法：排序是对数据进行顺序排列，查找是在大量数据中寻找我们需要的数据的过程
什么是数据结构？
- 数据项：一个数据元素可以由若干数据项组成
- 数据对象：有相同性质的数据元素的集合，是数据的子集
- 数据结构：是相互之间存在一种或多种特定关系的数据元素集合
逻辑结构与物理结构##
逻辑结构：是指数据对象中数据元素之间的相互关系
- 集合结构
- 线性结构
- 树形结构
- 图形结构
物理结构：是指数据的逻辑结构在计算机中的存储
- 顺序存储结构
- 链式存储结构
数组
- 简单：数组是一种最简单的数据结构
- 占据连续内存：数据空间连续，按照申请的顺序存储，但是必须指定数组大小
- 数组空间效率低：数组中经常有空闲的区域没有得到充分的应用
- 操作麻烦：数组的增加和删除操作很麻烦
线性表
物理结构划分（一个萝卜一个坑，美女）
链式存储结构（天龙三兄弟）
- 顺序表
a1是a2的前驱，ai+1是ai的后继，a1没有前驱，an没有后继
n为线性表长度，若n==0,线性表为空
数据节点：
class students{
Student[40];
int size;
...
}
下面从ArrayList的添加删除来看看顺序表：（从android studio中分离出来的方法）
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
add方法中有一个参数和二个参数的方法，首先我们看一个参数的方法：
首先看看ensureCapacityInternal（size+1）从他的参数我们可以看到是整个ArrayList大小+1,如果ArrayList（elementData）数组等于初始的数组，就对比传入参数与默认的参数大小，两者取其大
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
如果较大的参数减去当前ArrayList的真实长度是大于0的，我们就走grow方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow方法中有一个新的容积大小（newCapacity），他扩充的大小相当于当前ArrayList的size+size*2,这个值与minCapacity对比取其大值，并且限制不能小于int的MAX。做完判断就会走copeyOf方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
System.arraycopy(a,4,a1,5,6)：把a数组的数据从下标 4 开始，移动到 a1数组下标是 5 ，移动6的长度
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
现在来看二个参数的add方法：
先走一个OutOfBoundsException的判断，如果当前要添加的位置index大于ArrayList的长度，或者小于0，根据前面的分析ensureCapacityInternal(size + 1)就是对ArrayList进行扩容，扩容完就继续复制，System.arraycopy(elementData, index, elementData, index + 1, size - index);
将elementData的下标为index复制到index+1处，复制的大小就是size-index，然后将要添加的值element插入到数组的index处，同时增加Arraylist的size，+1。
remove方法也有两种参数，一个是int下标，一个是object值：
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
先看传入int下标的方法，如果下标大于ArrayList长度，就出OutOfBoundsException。获取在该index上的元素，判断需要发生移动的数据量大小，然后将index+1的numMoved的数据移动到从index开始，同时将最后一位置为空。
如果传入了Object，就循环遍历出这个数据，并进行移除。
ArrayList类的关系如下：
ArrayList面试常见问题
ArrayList的大小是如何自动增加的？
ArrayList在add方法中会做出判断，如果当前长度过短，会增加size+size*2的长度
什么情况下你会使用ArrayList？
ArrayList在插入删除时候有明显的复杂度增加，因为他删除的时候是顺序表，插入删除都要移动size-index-1长度的数据。明白他的特性下，我会在保存数据同时对这段数据不进行排序删除等操作时候，我会优先使用ArrayList，如果要进行排序等操作我会选择LinkList。
在索引中ArrayList的增加或者删除某个对象的运行过程？效率很低吗？解释一下为什么？
从ArrayList的remove方法我们可以看到，如果要删除某个对象，根据对象删除需要遍历整个数组，然后删除后进行位移，根据下标删除也需要进行位移，效率很低。但是在尾部删除或者添加，根据顺序表的规则，效率不低。
ArrayList如何顺序删除节点 ？
他是可以顺序删除节点的。通过迭代器顺序删除，each和for循环也可以删除，但是需要从后往前删除。如果从前往后删，根据顺序表的特点，0节点永远存在，删除了也会从1节点上面前移所以会报错。
arrayList的遍历方法
each和for循环，迭代器
线性表之链表
定义：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的
class Node{
Object data;
Node next;
}
单循环链表
双循环链表
链表的增删改查
//增
s.next=p.next
p.next=s
//删
p.next=p.next.next
//改
p.data=new data();
//查
while(p.next!=l){
p=p.next;
}
顺序表 优点，存储空间连续允许随机访问尾插，尾删方便，缺点插入效率低，删除效率低，长度固定
单链表 优点，随意进行增删改，插入效率高，删除效率高O0，长度可以随意修改，缺点内存不连续，不能随机查找
双链表的存储结构单元
private static class Node<E>{
E item;
Node<E> next;
Node<E> prev;
}
双链表的表现形式
双链表的知识树
- 增
1：s.next=p.next;
2: p.next.prev=s;
3: s.prev=p;
4: p.next=s;
//步骤不能乱，否则就会出现跳跃式的循环，比如2,4调换，这样s=p.next,而p.next.prev=s,这样s这里就出现了一个死循环
- 删
p.next.prev=p.prev;
p.pre.next=p.next;
现在分析一下LinkedList的添加删除方法：首先是add()
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
单参数的add，方法很简单，只有一个likLast(e)
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;
}
}
这是一个简单的尾插，我们可以从名称上看出来。首先获取最后一个节点l，同时new出来一个Node<>,从Node的构造方法，我们可以看出，第一个是新参数的prev指向的节点，而next为空。同时把尾值替换为新节点。然后是一个判断，当首节点为空，就把新参数作为首节点，否则就将首节点的next指向尾节点。
再看两个参数的add方法。当插入的位置为尾部，就使用尾插，否则就走linkBefore
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++;
}
拿出该插入位置的pred(p.prev),同时新建一个Node（s），将新节点的prev指向该prev(s.prev=pred)，同时将新节点的next，指向原位置的节点(s.next=p)。判断如果新节点的prev为空，那就将新节点命名为首节点，否决就将老节点的next指向新节点（pred.next=s）
删除方法如下：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public boolean remove(Object 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;
}
传入下标的方法相对简单
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
判断下标节点prev，若prev为空，这时候就在首节点位置，就把首节点复制为下标节点的next，否则就将下表节点的值赋为她的next（prev.next=next）,同时把下标节点的prev指空。如果next位置为空，那么此时处于尾节点位置，将节点的next的prev指向prev，并将下标节点指向null。最后将节点赋空。
如果是传入Object，分两种情况进行遍历。
List总结
- List是一个接口，它继承于Collection的接口。它代表这有序的队列
- AbstractList是一个抽象类，它继承于AbstractCollection。AbstractList实现了List接口中除size（）、get（int location）之外的函数
- AbstractSequentialList是一个抽象类，它继承于AbstractList。AbstractSequentialList实现了链表中，根据index索引值操作链表的全部函数
- ArrayList，LinkList，Vector，Stack是List的4个实现类
