Java之LinkedList实现原理

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 ，查找节点过程和插入一样；
④获取数据很慢，需要从头节点进行查找；
⑤遍历数据很慢，每次获取数据都需要从头开始；