Java总结 - List实现类Vector&Stack

2022-04-25 01:24:42

由于之前对ArrayList和LinkedList的分析,所以在看Vector和Stack的源码实现就会非常简单

观察上图,我们可以看到本文要说的Stack和Vector是父子关系,我们依旧从源码入手,期望能够对你有帮助,如果本文有理解不对的地方,请及时指正,谢谢您

Vector

我们知道Vector的实现和ArrayList一样,都是底层以数组的方式存储的,但是不同的Vector是线程安全的,这一点我们可以从源码中看出来

定义

@since 1.0
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{...}

属性

//保存元素的数组
protected Object[] elementData;
//容量增量,就是数组按多少速度扩容,这里是2倍
protected int capacityIncrement;
//元素个数
protected int elementCount;
//最大容量,跟ArrayList一样的
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

对于属性列出了这几个,我们看到一些ArrayList中出现的属性值,可能是由于出现的过早的原因,其中的属性变量名定义的并不是很直观,比如elementCount在ArrayList中称为size
对于其中的方法实现的源码我就不列的很详细了,我看了一下,其实现基本都是在方法上加上了sync关键字

初始化

public Vector() {
    this(10);
}
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
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(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

如上实现较简单,我们从中可以看到,对于Vector的增量和初始化容量我们都可以进行自定义

add

跟之前的ArrayList的实现基本一致,所以就不再赘述

public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    elementCount = s + 1;
}

public void add(int index, E element) {
    insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    modCount++;
    final int s = elementCount;
    Object[] elementData = this.elementData;
    if (s == elementData.length)
        elementData = grow();
    //核心方法arrycopy,将要插入的位置挪出来
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = obj;
    elementCount = s + 1;
}

