欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

ArrayList和LinkedList学习

程序员文章站 2022-09-22 15:28:10
ArrayList和LinkedList是对List接口的不同数据结构的实现。它们都是线程不安全的,线程不安全往往出现在数组的扩容、数据添加的时候。 ......

摘要

arraylist和linkedlist是对list接口的不同数据结构的实现。它们都是线程不安全的,线程不安全往往出现在数组的扩容、数据添加的时候。

一、arraylist和linkedlist是什么?

arraylist:arraylist是list接口的可变数组的实现。

linkedlist:linkedlist是list接口的(双向)链表实现。

二、两个list的数据结构

1、arraylist的数据结构

arraylist的类继承图如下:

ArrayList和LinkedList学习

(1-1:arraylist的类继承图)

存储

arraylist使用数组(elememntdata)存储数据,默认构造方法创建arraylist时,会初始化一个空数组。

扩容

arraylist使用数组存储数据,因此在添加数据的时候需要做容量检查,如果容量不足则需要进行扩容。

其新容量大小公式为:新容量=旧容量+旧容量/2

扩容过程请看下面源码:

public boolean add(e e) {
    // 容量检查
    ensurecapacityinternal(size + 1);  // increments modcount!!
    elementdata[size++] = e;
    return true;
}

// 计算数组需要的最小容量
private void ensurecapacityinternal(int mincapacity) {
    if (elementdata == defaultcapacity_empty_elementdata) {
        mincapacity = math.max(default_capacity, mincapacity);
    }

    ensureexplicitcapacity(mincapacity);
}

// 判断是否需要扩容,如果需要则扩容
private void ensureexplicitcapacity(int mincapacity) {
    // modcount表示list结构修改的次数,快速失败机制会用到,快速失败机制在后面会详细说明。
    modcount++;

    // overflow-conscious code
    if (mincapacity - elementdata.length > 0)
        grow(mincapacity);
}

private void grow(int mincapacity) {
    // overflow-conscious code
    int oldcapacity = elementdata.length;
    // 新容量=旧容量+旧容量/2
    int newcapacity = oldcapacity + (oldcapacity >> 1);
    if (newcapacity - mincapacity < 0)
        newcapacity = mincapacity;
    if (newcapacity - max_array_size > 0)
        newcapacity = hugecapacity(mincapacity);
    // mincapacity is usually close to size, so this is a win:
    elementdata = arrays.copyof(elementdata, newcapacity);
}
(1-2:arraylist数组扩容源码)

2、linkedlist的数据结构

linkedlist的类继承图如下:

ArrayList和LinkedList学习

(2-1:linkedlist的类继承图)

存储

linkedlist使用双向链表来存储数据。其中链表结点定义如下:

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;
    }
}
(2-2:linkedlist的存储结点定义)

添加/删除元素操作

linkedlist添加删除元素,实际上就是对链表进行结点添加/删除,下面给出实现细节,以供后面的线程安全讨论使用(注意modcount发生了变化)。

// 添加元素
public boolean add(e e) {
    // 往链表末尾添加元素
    linklast(e);
    return true;
}
// 添加结点
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++;
}

// 删除元素(删除第一个匹配的元素)
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;
}
// 删除结点
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;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

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

    x.item = null;
    size--;
    modcount++;
    return element;
}
(2-3:linkedlist添加/删除结点关键代码)

三、线程安全讨论

首先确认一点的是,arraylist和linkedlist均是线程不安全的,下面将分析多线程情况下会出现的一些问题。

1、快速失败(fail-fast)

快速失败,指的是使用遍历器对list进行遍历时,如果在遍历过程中,对list进行了修改,则会触发快速失败机制,抛出java.util.concurrentmodificationexception异常。

快速失败触发机制

前文谈到modcount的作用用于记录list的修改次数,在遍历器进行遍历时,代码正是通过这个值触发快速失败的。

相关核心代码如下:

int expectedmodcount = modcount;

public e next() {
    checkforcomodification();
    try {
        int i = cursor;
        e next = get(i);
        lastret = i;
        cursor = i + 1;
        return next;
    } catch (indexoutofboundsexception e) {
        checkforcomodification();
        throw new nosuchelementexception();
    }
}

// 检查修改次数,该方法在类中多次会被调用
final void checkforcomodification() {
    if (modcount != expectedmodcount)
        throw new concurrentmodificationexception();
}
(1-1:java.util.abstractlist内部类itr代码片段)

2、arraylist添加元素时的数组越界问题

添加元素时的数组越界问题发生在扩容判断上,当当前数组容量还差一个元素达到数组扩容的临界值时。并发插入元素时对数组大小的判断均是无需扩容,但是当前数组实际上仅有一个空闲位置,因此数组越界异常就发生了。

3、添加元素被覆盖

这种异常出现情况如下面代码注释所示:

多个线程对数组同一个位置进行赋值,导致元素被覆盖。

elementdata[size++] = e;
// elementdata[size] = e;  --- thread1
// elementdata[size] = e;  --- thread2
// size++; --- thread1
// size++; --- thread2
(3-1:arraylist添加元素被覆盖)

类似的分析,linkedlist添加元素时也会出现这种情况。

4、线程安全的list

同步方法

全部使用同步方法,如:vector、collections.synchronizedlist(list)

其它加锁

其它加锁实现线程安全,如:concurrentlinkeddeque(自旋+cas)、copyonwritearraylist(读写锁)

参考资料