文档章节

0004--jcf(jdk1.7)-LinkedList源码

c
 cengy
发布于 2016/03/28 22:48
字数 2881
阅读 62
收藏 0

1.     LinkedList的定义
内部是一个链式结构的实现。它还实现了Deque接口。可以当作一个队列,堆栈或双端队列使用。其类定义如下:

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

关于AbstractSequentialList,它对List的这些接口进行了实现。

get(int): E
set(int, E): E
add(int, E): void
remove(int): E
addAll(int, Collection<? extends E>): boolean

如果我们需要自己实现一个List,可以扩展此类,我们只需要实现listIterator()和size()方法即可。我们也可以基于此类,实现可修改和不可修改的List。如果想实现一个不修改的列表,只需要我们实现list iterator的hasNext,next,hasPrevious,previous以及index方法。而实现一个可以修改的列表,需要实现list iterator的set方法。如果要实现可变大小的列表,还应该提供list iterator的remove方法。

了解一下双向链表的结构


2.    LinkedList的实现

它有三个属性:

transient int size;    --存储的元素个数
transient Node<E> first;--头节点
transient Node<E> last;--尾节点

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

提供了两个构造函数:

public LinkedList() {
}

//以指定列表元素创建一个LinkedList列表
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(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;

    // 定义两个临时变量pred前一个节点,succ下一个节点。用来存储index处的前后节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;    // 这里succ有可能为null
    }

    //    以pred节点为起点,构造了一个双向链表
    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;//此时pred指向了这个链表的最后节点
    }

    // 将index处的节点与上面的链表链接
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

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

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

第一个构造函数就什么也没做,它的first与last都是为null。

第二个构造函数,用指定列表构造了一个双链表。

index是从0开始的,当index==size的时候,表示是从之前列表的末节点开始插入元素。

3. LinkedList列表元素的操作

1).    增加

有如下向列表添加元素的方法:

add(E): boolean
add(int, E): boolean
addAll(Collection<? extends E>): boolean
addAll(int, Collection<? extends E>): boolean

其中addAll(int, Collection<? extends E>) 已经在上面构造函数里提过。看下其它几个方法。

  • add(E)

public boolean add(E e) {
    linkLast(e);
    return true;
}
  • add(int, E)

public void add(int index, E element) {
    checkPositionIndex(index);
    // 当是在列表末尾添加元素
    if (index == size)
        linkLast(element);
    else    // 在指定位置插入元素
        linkBefore(element, node(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;
    }
}

void linkLast(E e) {
    final Node<E> l = last;
    // 构造插入的节点
    final Node<E> newNode = new Node<>(l, e, null);    
    //更新最后节点为当前节点
    last = newNode;    
    // 更新之前那个最后节点的next指向这个新加入的节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // succ的前一个节点
    final Node<E> pred = succ.prev;    
    // 构造插入的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将节点链接到succ的prev指向处
    succ.prev = newNode;
    // 将succ的最开始prev指向的节点指向新增节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
  • addFirst(E)

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

private void linkFirst(E e) {
    final Node<E> f = first;
    // 构造新增节点
    final Node<E> newNode = new Node<>(null, e, f);
    // 将新增节点指向first节点
    first = newNode;
    // 更新之前头结点指向新增节点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
  • addLast(E)

public void addLast(E e) {
    linkLast(e);
}

2).    查询

查询接口有如下几个方法:

get(int): E
indexOf(Object): int
lastIndexOf(Object): int
  • get(int)

public E get(int index) {
    // index范围判定
    checkElementIndex(index);
    return node(index).item;
}
  • indexOf(object)查找元素第一次出现的位置,未找到则返回-1

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
  • lastIndexOf(Object)查找元素最后一次出现的位置,未找到则返回-1

public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

3).    修改

提供的修改接口有:

set(int, E): E
  • set(int, E)源码如下:

public E set(int index, E element) {
    checkElementIndex(index);   // 位置判定,会抛出异常IndexOutOfBoundsException
    Node<E> x = node(index);    // 查找指定位置元素,并替换
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

4).    删除

remove(int): E
remove(Object): boolean
clear()
  • remove(int)

public E remove(int index) {
    checkElementIndex(index);    //会抛出IndexOutOfBoundsException
    return unlink(node(index));
}

// 将删除元素的前后节点都更改
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;

    // 删除的是首节点,那么x节点的下一个节点将成为首节点
    if (prev == null) {
        first = next;
    } else {
        // 将x节点的前一个节点链接到x的下一个节点
        prev.next = next;
        // 释放x节点的前节点的指向
        x.prev = null;
    }

    // 如果删除的是尾节点,那么x节点的前一个节点将是末节点
    if (next == null) {
        last = prev;
    } else {
        // 将x节点的后节点指向x的前一个节点
        next.prev = prev;
        // 释放x节点的后节点指向
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    // 返回被删除的元素
    return element;
}
  • remove(Object),此方法返回的是boolean值

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;
}
  • clear()

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