//逻辑跟ArrayList中的完全一致,不再赘述
public synchronized boolean addAll(int index, Collection<? extends E> c) {
    if (index < 0 || index > elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData = this.elementData;
    final int s = elementCount;
    if (numNew > elementData.length - s)
        elementData = grow(s + numNew);

    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    elementCount = s + numNew;
    return true;
}

对于上面代码我们基本都分析过了在ArrayList中,所以下面的方法我不打算都贴出来了,直贴一个实现相较复杂的实现,我们已经贴出增加的方法,下面我们凑齐CRUD

remove

public boolean remove(Object o) {
    return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
    modCount++;
    //indexOf方法就跟之前介绍的node方法一致,根据元素找出其位置
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}
public synchronized void removeElementAt(int index) {
  //检查索引
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    //j 就是要删除元素的位置
    int j = elementCount - index - 1;
    if (j > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    modCount++;
    elementCount--;
    elementData[elementCount] = null; /* to let gc do its work */
}

set

public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

get

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    return elementData(index);
}

上面实现没得可说的了,很简单,从中我们可以看出,Vector和ArrayList的实现之差一个sync,所以Vector是线程安全的,但是由于是线程安全的,所以Vector要比ArrayList要慢,因为锁竞争的原因,并且Vector的实现也不好,因为一个操作只能是一个线程进行操作,这样当竞争高的时候会慢的要死.

Stack

从最上面的类图中可以看到Stack是基于Vector实现的,是其子类,Stack是用于模拟栈这种数据结构,是指后进先出LIFO的容器,最后push进栈的元素,将最先被pop出栈,我们来看一下实现

定义

public
class Stack<E> extends Vector<E> {...}

属性

//由于父类Vector中的属性都是protected修饰,所以本类的属性就是使用了继承下来的Vector类中的属性

初始化

public Stack() {
}

push

自身的方法比较少,但是有些方法是直接调用了父类的默认实现,以提高代码的复用性,我们可以都来看一下

Stack:
public E push(E item) {
    addElement(item);
    return item;
}
Vector:
public synchronized void addElement(E obj) {
    modCount++;
    add(obj, elementData, elementCount);
}

add的实现就是从数组头开始一直加嘛,所以Stack就是这样的,依次往数组中添加

pop

public synchronized E pop() {
    E obj;
    //Vector:size
    int len = size();
    //Stack:peek
    obj = peek();
    //Vector:removeElementAt之前有贴实现的源代码
    removeElementAt(len - 1);
    return obj;
}

peek

public synchronized E peek() {
    ////Vector:size
    int len = size();
    if (len == 0)
        throw new EmptyStackException();
    ////Vector:elemenAt方法是将len-1位置上的数据返回但是不删除
    return elementAt(len - 1);
}

search

public synchronized int search(Object o) {
    //Vector:lastIndexOf,从0开始一直往后循环搜索,遇到第一个相等的返回相同元素的index
    int i = lastIndexOf(o);
    if (i >= 0) {
        return size() - i;
    }
    //代表不存在
    return -1;
}

这就是一些核心的方法了,实现起来还是很简单的,所以我就没有很大篇幅的一句句注释,但是需要注意的是,Stack的出入栈都是Object的,那么Stack是一种栈结构,我们除了使用Stack,也可以考虑ArrayDeque
ArrayDeque底层是基于数组实现的,所以其性能也是很好的

队列和栈

说到了上面的Stack实现类,那么我们就应该再去了解一下,看看List中有哪些实现类可以直接拿过来当做队列或者栈使用,我们之前介绍的LinkedList就可以,我们已经分析过了,所以我们这就不再详细说LinkedList了
我们看一张类图

Queue代表队列的抽象,而Deque是其一个子类,其进一步扩充了Queue的方法,Deque就既可以实现栈又可以实现队列了,我们分别看一下其中的方法定义
```
Queue:
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
```

上面一些方法的作用和区别如下,摘自 CSDN

add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断

remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，但是新的 poll() 方法在用空集合调用时只是返回 null。因此新的方法更适合容易出现异常条件的情况。

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

然后是Deque的方法

void push(E e);
E pop();
void addFirst(E e);
...

方法较多,但是我们从push和pop已经看出,Deque接口已经为我们定义了栈的操作,所以我们可以使用Deque的具体实现类来完成栈和队列的操作,我们在这使用的是ArrayDeque

public static void main(String[] args) throws Exception {
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("A");
    queue.offer("B");
    queue.offer("C");
    System.out.println(queue.poll());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
    //ABC
    Deque<String> stack = new ArrayDeque<>();
    stack.push("A");
    stack.push("B");
    stack.push("C");
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    //CBA
}

在这我先不仔细分析ArrayDeque类,打算再单独写一下这个类,现在我们只要知道他可以作为栈或者队列就可以了
还有一种队列,是有序队列,如PriorityQueue,下面是他的实现方法,既然是保证了元素的有序,那么添加进入的元素肯定是实现Comparable接口的,这里所说的有序不是加入顺序,而是排列顺序,所以这个类就可以定制排序了,下面只是介绍一下使用方法,具体的分析我会跟ArrayDeque一起写出来的.
```
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(1);
queue.add(10);
queue.add(3);
queue.add(7);
//[1, 7, 3, 10]
System.out.println(queue);
int size = queue.size();
for (int i = 0; i < size; i++) {
    //1 3 7 10
    System.out.println(queue.poll());
}
```

然后是定制排序

Comparator<Integer> comparator = (x,y) -> - Integer.compare(x,y);

将上面对象传入构造参数中就可以实现数值的从大到小输出

各种线性表的性能分析

Java提供的List就是一个线性表接口,而ArrayList,LinkedList又是线性表的两种典型实现:基于数组的线性表和基于链的线性表.Queue代表了队列,Deque代表了双端队列,既可以作为队列使用,又可以当做栈使用
LinkedList集合不仅提供了List的功能,还提供了双端队列,栈的功能
一般来说,由于数组以一块连续内存区来保存所有的数组元素,所以数组在随机访问时性能最好,所有的内部以数组作为底层实现的集合在随机访问时性能都比较好.而内部以链表作为底层实现的集合在执行插入,删除操作时有较好的性能.但总体来说,ArrayList的性能比LinkedList的性能要好.因此大部分时候都应该考虑使用ArrayList.
使用List集合的一些建议
- 如果需要遍历List集合,对于ArrayList,Vector集合,应该是用随机访问方法get来遍历集合元素,这样性能更好.对于LinkedList集合,则应该采用迭代器Iterator来遍历集合元素.
- 如果需要经常执行插入,删除操作来改变含大量数据的List集合的大小,则可考虑使用LinkedList集合,使用ArrayList,Vector集合可能需要经常分配内部数组的大小.效果可能较差.
- 如果有多个线程需要访问List集合中的元素,需要考虑使用Collections将几个包装成线程安全集合.

码农公寓