LinkedList数据结构原理
LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据；
LinkedList构造函数
transient int size = 0;
transient Link<E> voidLink;
private static final class Link<ET> {
ET data;
Link<ET> previous, next;
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
Link是LinkedList的静态内部类，可以看作节点类，data用来存放数据，previous与next则分别存放前后节点的信息；而构造函数中实际上是作了对voidLink的初始化操作，也就是对头指针的初始化操作；
空链表的情况应该是header节点的前一节点和后一节点均为null；
1.添加一个元素到链表尾部
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
从源码中可以看到，添加元素到链表尾实际上是新new了一个Link节点（newLink）;
voidLink实际上是头节点，然后把头节点的前结点指向newLink；把原尾结节oldLast的后结点指向newLink；
2.添加一个元素到链表指定位置
public void add(int location, E object) {
if (location >= 0 && location <= size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
添加到链表指定位置，会先遍历，是顺向迭代还是反向迭代，找到位置然后再同上添加元素的操作，将节点指向修改正确；
3.删除数据
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
删除的节点对象是由系统去gc回收的；
4.查找数据与修改数据
为了提高效率，需要根据获取的位置判断是从头还是从尾开始遍历
5.用LinkedList模似堆栈
addLastImpl(E object)
addFirst(E object)
removeFirstImpl()
removeLast()
在LinekList中封装了上面四个方法，分别添加删除链表头尾，对链表的操作进行一下封装和限制就可以模拟堆栈或者队列了；
public class Test5{
public static void main(String[] args){
Duilie dl = new Duilie();
dl.myAdd("abc1);
dl.myAdd("abc2);
dl.myAdd("abc3);
dl.myAdd("abc4);
while(!dl.isNull()){
System.out.println(dl.myGet());
}
}
}
class Duilie{
private LinkedList link;
public Duilie(){
link = new LinkedList();
}
public void myAdd(Object obj){
//添加到链表尾部
link.addLast(obj);
}
public Object myGet(){
//获取头部元素
// return link.removeFirst(); 模似队列
//获取尾部元素
return link.removeLast(); //模似堆栈
}
public boolean isNull(){
return link.isEmpty();
}
}
LinkedList总结
①数据存储是基于双向链表实现的；
②插入数据很快。先是在双向链表中找到要插入节点的位置index，找到之后，再插入一个新节点。 双向链表查找index位置的节点时，有一个加速动作：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找；
③删除数据很快。先是在双向链表中找到要插入节点的位置index，找到之后，进行如下操作：node.previous.next = node.next;node.next.previous = node.previous;node = null ，查找节点过程和插入一样；
④获取数据很慢，需要从头节点进行查找；
⑤遍历数据很慢，每次获取数据都需要从头开始；
