程序猿的日常——Java中的集合列表

列表对于日常开发来说实在是太常见了，以至于很多开发者习惯性的用到数组，就来一个ArrayList，根本不做过多的思考。其实列表里面还是有很多玩法的，有时候玩不好，搞出来bug还得定位半天。所以这里就再啰嗦一下，整理下相关的内容。

基础知识

一般计算机相关的专业都应该学过数据结构，而很多的集合都是应用了经典的数据结构设计的。比如数组、栈、队列、链表、树等等，里面也会用到很多常见的查找或者排序算法，所以就先简单的回顾下。

数组

数组在c语言里面用的很广泛，刚开始学习的时候，整天的空指针和数组越界。后来使用java，开始使用一些集合框架，基本都不用担心这个问题了。

简单的说，数组就是内存中的一段连续的空间，它对于随机访问或者针对某个索引的修改特别快，因为直接可以根据下标索引访问。不过针对于在指定位置插入节点或者删除指定位置的元素，会很慢，因为它会导致后面所有的元素都要移动一次空间。

栈

栈是一种先进后出，或者叫做后进先出的数据结构。比如我们在做数学公式计算的时候，就可以用栈保存，并进行相关的计算。另外，在java中栈的应用也很广，比如程序栈就是通过栈的方式存储的。

public void a(){ b();}
public void b(){ c();}
public void c(){}

那么在代码执行的时候，程序栈里面会记录:
a,b,c
这也是为什么一个方法出错，错误堆栈会打印出一大串的类名和方法名。如果了解这个知识点，对于看懂错误日志就很轻松了。

队列

队列一般都是特定的业务场景才需要使用，比如某个网站的排队功能或者是一些叫号功能，都是队列的机制。

链表

链表有很多种，有单向链表、双向链表、循环链表...每个都有不同的使用场景。在java中有一些复杂的集合类，就用到了链表，比如HashMap、HashTable、LinkedList等等,这个后面慢慢再说。

Java中的列表

ArrayList

这个是日常开发应用最广泛的List集合类了，如果不是有特殊要求，基本上这个类就能满足大部分的需求。不过它还是有很多需要注意的点，比如：

  • 非线程安全
  • 自动扩容
  • 适合场景

非线程安全

这个在javadoc上很明显的强调过，如果想要线程安全，可以使用Collections.synchronizedList进行包装，这个synchronizedList其实就是外面套了一层方法，具体的可以参考下面的简约代码:

static class SynchronizedList<E> ... {
    final Collection<E> c;
    final Object mutex;
    public boolean add(E e) {
        synchronized (mutex) {return c.add(e);}
    }
    ...
}

看到这里应该就了解它的线程安全方法了。

另外也可以使用Vector代替ArrayList，Vector是在方法上做的同步，相对来说要比上面更乐观一点。

最后还有一些高级的集合，比如CopyOnWriteArrayList，这个就更乐观了，之后再详细说。

自动扩容

在添加元素的时候，list会检查当前的容量是否已经满：

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

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

大致的流程是：

  1. 先判断当前容量和插入后的容量大小
  2. 如果容量不够，则增加当前容量*50%，即一半的大小
  3. 最后把数据增加到末尾

删除的时候，是直接移动删除位置以及后面的元素，然后把最后一个元素赋空:

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

modCount

很多的集合类都有一个modCount,在很多新增、修改、删除的方法中，都会对这个变量modCount++，他有什么作用？

因为很多集合都可以通过iterable来访问，这时候相当于list的快照，此时是不能修改列表元素的，不然会报错。这个modCount就是用来判断是否有修改的。

大概看下代码:

public Iterator<E> iterator() {
    return new Itr();
}
private class Itr implements Iterator<E> {
    ...
    int expectedModCount = modCount;
    ...
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        ...
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

适用的场景

因此，ArrayList适合大量随机读取和修改的场景，不太适合频繁删除和指定位置插入的场景。

LinkedList

LinkedList是基于链表的列表，因此具有删除节点新增节点很快的特性。可以简单看下它的内部结构：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> 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;
        }
    }
}

通过接口的声明，可以看出它的几个特性：

  1. 可以当作队列使用Deque,提供push,pop,offer,peek,poll等方法
  2. 支持序列化，内部使用transient修饰，自定义了序列化和反序列化的方法，节省空间
  3. 内部是一个静态内部类的Node节点

静态内部类和非静态内部类，有什么不同？1 静态内部类不需要外部的引用；非静态内部类需要。2 静态内部类只能访问外部类的静态成员，非静态内部类则没有限制。3 静态内部类可以独立创建，非静态内部类总不能。

它的新增和删除就是简单的列表操作了，没什么太要强调的：

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

如果是删除指定的位置，则需要判断改位置是离first最近，还是last最近，然后分别进行扫描:

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

查询指定位置的元素:

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

移除对应的元素:

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

Vector

Vector根ArrayList很像，只不过他是线程安全的

public synchronized boolean add(E e) {}
public synchronized boolean removeElement(Object obj) {}
...

并且扩容的时候，如果没有自己设置扩容的步长，就会扩大一倍

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

Stack

