Java集合详解

您所在的位置：网站首页 › java里的long什么意思 › Java集合详解

Java集合详解

2024-02-24 06:58| 来源: 网络整理| 查看: 265

简述

上章简单介绍了什么是集合，集合有哪几种种类。在这章中我们主要介绍Collection的其中一种实现方式，List。

什么是List

在上一章，我们已经了解了List主要分为3类，ArrayList， LinkedList和Vector。为了进一步清晰List的结构，我在这手工画了一张图，用于回顾下

这里写图片描述

AbstarctCollection在上一张Java集合详解–什么是集合已经有简单的介绍，它是Collection接口的部分实现

1.List接口

首先看下List的官方定义

这里写图片描述

这段描述解决了许多公司经常问的两个问题List有什么特点和Set有什么区别。上面清楚的说明了List是一个有序的集合，和set不同的是，List允许存储项的值为空，也允许存储相等值的存储项，还举了e1.equal(e2)的例子。

List是继承于Collection接口，除了Collection通用的方法以外，扩展了部分只属于List的方法。

这里写图片描述

从上图可以发现，List比Collection主要多了几个add（…）方法和remove(…)方法的重载，还有几个index(…)， get(…)方法。而AbstractList也只是实现了List接口部分的方法，和AbstractCollection是一个思路，这里就不具体介绍了，有兴趣的同学可以自行研究下。

2.ArraryList

ArrayList是一个数组实现的列表，由于数据是存入数组中的，所以它的特点也和数组一样，查询很快，但是中间部分的插入和删除很慢。我们来看几段关键的代码。

首先是ArrayList的类关系和成员变量

//ArrayList继承了Serializable并且申明了serialVersionUID，表示ArrayList是一个可序列化的对象，可以用Bundle传递 public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 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 == EMPTY_ELEMENTDATA will be expanded to * DEFAULT_CAPACITY when the first element is added. */ //从这里可以看到，ArrayList的底层是由数组实现的，并且默认数组的默认大小是10 private transient Object[] elementData; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;

然后是构造函数

//ArrayList有2个构造函数，一个是默认无参的，一个是传入数组大小的 //在JavaEffect书中明确提到，如果预先能知道或者估计所需数据项个数的，需要传入initialCapacity //因为如果使用无参的构造函数，会首先把EMPTY_ELEMENTDATA赋值给elementData //然后根据插入个数于当前数组size比较，不停调用Arrays.copyOf()方法，扩展数组大小 //造成性能浪费 /** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */ public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; }

然后是add()操作

//首先看到，不过是指定index执行add操作，还是在尾部执行add操作，都会先确认当前的数组空间是否够插入数据 //并且从 //int oldCapacity = elementData.length; //int newCapacity = oldCapacity + (oldCapacity >> 1); //if (newCapacity - minCapacity < 0) // newCapacity = minCapacity; //看出，ArrayList默认每次都是自增50%的大小再和minCapacity比较，如果还是不够，就把当的 //size扩充至minCapacity //然后，如果是队尾插入，也简单，就把数组向后移动一位，然后赋值 //如果是在中间插入，需要用到System.arraycopy，把index开始所有数据向后移动一位 //再进行插入 /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return true (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ 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++; } private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } 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); }

然后是remove操作

//个人感觉整个remove操作的代码写了很冗余，不像甲骨文这些大神的风格 //首先来看remove(int index) //先进行边界确认，传入的index是否超过了当前数组的大小，如果是抛出异常 //如果在数组范围内，就把index之后的数据整体向前移动一位，最后一位值清空 //如果是remove(Object o)，传入的是一个对象，就会进行一次indexOf的操作，去当前数组中寻找 //判断是否存在，这里的代码就十分冗余了，就是把indexOf的代码拷贝了一次，完全可以调用indexOf方法 //根据返回值是否为-1来判断该值是否存在，如果存在就调用fastRemove方法 //fastRemove(int index)和remove(int index)方法除了边界检查一模一样 //完全可以在remove调用完rangeCheck(index)后调用fastRemove就可以了 //这里不是很明白设计者的意图 /** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */ 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; } /** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * i such that * (o==null;?;get(i)==null;:;o.equals(get(i))) * (if such an element exists). Returns true if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return true if this list contained the specified element */ public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /* * Private remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(int index) { modCount++; 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 }

