JDK1.8源码分析:LinkedList

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

JDK1.8源码分析:LinkedList


接口和数据结构


LinkedList,实现了List和Deque接口,其中Deque是双向队列,即可以在队列头部和尾部进行插入或删除数据节点。LinkedList也不是线程安全的。


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


LinkedList为了实现以上功能,在内部使用了双向链表这种数据结构。数据结构定义如下:


// 链表长度
transient int size = 0;
    /**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 * (first.prev == null && first.item != null)
 */

transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 * (last.next == null && last.item != null)
 */

transient Node<E> last;

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;
    }
}


Node为链表节点,item为进行数据存放,类型为泛型E;pref和next分别为当前链表节点的前后节点。


链表指定位置操作


对链表指定位置操作,是通过指定某个索引,类似于数组下标,来获取指定位置的数据。核心实现为提供了一个node(index)的方法来查找index对应的链表节点,如get,set为例:


public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
/**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}


/**
 * Returns the (non-null) Node at the specified element index.
 */

Node<E> node(int index) {
    // assert isElementIndex(index);

    // index在前半部分,则从头开始查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    // index在后半部分,则从尾部开始查找
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}


node方法主要利用了头部,尾部指针和链表长度size,对于给定的index,如果在链表前半部分,则直接头部开始查找,如果在链表后半部分,则从尾部指针往前查找,从而可以减少遍历次数,提高性能。


链表头部操作


链表头部操作是指相对于内部的双向链表的头结点进行操作,具体为增删查改。


public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// 删除链表头部节点
/**
 * Unlinks non-null first node f.
 */

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

public void addFirst(E e) {
    linkFirst(e);
}

// 在链表头部插入节点
/**
 * Links e as first element.
 */

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

// 获取头部节点
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
// poll和remove都是获取并删除头部节点
// 还有pollFirst,pollLast版本的方法
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
public E remove() {
    return removeFirst();
}

public void push(E e) {
    addFirst(e);
}
public E pop() {
    return removeFirst();
}


链表尾部操作


链表尾部操作是指相对于内部的双向链表的尾部结点进行操作,具体为增删查改。


public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
  
// add和addLast都是在链表尾部添加元素
public void addLast(E e) {
    linkLast(e);
}
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 在链表尾插入节点
/**
 * Links e as last element.
 */

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++;
}

// 在尾部添加节点
// 还有offerFirst,offerLast版本的方法
public boolean offer(E e) {
    return add(e);
}


链表长度size


在LinkedList中也使用了一个size来维护当前链表的长度,在添加或删除链表节点时,同步更新该size的值,从而可以直接返回该size变量来获取该链表当前存在多少元素。


public int size() {
    return size;
}


清空链表


将链表内所有节点置null,头部和尾部节点置null,从而可以让GC回收。


public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    // more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}



原文链接:https://blog.csdn.net/u010013573/java/article/details/86990289



精彩推荐

JDK1.8源码分析:Executors线程池创建工厂的用法和实现原理

JDK1.8源码分析:可重入锁ReentrantLock和Condition的实现原理

Java基础系列:JDK1.8源码分析之HashMap

Java 基础系列:图解Java内存



扫下方二维码关注“程序员考拉”,每日推荐优秀好文!



JDK1.8源码分析:LinkedList


如果感觉推送内容不错,不妨右下角点个在看,感谢支持

原文始发于微信公众号(程序员考拉):JDK1.8源码分析:LinkedList