这个是继承于Vector的方法，提供了基本的堆栈功能。同时他也是线程安全的。

本文转自博客园xingoo的博客，原文链接：程序猿的日常——Java中的集合列表，如需转载请自行联系原博主。

时间： 2024-10-10 08:06:12

程序猿的日常——Java中的集合列表的相关文章

程序猿的日常——Java基础之抽象类与接口、枚举、泛型

再次回顾这些基础内容,发现自己理解的又多了一点.对于一些之前很模糊的概念,渐渐的清晰起来. 抽象类与接口 抽象类通常是描述一些对象的通用方法和属性,并且默认实现一些功能,它不能被实例化.接口仅仅是描述一种方法的规约,即只能通过某几个方法来操作对象,它把内部的实现隐藏到实现类中,自己仅仅关注使用而已. 参数 抽象类 接口 默认的方法实现 它可以有默认的方法实现 接口完全是抽象的.它根本不存在方法的实现 实现 子类使用extends关键字来继承抽象类.如果子类不是抽象类的话,它需要提供抽象类中所有声

程序猿的日常——Java基础之equals与hashCode

equals和hashCode是我们日常开发最常使用的方法,但是因为一般都使用默认的规则,因此也很少会引起关注.不过了解他们的用途和设计的原则,还是会帮助我们更好的设计代码. equals equals是java很基础的一个问题,通常都会跟==来做比较.那么看看下面的问题: int a = 1; int b = 1; System.out.println(a==b);//true Integer a1 = new Integer(1); Integer a2 = new Integer(1);

程序猿的日常——Java基础之clone、序列化、字符串、数组

其实Java还有很多其他的基础知识,在日常工作技术撕逼中也是经常被讨论的问题. 深克隆与浅克隆 在Java中创建对象有两种方式: 一种是new操作符,它创建了一个新的对象,并把对应的各个字段初始化成默认值: 另一种是用clone方法,基于已有的对象创建一个新的对象,此时会根据原有的对象各个字段赋值给新的对象. 如果对象的字段都是基础类型,没有什么问题,但是如果字段是对象,那么其实clone的时候复制的仅仅是对象的引用而已. 上面就是深克隆与浅克隆的区别. 在我们日常的开发中,如果涉及到克隆,就需

Java程序员的日常 —— Java类加载中的顺序

之前说过Java中类的加载顺序,这次看完继承部分,就结合继承再来说说类的加载顺序. 继承的加载顺序 由于static块会在首次加载类的时候执行,因此下面的例子就是用static块来测试类的加载顺序. package xing.test.thinking.chap7; class A{ static{ System.out.println("A static"); } } class B extends A{ static{ System.out.println("B stat

程序猿的日常——SpringMVC系统架构与流程回顾

web开发经历了很漫长的时间,在国内也快有十几年的时间了.从最开始的进程级到现在的MVC经历了很多的改进和优化,本篇就主要复习了解下Spring MVC相关的知识. 发展历程 第一阶段 CGI进程响应 这一阶段,服务器比较弱,请求也很简单,就是用户发一个请求,服务器接收后新建进程,然后返回结果. 这种方式一看代价就很大,每次都新建进程,很麻烦. 第二阶段 Servlet线程级别响应 Servlet结构跟上面差不多,只不过每次都只是新建一个线程,这样代价就小很多了. Servlet的生命周期有四个

深入剖析java中的集合框架_java

解析:如果并不知道程序运行时会需要多少对象,或者需要更复杂方式存储对象,那么可以使用Java集合框架. 如果启用集合的删除方法,那么集合中所有元素的索引会自动维护. 集合完全弥补了数组的缺陷. 02.集合框架的内容  集合框架都包含三大块内容:对外的接口,接口的实现和对集合运算的算法  01.接口:表示集合的抽象数据类型  02.实现:集合框架中接口的具体实现  03.算法:在一个实现了某个集合框架的接口的对象身上完成某种有用的计算方法 java集合框架简图:    01.Collection接

java中一个商品列表集合简单问题

问题描述 java中一个商品列表集合简单问题 java中一个商品列表集合简单问题 java中一个商品列表集合简单问题 肯德可以理解为对象,java一切都是对象 那么可以理解为一个类吗可以理解为一个数组吗,可以理解为一种数据泪腺吗 解决方案 对象集合类是类,但不能说对象集合的对象是一个类,对象就是类的实例,和类是不等的.数组是指基本数据类型集合.比如int [] arrs = new int[]{},而List 等类创建的对象集只能称为集合.不能理解为数据类型.数据类型只有基本类型和引用类型.

java 中list集合中对象的声明周期

问题描述 java 中list集合中对象的声明周期 list集合中存放是是堆中的对象,但如果堆中的对象被回收后就变成了空?还是只要list集合存在就不会被回收?如果会被回收的话,怎样保证集合内的数据在list存在时长期有效??求大牛帮助

浅谈java中对集合对象list的几种循环访问_java

java中对集合对象list的几种循环访问的总结如下  1 经典的for循环  public static void main(String[] args) { List<String> list = new ArrayList(); list.add("123"); list.add("java"); list.add("j2ee"); System.out.println("=========经典的for循环======