List与Set

发布于 2022年 05月 19日 13:04

List集合是Collection集合的子接口,其中的元素有序,并且可重复,元素可以通过下标访问。

接囗特有且常用的方法

1.add(int index, E element)

void add(int index, E element);

将指定的数据element存储到集合的指定索引index位置上。如果这个索引上存有元素就把原有的元素和随后的元素向右移动1位(在它们索引上加一),再将存储element

该方法会进行范围检查,如果不在这个范围的会报:java.lang.IndexOutOfBoundsException异常

2.get(int index)

E get(int index);

获取集合中指定索引上的元素

该方法会进行范围检查,如果不在这个范围的会报:java.lang.IndexOutOfBoundsException异常

3.indexOf(Object o)

int indexOf(Object o);

返回指定元素在这个列表中第一次出现的索引,如果这个列表不包含该元素,则返回-1

4.lastIndexOf(Object o)

int lastIndexOf(Object o);

返回指定元素在这个列表中最后出现的索引,如果这个列表不包含该元素,则返回-1。

5.remove(int index)

E remove(int index);

删除集合中指定索引处的元素,并将后面的元素向左移动(从它们的索引中减一)

返回被删除的元素

6.set(int index, E element)

E set(int index, E element);

用指定的元素替换这个列表中指定位置的元素

ArrayList


/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access

其底层采用了数组数据结构,其默认容量是10

构造方法

ArrayList有两种初始化

//面向接口
//默认容量10
List list = new ArrayList();
//自定义集合容量20
Lsit list1 = new ArrayList(20);

使用无参构造,底层会先给赋一个长度为0的数组,在添加第一个元素时,再把容量设为10

扩容

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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.5倍。elementData会指向这个新数组,旧数组会被回收。

如果新容量减去最小容量小于0,则最终扩容的容量为最小容量

Q:建议尽可能减少扩容,因为数组的扩容效率较低

增删元素

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

由源码可知,ArrayList在向某个索引增加或删除元素时底层会调用System.arraycopy,而这一操作极为消耗资源

在涉及到频繁插入和删除元素的情况下,LinkedList是首选,因为它只需要添加或删除节点,并重新链接现有的节点。

优缺点

优点:ArrayList底层是数组,元素间的内存地址是相连的,其检索效率高,向末尾添加元素效率也高。

而日常工作最常用到的是向末尾添加元素。

缺点:随机增删元素效率低,且消费高;数组不适合存储大数据,因为内存空间没有很大的一块地方分配给它

[Data Analytics]

链表


链表的基本单元是节点:Node

单向链表

对于单向链表,任意的Node都有两个属性,一个是存储数据,另一个则存储的是下一节点的内存地址

其中最后一个节后存储内存地址的部分指向空值(null)

链表中各节点内存地址并不连续,要寻找某个元素时,要从头节点开始查,靠上一节点内部的属性记录下一节点的内存地址。

随机增删元素不会涉及大量节点位移。删除或增加某个节点时,上一节点要重新记录下一节点的内存地址

双向链表

与单向链表相似,不过Node还多了一个存储上一节点内存地址的属性

在删除或增加某个节点时,上一节点要重新记录下一节点的内存地址,下一节点也要记录上一节点的内存地址

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;

底层采用双向链表存储数据,first、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,用于存储节点信息

初始化

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

无论使用哪种构造,都会调用无参构造

在LinkedList类中,并未对链表的容量作说明,而从构造方法可以看出LinkedList是一个无界限的链表,可以不限容量存储

方法

1.添加元素

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

add方法向尾部添加元素。

首先方法内部对象 l 会保存链表尾部节点,然后创建新节点,将新节点的 prev 节点信息关联到链表当前的尾节点,并把新节点的 next 节点赋值null。再将新创的节点newNode更新为链表的尾部节点 last 。再对内部变量 l 做非空引用判断,如果对象 l 引用为空,则表示当前链表中没有节点,把首节点 first 也更新为newNode;如果对象 l 引用不为空,则把newNode节点与对象 l 指向节点的next属性关联。最后再把节点个数加1,集合修改次数加1

public void add(int index, E element) {
    checkPositionIndex(index);

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

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

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

向指定索引添加节点。

与上面的add方法基本一致,不同的是要让索引index的上一节点与下一节点重新关联新的节点

2.删除节点

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

删除元素为 o 的节点

要先对链表遍历,因为LinkedList可以存储null值,所以需要进行null判断。判断这个节点是不是首尾节点,让上一节点的next属性与 x 节点的next关联,或让下一节点的pre属性与 x 节点的pre关联,将x的next 、 prev 、 item设为null。因为 x 节点没有被使用,后面会被垃圾回收器回收

3.更新节点数据

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

更新指定节点存储的元素

4.是否包含元素

public boolean contains(Object o) {
    return indexOf(o) != -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;
}

判断元素是否存在于链表中

特有方法

1.获取首或尾节点元素

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

返回首节点或尾节点存储的元素

优缺点

因为节点的内存地址不连续,随机增删元素不会导致大量的元素产生空间位移,随机增删元素效率高。但不能通过数学表达式查找元素的内存地址,每次查找元素都要去遍历链表,检索效率低

Vector


/**
 * The array buffer into which the components of the vector are
 * stored. The capacity of the vector is the length of this array buffer,
 * and is at least large enough to contain all the vector's elements.
 *
 * <p>Any array elements following the last element in the Vector are null.
 *
 * @serial
 */
protected Object[] elementData;

/**
 * The number of valid components in this {@code Vector} object.
 * Components {@code elementData[0]} through
 * {@code elementData[elementCount-1]} are the actual items.
 *
 * @serial
 */
protected int elementCount;

/**
 * The amount by which the capacity of the vector is automatically
 * incremented when its size becomes greater than its capacity.  If
 * the capacity increment is less than or equal to zero, the capacity
 * of the vector is doubled each time it needs to grow.
 *
 * @serial
 */
protected int capacityIncrement;

和ArrayList一样,其底层也是数组;elementCount是记录这个数组的有效元素个数;capacityIncrement是每次扩容的大小,如果容量增量小于或等于零,每次需要增长时,向量的容量就会增加一倍。

构造方造

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

从其底层的构造方法可以看出,默认的数组长度为10。

扩容

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;  //10
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

如果在初始化时没有对 capacityIncrement 赋值,那其默认的扩容容量是原容量的两倍

线程安全

Vector中所有的方法都有synchronized线程同步,是线程安全的

java.util下还有个Collections集合工具类,其中有synchronizedList()方法,可以把List接口下的非线程安全集合转换成线程安全的

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

返回一个由指定列表支持的同步(线程安全)的列表

当用户在返回的列表上进行迭代时,必须对其进行手动同步,否则可能会导致非确定性的行为,例:

List list = Collections.synchronizedList(new ArrayList))。
            ...
synchronized (list) {
	Iterator i = list.iterator(); // 必须在同步块中进行
	while (i.hasNext())
		foo(i.next())
}

Set


其元素无序、不可重复

Set接口的方法基本与Collection一致。由于元素无序,Set中元素没有下标,所以没有set和get、index等从索引上访问元素的方法

与List集合一样可以通过迭代器或forEach、for循环完成遍历

推荐文章