4.    LinkedList的其它方法

clone()
toArray(): Object[]
toArray(T[]): T[]
subList(int, int)
  • clone(): 浅复制

public Object clone() {
    LinkedList<E> clone = superClone();

    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // Initialize clone with our elements
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}
private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError();
    }
}
  • toArray()

// 数组大小为列表拥有的元素个数
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;
}
  • toArray(T[])

//
public <T> T[] toArray(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;
}
  • subList(int, int)

// LinkedList没有重写subList方法,所以它默认是继承AbstractList的subList方法

public List<E> subList(int fromIndex, int toIndex) {
    return new SubList<>(this, fromIndex, toIndex);
}
class SubList<E> extends AbstractList<E> {
    private final AbstractList<E> l;
    private final int offset;
    private int size;

    SubList(AbstractList<E> list, int fromIndex, int toIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        this.modCount = l.modCount;
    }

5.    内部类ListItr迭代

获取ListItr迭代器:(这两个方法都是List中接口的,其中ListIterator<E> ()接口是在AbstractList中实现的。

ListIterator<E> (){
return listIterator(0);
}

ListIterator<E> (index) {
    checkPositionIndex(index)ListItr(index)}

ListIterator是基于fail-fast机制的:当list iterator被创建之后,任何对list的结构性修改(remove,add)将会抛出ConcurrentModificationException。(但是我在跑以下代码的时候,没有抛出异常)

// 这段代码在jdk1.6上面跑,会抛出ConcurrentModificationException. 但jdk1.7没有异常
        List<Integer> mLinkedList = new LinkedList<Integer>();
        mLinkedList.add(2);
        mLinkedList.add(3);
        Iterator<Integer> mItrLinkedList = mLinkedList.iterator();
        while (mItrLinkedList.hasNext()) { 
            Integer mInteger = mItrLinkedList.next(); // index++
            mLinkedList.remove(mInteger); //size--
//            mItrLinkedList.remove();
        }
        System.out.println(mLinkedList);
// 输出结果
[3]

// 下面这段代码回抛出异常ConcurrentModificationException(jdk1.6和jdk1.7都会)
List<Integer> mArrayList = new ArrayList<Integer>();
mArrayList.add(2);
Iterator<Integer> mItrArrayList = mArrayList.iterator();
while (mItrArrayList.hasNext()) {
    Integer mInteger = mItrArrayList.next();
    mArrayList.remove(mInteger);
}

/*
原因:jdk1.7中ListItr迭代器里面hasNext()方法是retrun nextIndex < size;
当调用list的remove(Object)时候,size--。迭代时nextIndex++,不满足nextIndex<size了,所以jdk1.7已经不会进入下一次next()了,就没有抛出异常。
jdk1.6中hasNext()方法是return nextIndex != size;但是即便如此,如果LinkedList中含有两个元素,在jdk1.6中也不会抛出这个异常,因为index++ == size--了。
*/

ListItr的属性以及构造函数

private class ListItr implements ListIterator<E> {
    // 迭代过程中,存储当前的元素
    private Node<E> lastReturned = null;
    // 游标元素,构造的时候是index处的节点
    private Node<E> next;
    // 构造的时候是当前index值
    private int nextIndex;
    private int expectedModCount = modCount;
    
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
}

ListIterator阔咱了Iterator接口,增加了访问前一个元素的功能

public boolean hasPrevious() {
    return nextIndex > 0;
}

public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();

    //返回前一节点,这里判定next==null的情况:ListItr的构造函数里面,当index==size的时候,next被赋值为null
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}
public void remove() {
    checkForComodification();
    if (lastReturned == null)
        throw new IllegalStateException();

    // lastReturned保存了上次返回的那个元素
    Node<E> lastNext = lastReturned.next;
    unlink(lastReturned);    //删除上次那个元素
    if (next == lastReturned)
        next = lastNext;
    else
        nextIndex--;
    lastReturned = null;
    expectedModCount++;
}

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

public void add(E e) {
    checkForComodification();
    lastReturned = null;
    if (next == null)
        linkLast(e);
    else
        linkBefore(e, next);
    nextIndex++;
    expectedModCount++;
}



6.     LinkedList提供关于队列的操作方法

getFirst(): E // 返回第一个元素,当list为空会抛出NoSuchElementException
getLast(): E  // 返回列表最后一个元素,当list为空会抛出NoSuchElementException

removeFirst(): E // 删除并返回第一个元素,当list为空会抛出NoSuchElementException
removeLast(): E  // 删除并返回列表最后一个元素,当list为空会抛出NoSuchElementException

addFirst(E): void   // 向list列表头添加元素
addLast(E): void    // 向列表尾添加元素

peek(): E // 获取列表头元素,当元素列表为空的时候,会返回null
element(): E // 获取列表头元素,当元素列表为空的时候,会抛出异常NoSuchElementException
poll(): E    // 获取并删除头元素,当元素列表为空的时候,会返回null
offer(): boolean    // 添加元素至列表尾
offerFirst(): boolean    // 添加元素在列表头
offerLast(): boolean    // 添加元素至列表尾

peekFirst(): E // 获取列表头元素,当元素列表为空的时候,返回null
peekLast(): E  // 返回列表尾元素,当元素列表为空的时候,返回null
pollFirst(): E // 获取并删除头元素,当列表为空,返回null
pollLast(): E  // 获取并删除尾元素,当列表为空,返回null
push(E): void  // 向栈顶置入元素
pop(): E        // 出栈
removeFirstOccurrence(Object): boolean
removeLastOccurrence(Object): boolean
  • removeFirst()

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(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作为first
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    // 返回被删除的头节点元素
    return element;
}
  • removeLast()

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

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    // 将last.prev作为末节点
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}









