美文网首页
Java集合系列03之LinkedList源码分析

Java集合系列03之LinkedList源码分析

作者: Hengtao24 | 来源:发表于2019-05-22 09:46 被阅读0次

    系列文章：

    前言

    本文开始分析LinkedList。ArrayList和LinkedList都实现了List接口，但内部数据结构有所区别，LinkedList内部是基于链表实现的，所以其插入和删除操作效率较高，但是随机访问效率就相对较低。其定义如下：

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

    可以看到LinkedList继承AbstractSequentialList，实现了List，Deque，Cloneable，java.io.Serializable四个接口。

    AbstractSequenceList实现了大部分List接口的方法，Deque接口定义了双端队列的操作。

    本文源码分析基于jdk 1.8.0_121

    继承关系

    LinkedList继承关系

    java.lang.Object
  |___ java.util.AbstractCollection<E>
      |___ java.util.AbstractList<E>
          |___ java.util.AbstractSequentialList<E>
              |___ java.util.LinkedList<E>

所有已实现的接口：
Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

    关系图

    LinkedList关系图
    LinkedList的本质是双向链表，LinkedList中first,last,size等成员比较重要，first是链表的头指针，last是尾指针，size是双向链表中节点的个数，链表的节点对应Node类数据结构如下： 
    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;
    }
}

    AbstractSequenceList

    AbstractSequentialList 继承自 AbstractList，是 LinkedList 的父类，提供了List接口大部分实现。
    AbstractSequentialList 实现了“随机访问”方法get(int index)、set(int index, E element)、add(int index, E element)、remove(int index)。
    要实现一个列表，我们只需要扩展此类，并提供 listIterator 和 size 方法的实现即可。对于不可修改的列表，我们只需要实现列表迭代器的 hasNext、next、hasPrevious、previous、index 方法即可。

    API

    boolean             add(E e)
void                add(int index, E element)
boolean             addAll(Collection<? extends E> c)
boolean             addAll(int index, Collection<? extends E> c)
void                addFirst(E e)
void                addLast(E e)
void                clear()
Object              clone()
boolean             contains(Object o)
Iterator<E>         descendingIterator()
E                   element()
E                   get(int index)
E                   getFirst()
E                   getLast()
int                 indexOf(Object o)
int                 lastIndexOf(Object o)
ListIterator<E>     listIterator(int index)
boolean             offer(E e)
boolean             offerFirst(E e)
boolean             offerLast(E e)
E                   peek()
E                   peekFirst()
E                   peekLast()
E                   poll()
E                   pollFirst()
E                   pollLast()
E                   pop()
void                push(E e)
E                   remove()
E                   remove(int index)
boolean             remove(Object o)
E                   removeFirst()
boolean             removeFirstOccurrence(Object o)
E                   removeLast()
boolean             removeLastOccurrence(Object o)
E                   set(int index, E element)
int                 size()
<T> T[]             toArray(T[] a)
Object[]            toArray()

    源码分析

    首先我们知道LinkedList是一个双向链表，但是同时也实现了List接口，因此也可以根据索引值（index）来获取，更改，删除节点等。那么是如何把链表和索引值联系的呢？LinkedList是通过一个计数索引值来实现的，当我们调用get(int index)时，我们会把index和链表长度的1/2比较，如果index值小·，则从链表头向后遍历；反之；如果index值大，则从链表尾遍历。其余方法原理类似。

    成员对象

    transient int size = 0;   // 节点个数
 
transient Node<E> first;  // 表头

transient Node<E> last;   // 表尾

    构造函数

    // 默认构造函数
public LinkedList() {
}

// 创建包含集合c的LinkedList
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

    增加元素

    // 添加元素，添加到last节点后
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 新建一个节点newNode，让其prev属性为当前last节点，last属性为null
// 如果当前last节点为null，则令first节点为newNode
// 如果当前last节点不为null，则让其next属性为newNode
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++;
}

// 先检查index，如果index值正好为size，那么添加到last节点后
// 否则，添加到index位置处，node(index)获取当前index处节点
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

// 先获取当前index处节点的前一个节点pred
// 再新建节点newNode，如果pred节点为null，则令first为newNode
// 否则pred的next节点为newNode，同时改变size和修改计数值
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

// 添加集合c到LinkedList中
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
  
// 在index处添加所有集合c中所有节点
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}    

// 添加元素到头节点位置
public void addFirst(E e) {
    linkFirst(e);
}

// 把元素e设置为第一个节点
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 void addLast(E e) {
    linkLast(e);
}

    设置元素

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

    获取元素

    // 返回index处节点值
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 返回头节点值
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

// 返回尾节点值
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

    删除元素

    // 从LinkedList中删除对象o
public boolean remove(Object o) {
    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;
}

// 删除index处节点
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

// 删除第一个元素
public E remove() {
    return removeFirst();
}

// 删除第一个元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除最后一个元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

    toArray

    // 返回LinkedList的Object[]数组
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

// 返回T类型的数组
public <T> T[] toArray(T[] a) {
    // 若数组a的大小小于LinkedList的元素个数
    // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;

    if (a.length > size)
        a[size] = null;

    return a;
}

    克隆函数

    // 克隆函数
public Object clone() {
    LinkedList<E> clone = superClone();
    
    // 重新初始化
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // 添加所有节点数值
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}

// 调用父clone函数
private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

    其余函数

    // 将e添加到链表末尾
public boolean offer(E e) {
    return add(e);
}

// 将e添加到链表头节点处
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

// 将e添加到链表末尾
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

// 返回头节点，头节点为null则返回null
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }

// 返回尾节点，尾节点为null则返回null
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

// 返回头节点并删除
// 头节点为null则返回null
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

// 返回尾节点并删除
// 尾节点为null则返回null
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

// 将e插入到双向链表头节点
public void push(E e) {
    addFirst(e);
}

// 删除并返回第一个节点
public E pop() {
    return removeFirst();
}

    小结

    • LinkedList是通过双向链表实现的，内部有节点的数据结构
    • LinkedList实现了Deque，而Deque接口定义了在队列两端访问元素的方法，有增加，删除，获取第一个元素等方法。
    • LinkedList可以作为FIFO先进先出的队列，下列方法等效
    队列方法 等效方法
    add(e) addLast(e)
    offer(e) offerLast(e)
    remove() removeFirst()
    poll() pollFirst()
    element() getFirst()
    peek() peekFirst()
    • LinkedList可以作为LIFO后进先出的栈，下列方法等效
    栈方法 等效方法
    push(e) addFirst(e)
    pop() removeFirst()
    peek() peekFirst()

    遍历方式

    迭代器遍历

    Iterator iter = list.iterator();
while(iter.hasNext()) {
    iter.next();
}

    随机访问

    for (int i=0; i<list.size(); i++) {
    list.get(i);        
}

    foreach循环

    for (Integer integ:list) {
    ;
}

    pollFirst

    while(list.pollFirst() != null)
    ;

    pollLast

    while(list.pollLast() != null)
    ;

    removeFirst

    try {
    while(list.removeFirst() != null)
        ;
} catch (NoSuchElementException e) {
    ...
}
##

    removeLast

    try {
    while(list.removeLast() != null)
        ;
} catch (NoSuchElementException e) {
    ...
}

    通过随机访问的方式遍历LinkedList时，效率很低，因此需要尽量避免这种方式。

    参考内容

    相关文章

      网友评论

          本文标题：Java集合系列03之LinkedList源码分析

          本文链接：https://www.haomeiwen.com/subject/soxyzqtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|Java集合系列03之LinkedList源码分析|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！