当前位置:首页 > 服务端 > List集合系列

List集合系列

2022年11月07日 20:48:31服务端14

一、 List集合全貌

List集合系列 _ JavaClub全栈架构师技术笔记

二、接口

  1. Collection接口
    Collection是一个接口,是高度抽象出来的集合,它包含了集合的基本操作和属性。包含了集合的基本操作:添加、删除、清空、遍历(读取)、是否为空、获取大小
  2. List接口
    在继承Collection接口的前提上,由于是链表,需要添加一些链表特有的接口方法:针对链表索引的增删改查
  3. Set接口
    Set是一个继承于Collection的接口,即Set也是集合中的一种。Set是没有重复元素的集合。
  4. Queue接口
    Set是一个继承于Collection的接口,添加队列的add.remove.poll.peek方法
  5. Deque接口
    继承于Queue,由于是双向队列,必然会添加一些针对头尾的接口方法
  6. Iterator:集合迭代器,包括:是否存在下一个元素、获取下一个元素、删除当前元素。迭代器遍历Collection时,采用Fail-fast机制,如果集合内容改变,线程抛出ConcurrentModificationException异常,解决方法是通过线程安全类java.util.concurrent

fail-fast参考:https://www.cnblogs.com/skywang12345/p/3308762.html

  1. ListIterator:是专门针对于List的迭代器接口

三、抽象类

  1. AbstractCollection:实现COllection中抽象方法,未实现iterator()和size(),由于不同集合对应处理方式不同
  2. AbstractList:实现List接口中的大部分方法(get(int index),size未实现,因为子类有数组结构与链表结构,获取元素的方式不同

内部静态实现迭代与链表迭代:
1、前序遍历添加了remove方法,此时需要考虑,正常抽象类已经实现remove方法,为什么会多此一举,因为在遍历获取对象的时候,修改集合本身元素就会导致无法继续遍历
2、链表迭代:新增了添加、是否存在上一个元素、获取上一个元素等等API接口。

List集合系列 _ JavaClub全栈架构师技术笔记
3. AbstractSet:由于接口方法就与Collection相同,因此实现方法也与AbstractCOllection相同
4. AbstractSequentialList:这个抽象类就已经比较具体,具体的含义是指,它是LinkedList的父类,表明处理的类型已经确定,所以针对get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)已经实现。

注意:此时AbstractSequentialList的实现只是逻辑上的实现, public abstract ListIterator<E> listIterator(int index);返回一个ListIterator接口类,因此真正的内部实现函数需要继承子类实现(也就是LInkedList实现)

比如:
AbstractSequentialList的add()

 public void add(int index, E element) {
        try {
            listIterator(index).add(element);//这里的add方法是接口方法,等待LInkedlist实现后才能使用
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

LIkedList实现add:

 public boolean add(E e) {
        linkLast(e);//调用了该函数,属于LinkedList的核心函数之一
        return true;
    }

四、ArrayList

(一)实现接口

ArrayList 继承了AbstractList,实现了List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandmoAccess接口,即提供了随机访问功能。随机访问就是通过索引去获得元素
ArrayList 实现了Cloneable接口,即覆盖了函数clone(),能被克隆。
ArrayList 实现java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输。

(二)属性

1、DEFAULT_CAPACITY=10默认容量=10
2、 transient Object[] elementData;存储结构采取动态数组
3、 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;最大数组长度

(三)构造函数

1、public ArrayList(Collection<? extends E> c) 构造函数接受一个集合参数
2、 public ArrayList(int initialCapacity) :构造函数设定初始容量
3、 public ArrayList():初始化一个空数组

(四)核心源码

1、增加

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!modCount用来实现ailfast,遍历的时候修改集合就会导致modCount改变,抛异常,每一次添加元素之前都会判断数组是否需要扩容
        elementData[size++] = e;
        return true;
    }

2、指定位置增加集合

 public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        Object[] a = c.toArray();//集合转化为数组
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount,是否扩容
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);//导致性能变差
        size += numNew;
        return numNew != 0;
    }