© 著作权归作者所有

c
粉丝 1
博文 22
码字总数 16864
作品 0
成都
私信 提问
关于JDK1.7中LinkedList索引方法的思考

前几天无意中看到LinkedList的部分源码,发现一个很有趣的问题,跟大家一起分享一下。 首先LinkedList底层实现是双向链表,这个毫无疑问,地球人都知道,这就使得LinkedList有了链表结构的一...

FuYung
2015/11/10
516
3
从源码角度看LinkedList一些基本操作(jdk1.7)

介绍 LinkedList是一个双向链表,就像下图展示那样,每个节点有个指向上个元素和一个指向下个元素的指针。 接下来我会对我们经常使用的方法进行介绍,代码如下 @Testpublic void testLinkedL...

勿妄
2018/04/03
0
0
Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理

Java2的集合框架,抽其核心,主要有三种:List、Set和Map。如下图所示: 需要注意的是,这里的 Collection、List、Set和Map都是接口(Interface),不是具体的类实现。 List lst = new Array...

止静
2014/09/19
125
1
Java并发编程笔记之ConcurrentHashMap原理探究

在多线程环境下,使用进行操作时存在丢失数据的情况,为了避免这种bug的隐患,强烈建议使用代替 HashTable是一个线程安全的类,它使用synchronized来锁住整张Hash表来实现线程安全,即每次锁...

狂小白
2018/08/15
0
0
ArrayList/LinkedList 的底层分析

ArrayList ArrayList 实现于 List、RandomAccess 接口。可以插入空数据,也支持随机访问。 ArrayList相当于动态数据,其中最重要的两个属性分别是: elementData 数组,以及 size 大小。 在调...

如同相见恨晚
07/09
25
0

没有更多内容

加载失败,请刷新页面

加载更多

秒杀系统思路

业务分析 技术挑战 请求响应要快:无论成功失败,需要尽快返回给用户 架构设计   前端:静态化   站点层:限制请求数   服务层:乐观锁写缓存   数据库CAP:读写高可用,一致性,扩容...

雷开你的门
14分钟前
7
0
最全的教育行业大数据解决方案,个个针对痛点

大数据的悄然兴起也带动了教育行业的革新,移动教育、云课堂等的出现,使得教育行业再次成为了可以中长期保持高景气的行业。然而,初涉数据领域的教育行业同时也面临着相当大的难题,还需要更...

朕想上头条
18分钟前
5
0
预约模块设计分析

1.预约功能描述: 预约是小程序中常见的一种商品管理系统,商家可根据商品或服务的特性,灵活设置预约细节,为用户提供线上预约服务,如场地预约,商品预定等,实现高效经营。 预约场景: ...

鱼煎
21分钟前
4
0
阿里云日志服务构建网站实时分析大盘实战

场景分析 挖掘数据价值是当前企业级网站共同面临的问题。买买网是一个电商平台网站,每天拥有大量的用户访问和购买记录。为了引导用户直接消费,提升购买率和转化率,不同的用户类别需要推荐...

阿里云官方博客
22分钟前
2
0
TL665xF-EasyEVM开发板硬件处理器、NAND FLASH、RAM

广州创龙结合TI KeyStone系列多核架构TMS320C665x及Xilinx Artix-7系列FPGA设计的TL665xF-EasyEVM开发板是一款DSP+FPGA高速大数据采集处理平台,其底板采用沉金无铅工艺的6层板设计,适用于高...

Tronlong创龙
26分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部