indexof

//这里就和上面remove寻找是一模一样的，就不进行探讨了 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; }

3.Vector

Vector就是ArrayList的线程安全版，它的方法前都加了synchronized锁，其他实现逻辑都相同。如果对线程安全要求不高的话，可以选择ArrayList，毕竟synchronized也很耗性能

4.LinkedList

故名思意就是链表，和我们大学在数据结构里学的链表是一会事，LinkedList还是一个双向链表。

这里写图片描述

LinkedList继承于AbstractSequentialList,和ArrayList一个套路。内部维护了3个成员变量，一个是当前链表的头节点，一个是尾部节点，还有是链表长度。然后我们在来看下Node这个数据结构。

这里写图片描述

和C语言实现方式差不多，由于是双向链表，所以记录了next和prev，只不过把C语言里的指针换成了对象。

然后我们简单的在来看下链表额度查询，插入和删除操作

首先是add(E e)操作

//学过数据结构的同学看这部分代码特别轻松 //首先来看下void linkLast(E e)，尾部插入 //就是把newNode的前面节点执行现在的尾部节点，newNode的后面节点执行null,因为是在尾部嘛 //然后把现在的尾部节点的后面节点指向newNode,因为现在的尾部节点不是最后一个了 //然后再来看下中间插入 //也是一个套路。假设现在在3号位插入一个newNode //就是通过现在的3号Node的prev找到2号节点，然后修改2号节点的next，指向nowNode //然后nowNode的prev指向2号节点，next指向3号节点 //最后3号节点的prev变成了nowNode,next不变 //这样就完成了一次中间插入 /** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * Appends the specified element to the end of this list. * *

This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { final Node l = last; final Node newNode = new Node(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } /** * Inserts element e before non-null Node succ. */ void linkBefore(E e, Node succ) { // assert succ != null; final Node pred = succ.prev; final Node newNode = new Node(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }

然后是void linkLast(E e)操作

//indexOf操作非常简单，就是从头开始遍历整个链表，如果没有就反-1，有就返回当前下标 /** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index {@code i} such that * (o==null;?;get(i)==null;:;o.equals(get(i))), * or -1 if there is no such index. * * @param o element to search for * @return the index of the first occurrence of the specified element in * this list, or -1 if this list does not contain the element */ public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }

虽然indexOf非常简单，但是我在这还是写了个例子，帮助大家理解下

List list = new ArrayList(); list.add("zero"); list.add(null); list.add("two"); list.add(null); list.add("three"); Log.i("test", "index : " + list.indexOf(null));

在不看答案的情况下大家能准确的说出答案吗？

Answer:I/test: index : 1

从这个例子可以看出三点List的特征 1.是按顺序查找 2.允许存储项为空 3.允许多个存储项的值相等

最后看下remove操作

//如果直接调无参的remove(),就会默认删除头节点 //删除头节点非常简单，就是把头节点的值清空，next清空 //然后把nextNode只为头节点，然后清空next的prev //最后size减1 //如果是删除中间节点，调用remove(int index) //首先判断Index对应的节点是否为头节点，即index是否为0 //如果不是中间节点，就是x的prev指向x的next public E remove() { return removeFirst(); } public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } private E unlinkLast(Node l) { // assert l == last && l != null; final E element = l.item; final Node prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } /** * Unlinks non-null node x. */ E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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; } /** * Unlinks non-null first node f. */ private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }

总结

通过上面对ArrayList和LinkedList的分析，可以理解List的3个特性 1.是按顺序查找 2.允许存储项为空 3.允许多个存储项的值相等可以知其然知其所以然

然后对比LinkedList和ArrayList的实现方式不同，可以在不同的场景下使用不同的List ArrayList是由数组实现的，方便查找，返回数组下标对应的值即可，适用于多查找的场景 LinkedList由链表实现，插入和删除方便，适用于多次数据替换的场景

再下一章中，我们可以了解set是如何实现的，还有set又有哪些特性

【本文地址】

公司简介

联系我们