LinkedList是Java集合框架中一个重要的实现,底层采用双向链表结构。和ArrayList一样,其也支持null值和重复值。它基于双向链表实现,就不用扩容了,可这也就是说,在维护结点的时候需要额外的空间存储前驱和后继的引用。在链表头部和尾部插入效率比较高,但是在指定位置插入就不太行了,原因是定位需要O(N)的时间复杂度,这也就是说查找的效率也不太行。最后,他是非线程安全集合类。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable 复制代码
可以看出它继承了AbstractSequentialList,查看AbstractSequentialList的源码,发现里面实现了增删查,很多都是基于iterator实现的。不用LinkedList自己重新实现了其中的一套方法,此外说一点,一般建议声明明队列的时候: Queue<T> queue = new LinkedList<>();
而且建议用LinkedList实现Stack。因为原生的 Stack<T> stack = new Stack<>();
有很多问题。
public E get(int index) { //检查index是否合理 checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); // 如果index是小于size的二分之一,这设计的很巧妙 if (index < (size >> 1)) { //则从前面从前往后开始找 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //否则从后往前找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } 复制代码
//单参,在链表尾部插入元素 public boolean add(E e) { linkLast(e); return true; } //双参,在指定位置加入元素 public void add(int index, E element) { //老规矩先检查 checkPositionIndex(index); //如果index就是size,就直接在末尾加 if (index == size) linkLast(element); //否则在指定位置之前插 else linkBefore(element, node(index)); } /** * Links e as last element. * 将e插入最后一位 */ void linkLast(E e) { final Node<E> l = last; //初始化新结点,指明前驱为l,后继为null final Node<E> newNode = new Node<>(l, e, null); last = newNode; //如果链表为空,就直接插第一个 if (l == null) first = newNode; //前面把last给l了,则直接把新插入的元素插到l的后面 else l.next = newNode; //改变了原有数据结构,操作数加一 size++; modCount++; } /** * Inserts element e before non-null Node succ. * 在非空结点之前插入e */ void linkBefore(E e, Node<E> succ) { // assert succ != null; //前提就是当前结点不空 final Node<E> pred = succ.prev; //初始化新结点,指明前驱为pred,后继为当前结点succ final Node<E> newNode = new Node<>(pred, e, succ); //让succ的前驱指向新结点 succ.prev = newNode; //如果pred为空,表明当前元素是第一个元素,或者当前链表为空 if (pred == null) first = newNode; //否则,succ的前驱的后继变成了新加入的结点 else pred.next = newNode; //改变了原有数据结构,操作数加一 size++; modCount++; } 复制代码
按照索引插入的过程大概就是:
public boolean remove(Object o) { //前面说过,LinkedList里面是可以塞空的,所以这就先在里面找null,从前往后,只要找到第一个就删 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; //prev为null表示x第一个元素,直接让first指向x的后继就行 if (prev == null) { first = next; } else { //否则就是x前驱的后继直接赋给x的后继,并让x的前驱引用为null,即释放x与前驱的连接 prev.next = next; x.prev = null; } //next为null表示x为最后一个元素,直接让last指向x的前驱就行 if (next == null) { last = prev; } else { //否则就是x后继的前驱直接赋给x的前驱,并让x的后继引用为null,即释放x与后继的连接 next.prev = prev; x.next = null; } //清除x的数据,方便GC回收 x.item = null; //改变数据结构 size--; modCount++; return element; } 复制代码
删除的时候断开连接的步骤小结(假设x既不是头也不是尾):
最后在讲一下基于LinkedList实现的Queue里面的一些常用方法,方便后续学习:
查看Queue接口,里面有这些方法:
在队尾增加元素: boolean add(E e);
在队尾增加元素: boolean offer(E e); //这个元素内部就是调用add方法,不再赘述
删除元素:
E remove(); //这个是Queue特有的remove public E remove() { return removeFirst(); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } 复制代码
出队并取得之: E poll();
//出队并且取得队首操作,不赘述了。 public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } 复制代码
取得队首元素: E element();
取得队首元素: E peek();
public E peek() { //和上面的区别就是这个peek可以在队空的情况下返回null,上面element()则直接报异常 final Node<E> f = first; return (f == null) ? null : f.item; } 复制代码