arraycopy()是个JNI函数,它是在JVM中实现的。 System.arraycopy(elementData, index, elementData, index + 1, size - index); 会移动index之后所有元素即可。这就意味着,ArrayList的add(int index, E element)函数,会引起index之后所有元素的改变
3、扩容
每次增长为原来的1.5倍,如果一开始知道数据量很大的话,可以在初始化时预先指定容量。

 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容为原来1.5
        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);
    }

4、返回元素索引位置

  public int indexOf(Object o) {
        if (o == null) {//元素为空
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {//元素不为空
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

5、大部分函数都比较容易理解,大致翻一翻源码就行

(五)迭代方式

1、迭代器遍历

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

2、随机访问,索引值遍历

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

3、foreach遍历

Integer value = null;
for (Integer integ:list) {
    value = integ;
}

随机访问效率最高,迭代访问效率最低,实现RandomAccess接口的集合类,使用for循环的效率会比Iterator高。
RandomAccess接口为ArrayList带来的好处:
1、可以快速随机访问集合。
2、使用快速随机访问(for循环)效率可以高于Iterator

五、Linkedlist

(一)实现接口

继承AbstractSequentialList双向链表,可以作为队列、栈、或者双端队列使用;
覆盖clone(),能够克隆;
实现Serializable,能够序列化与反序列化

(二)属性

1、transient int size = 0;链表容量
2、transient Node<E> first;链表头结点
3、transient Node<E> last;链表尾节点

(三)构造函数

1、public LinkedList()无参构造函数
2、public LinkedList(Collection<? extends E> c)接受集合作为参数,内部调用addAll方法,先将集合转化为数组,之后采用头插法,插入到链表

(四)核心源码

1、四个函数大致类似,无非就是链表节点的操作分别是first前添加元素,last后添加元素,某个节点前添加元素,删除first指向的元素,删除last指向的元素,删除某一个元素。以下六个函数包含了构成了LinkedList的核心,其余操作一般是这六个函数的封装。
List集合系列 _ JavaClub全栈架构师技术笔记
2、其余大部分函数
List集合系列 _ JavaClub全栈架构师技术笔记
3、LinkedList实现queue (双向链表尾部插入元素,头部获取元素)

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

4、LinkedList实现stack(双向链表头部插入元素,头部获取元素)

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

(五)迭代方式

可以通过随机访问方式、迭代器遍历的方式、for循环的方式,使用removeFist()或removeLast()方式去访问,使用removeFist()或removeLast()效率最高。但用它们遍历时,会删除原始数据;若单纯只读取,而不删除,应该使用for循环的方式,一定不要去使用随机访问去遍历。

for (Integer integ:list) {
	//综合来说最优
}

六、Vector

(一)实现接口

AbstractList它是一个队列,支持相关的添加、删除、修改、遍历等功能;随机访问;克隆对象
最重要:它是线程安全(只是因为添加synchronized关键字同步)

(二)属性

1、protected Object[] elementData;存储元素
2、protected int elementCount;动态数组的实际大小。
3、protected int capacityIncrement;设定每次和扩容的数量,如果设置为0,则新的容量是原来容量的2倍

(三)构造函数

1、public Vector(int initialCapacity, int capacityIncrement)设置容量与扩容系数的构造函数
2、public Vector(int initialCapacity)设置容量与扩容系数=0的构造函数
3、设置容量=10与扩容系数=0的构造函数

 public Vector() {
                this(10);
            }

4、public Vector(Collection<? extends E> c)接收集合作为参数的构造函数

(四)核心源码

1、增加元素(追加的方式)
添加元素之前都会检查Vector容量,当Vector的容量不足以容纳当前的全部元素,增加容量大小。

//添加单个元素
public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);//确保容量充足
        elementData[elementCount++] = e;//数组结构存储
        return true;
    }
 //添加集合元素
 public synchronized boolean addAll(Collection<? extends E> c) {
        modCount++;
        Object[] a = c.toArray();//转换为数组
        int numNew = a.length;
        ensureCapacityHelper(elementCount + numNew);//判断是否扩容
        System.arraycopy(a, 0, elementData, elementCount, numNew);//数组拷贝
        elementCount += numNew;
        return numNew != 0;
    }

2、扩容

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?//是否设置扩容系数,等于0,扩容为原来2倍,不等于0,增加扩容系数
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);//复制元素
    }

