Fork me on GitHub

2019-7-18 jdk源码分析(3)-LinkedList

jdk源码分析(3)-LinkedList

一、LinkedList简介

LinkedList是基于双向链表实现的,它也可以被当作堆栈、队列或双端队列进行操作。

LinkedList的源码大致分三个部分,双向循环链表的实现、List的API和Deque的API。

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

从类定义和图中也能很清晰的看到,LinkedList的结构大致分为三个部分;同时和ArrayList相比,他并没有实现RandomAccess接口,所以他并不支持随机访问操作;另外可以看到他的List接口是通过AbstractSequentialList实现的,同时还实现了多个迭代器,表明他的访问操作时通过迭代器完成的.

二、链表结构

常见链表

LinkedList是基于双向循环链表实现的,所以如图所示,当对链表进行插入、删除等操作时,

  • 首先需要区分操作节点是否为首尾节点,并区分是否为空,
  • 然后再变更相应prenext的引用即可;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void linkFirst(E e)
void linkLast(E e)
void linkBefore(E e, Node<E> succ)
E unlinkFirst(Node<E> f)
E unlinkLast(Node<E> l)
E unlink(Node<E> x)

/**
* Returns the (non-null) Node at the specified element index.
*/
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;
}
}

上面所列的方法封装了对双向循环链表常用操作,其中node(int index)是随机查询方法,这里通过判断index是前半段还是后半段,来确定遍历的方向以增加效率。
同时在LinkedList中有关ListDeque的API也是基于上面的封装的方法完成的

三、LinkedList的成员变量

1
2
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

LinkedList有两个成员变量,表头 header 和长度size.

四、LinkedList的构造函数

1
2
3
4
5
6
7
8
public LinkedList() {//构造一个空链表
header.next = header.previous = header;
}

public LinkedList(Collection<? extends E> c) {//将一个数据类型相同的集合添加到LinkedList的尾部
this();
addAll(c);
}

五、LinkedList的内部类。

  • Entry是LinkedList的节点类,节点类包含:当前节点的值,前一节点,后一节点。该节点类是一个静态内部类:当内部类对象不需要访问外围类对象时,应该声明为静态内部类。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;
    Entry(E element, Entry<E> next, Entry<E> previous) {
    this.element = element;
    this.next = next;
    this.previous = previous;
    }
    }
  • ListItr 是 LinkedList 的迭代器类

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
      
    private class ListItr implements ListIterator<E> {
    private Entry<E> lastReturned = header;//上一次返回的节点
    private Entry<E> next;//下一节点
    private int nextIndex;//下一节点的索引
    private int expectedModCount = modCount;//!!!!!!期望的改变次数~ Java的 fail-fast 机制。

    ListItr(int index) {
    if (index < 0 || index > size)
    throw new IndexOutOfBoundsException("Index: "+index+
    ", Size: "+size);
    if (index < (size >> 1)) {//size>>1是右移一位,即size/2 ,若索引值小于 size/2则从前开始
    next = header.next;
    for (nextIndex=0; nextIndex<index; nextIndex++)
    next = next.next;
    } else {//否则从后开始
    next = header;
    for (nextIndex=size; nextIndex>index; nextIndex--)
    next = next.previous;
    }
    }

    public boolean hasNext() {//是否存在下一个元素
    return nextIndex != size;//通过下一节点索引值是否等于size来判断是否到了最末尾
    }

    public E next() {
    checkForComodification();
    if (nextIndex == size)//!!
    throw new NoSuchElementException();

    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.element;
    }

    public boolean hasPrevious() {//是否存在上一个
    return nextIndex != 0;//通过下一节点的索引值是否等于0来判断是否在最前面即头节点,由此来判断是否有前节点
    }

    public E previous() {//取得上一元素
    if (nextIndex == 0)
    throw new NoSuchElementException();

    lastReturned = next = next.previous; //??????
    nextIndex--;
    checkForComodification();
    return lastReturned.element;
    }

    public int nextIndex() {
    return nextIndex;
    }

    public int previousIndex() {//上一元素的索引
    return nextIndex-1;
    }

    public void remove() {//删除当前节点!!
    checkForComodification();
    Entry<E> lastNext = lastReturned.next;
    try {
    LinkedList.this.remove(lastReturned);
    } catch (NoSuchElementException e) {
    throw new IllegalStateException();
    }
    if (next==lastReturned)
    next = lastNext;
    else
    nextIndex--;
    lastReturned = header;
    expectedModCount++;
    }

    public void set(E e) {
    if (lastReturned == header)
    throw new IllegalStateException();
    checkForComodification();
    lastReturned.element = e;
    }

    public void add(E e) {//讲e添加到当前节点前面
    checkForComodification();
    lastReturned = header;
    addBefore(e, next);
    nextIndex++;
    expectedModCount++;
    }

    final void checkForComodification() {//!!!!!判断 modCount是否等于 expectedModCount来实现fail-fast机制。
    if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
    }
  • DescendingIterator

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    private class DescendingIterator implements Iterator {
    final ListItr itr = new ListItr(size());
    public boolean hasNext() {
    return itr.hasPrevious();
    }
    public E next() {
    return itr.previous();
    }
    public void remove() {
    itr.remove();
    }
    }

六、LinkedList的成员函数

  • 1.get类型的函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    public E getFirst() {//取得第一个节点的值
    if (size==0)
    throw new NoSuchElementException();//时刻注意特殊情况的考虑
    return header.next.element;
    }

    public E getLast() {
    if (size==0)
    throw new NoSuchElementException();
    return header.previous.element;//获得最后一个是 header.previous.element
    }

    public E removeFirst() {//移除第一个节点
    return remove(header.next);//remove函数下面单独介绍
    }

    public E removeLast() {//移除最后一个节点
    return remove(header.previous);
    }

    public void addFirst(E e) {//在
    addBefore(e, header.next);
    }

    public void addLast(E e) {
    addBefore(e, header);
    }

    public boolean contains(Object o) {
    return indexOf(o) != -1;
    }

    public int size() {
    return size;
    }

    public boolean add(E e) {//在最末尾添加值为e的节点,添加在header前即最末尾
    addBefore(e, header);
    return true;
  • 2.boolean remove(Object o) / E remove() / E remove(Entry e)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    public boolean remove(Object o) {
    if (o==null) {//即使是null也要查找到然后再移除
    for (Entry<E> e = header.next; e != header; e = e.next) {
    if (e.element==null) {
    remove(e);//调用下面的方法
    return true;
    }
    }
    } else {
    for (Entry<E> e = header.next; e != header; e = e.next) {
    if (o.equals(e.element)) {
    remove(e);
    return true;
    }
    }
    }
    return false;
    }
    private E remove(Entry<E> e) {
    if (e == header)
    throw new NoSuchElementException();//考虑头指针的特殊情况

    E result = e.element;
    e.previous.next = e.next;//!!!
    e.next.previous = e.previous;//!!!
    e.next = e.previous = null;// ???不是特别理解
    e.element = null;
    size--;
    modCount++;
    return result;
    }
  • 3.增删改查的一些方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    public void clear() {//清空LinkedList
    Entry<E> e = header.next;
    while (e != header) {
    Entry<E> next = e.next;
    e.next = e.previous = null;
    e.element = null;
    e = next;
    }
    header.next = header.previous = header;
    size = 0;
    modCount++;
    }

    public E get(int index) {//获得某索引对应的节点值
    return entry(index).element;
    }

    public E set(int index, E element) {//设置某索引的节点值
    Entry<E> e = entry(index);
    E oldVal = e.element;
    e.element = element;
    return oldVal;
    }


    public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
    }


    public E remove(int index) {//移除节点
    return remove(entry(index));
    }
  • 4.Entry entry(int index)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
    throw new IndexOutOfBoundsException("Index: "+index+
    ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {//若小于size/2,则从头遍历
    for (int i = 0; i <= index; i++)
    e = e.next;
    } else {//否则从尾遍历
    for (int i = size; i > index; i--)
    e = e.previous;
    }
    return e;
    }

七、方法归类

a.LinkedList可以作为FIFO(先进先出)的队列,作为FIFO的队列时,下表的方法等价:

队列方法 等效方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

b.LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,下表的方法等价:

栈方法 等效方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()

八、总结

  • LinkedList是以双链表的形式实现的。

  • LinkedList即可以作为链表,还可以作为队列和栈。

  • LinkedList是 非 线程安全的。

  • LinkedList 基于双向循环链表实现,随机访问比较慢,所以在遍历 List 的时候一定要注意。

  • LinkedList 可以添加重复元素,可以添加 null。
-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!