Java LinkedList源码学习

2018-03-09 本文已影响40人梦工厂

LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

abstract class AbstractSequentialList<E> extends AbstractList<E>
This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.
AbstractSequentialList的数据访问是连续访问，AbstractList 是随机访问；
基于位置的增删改查，依赖listIterator(index)找到位置进行处理，O（n）开销；

public E get(int index) {
    try {
        return listIterator(index).next();
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

public E set(int index, E element) {
    try {
        ListIterator<E> e = listIterator(index);
        E oldVal = e.next();
        e.set(element);
        return oldVal;
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

LinkedList实现：Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
获取特定位置的节点，从头找或者从尾找，时间O（n/2）；

Node<E> node(int index) {
    // assert isElementIndex(index);
  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;
  }
}

Doubly-linked list implementation of the List and Deque interfaces.
双向链表

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;
    }
}
transient Node<E> first;//指向头结点
transient Node<E> last;//指向尾节点

没有数据时：first == null && last == null
添加第一个元素时：first，last指向同一个元素

Deque接口interface Deque<E> extends Queue<E>
add(E e) 默认加到尾部； remove()默认移除头部；Deque extends Queue，Queue默认FIFO；
Deque为双端队列接口，因此LinkedList可以用作双端队列；
双端队列操作：
removeFirst() removeLast()
addFirst(E e) addLast(E e)
getFirst() getLast()
stack操作：
pop,push对LinkedList头部进行操作；
线程不安全 & fail-first机制
List list = Collections.synchronizedList(new LinkedList(...));
总结
LinkedList vs ArrayList
是否可以随机访问 -》中间节点
链表实现，节点开销大，灵活；数组实现，节点开销小，不灵活；- 》中间节点的插入和删除

@梦工厂 2018.3.9

Java LinkedList源码学习

猜你喜欢

热点阅读