3、指定位置插入元素public void add(int index, E element)包括在指定位置插入集合方法内部依旧是调用的数组拷贝System.arraycopy
4、根据索引查找元素
以下两个函数内部都调用了elementData(int index)来获取元素

public synchronized E elementAt(int index) 
public synchronized E get(int index)
 @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

5、找到集合中包含元素的第一个索引位置

public synchronized int indexOf(Object o, int index) {
        if (o == null) {//null元素
            for (int i = index ; i < elementCount ; i++)
                if (elementData[i]==null)
                    return i;
        } else {//其余元素
            for (int i = index ; i < elementCount ; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;//未找到
    }

6、排序

 public synchronized void sort(Comparator<? super E> c) {//可以通过集成Comparator实现自己的排序规则
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, elementCount, c);//调用Arrays排序
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

7、添加的方式包括:添加元素、指定位置添加元素、指定位置添加集合、添加剂和
List集合系列 _ JavaClub全栈架构师技术笔记
删除的方式包括:删除指定位置元素、删除当前元素(第一次出现)、删除集合
List集合系列 _ JavaClub全栈架构师技术笔记
8、转化为静态数组

//返回数组
 public synchronized Object[] toArray() {
        return Arrays.copyOf(elementData, elementCount);
    }
//返回指定长度的数组
 public synchronized <T> T[] toArray(T[] a) {
        if (a.length < elementCount)
            return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());//指定数组长度不够,则只拷贝指定数组长度的元素

        System.arraycopy(elementData, 0, a, 0, elementCount);//全部元素拷贝

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

        return a;
    }

(五)迭代方式

遍历方式:迭代器、随机访问、for循环(语法糖)
遍历Vector,使用索引的随机访问方式最快,使用迭代器最慢。

(六)Stack(封装了Vector的方法)

Stack继承了Vector,本来想把栈单独一个模块提出来的,但是stack就是Vector方法的封装,再往简单的理解:栈就是通过数组来实现的,在数组尾部添加元素,尾部获取元素,删除尾部元素,通过一个索引自己搞定。

八、对比性能

ArrayLIst与LinkedList与Vector

1、ArrayLis和vector底层结构是数组,LinkedList底层结构是双向链表
2、使用场景:
     对于需要快速插入,删除元素,应该使用LinkedList。
     对于需要快速随机访问元素,应该使用ArrayList。
     单线程环境使用ArrayList,多线程环境使用同步类(Vector)
3、性能分析:
     LinkedList通过链表指针形式插入元素,因此速度快,而ArrayList选择 System.arraycopy系统即时编译方法,其实自己想一下就可以直到,数组添加删除元素都需要移动后边的数组元素,自然而然慢
     ArrayList获取元素,直接数组索引查找,而LinkedList需要遍历节点查找元素,自然而然慢
4、
ArrayList实现了RandomAccess随机访问接口,因此它对随机访问的速度快,而基本的for循环中的get()方法,采用的即是随机访问的方法,因而在ArrayList中,for循环速度快。
LinkedList采取的是顺序访问方式,iterator中的next()方法,采用的即是顺序访问方法,因此在LinkedList中,使用iterator的速度较快。

ArrayLIst与Vector

相同点:
1、底层数据结构为数组
2、可以随机访问和克隆
3、默认初始容量都为10
4、都支持迭代器遍历
不同点:
1、ArrayList是非线程安全,而Vector是线程安全的(synchronized关键字实现)
2、构造函数:相同功能的构造函数3个:空构造函数、集合作为参数的构造函数、设置容量的初始函数
     但是Vector构造函数需要设置扩容系数(来把握扩容的数量)
3、容量增长方式:Vector如果设置扩容系数,则扩容相应的扩容系数个,否则扩容2倍
     ArrayList扩容为原来的1.5倍

引用

【1】极力推荐:https://www.cnblogs.com/skywang12345/p/3323085.html

作者:洛豳枭薰
来源链接:https://blog.csdn.net/qq_32679835/article/details/93195910

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/server/68440.html

标签: List
分享给朋友: