内容简介:程序猿的日常——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); }
大致的流程是:
- 先判断当前容量和插入后的容量大小
- 如果容量不够,则增加
当前容量*50%
,即一半的大小 - 最后把数据增加到末尾
删除的时候,是直接移动删除位置以及后面的元素,然后把最后一个元素赋空:
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; } } }
通过接口的声明,可以看出它的几个特性:
- 可以当作队列使用Deque,提供push,pop,offer,peek,poll等方法
- 支持序列化,内部使用transient修饰,自定义了序列化和反序列化的方法,节省空间
- 内部是一个静态内部类的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的方法,提供了基本的堆栈功能。同时他也是线程安全的。
以上所述就是小编给大家介绍的《程序猿的日常——Java中的集合列表》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 小程序云开发遇到的一些问题集合
- .NET 将多个程序集合并成单一程序集的 4+3 种方法
- Scala 中的集合(二):集合性能比较
- Scala 中的集合(二):集合性能比较
- 《面试知识,工作可待:集合篇》:Java 集合面试知识大全
- 如何对集合对象求合计,然后追加在该集合对象中
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Python编程初学者指南
[美]Michael Dawson / 王金兰 / 人民邮电出版社 / 2014-10-1
Python是一种解释型、面向对象、动态数据类型的高级程序设计语言。Python可以用于很多的领域,从科学计算到游戏开发。 《Python编程初学者指南》尝试以轻松有趣的方式来帮助初学者掌握Python语言和编程技能。《Python编程初学者指南》共12章,每一章都会用一个完整的游戏来演示其中的关键知识点,并通过编写好玩的小软件这种方式来学习编程,引发读者的兴趣,降低学习的难度。每章最后都会......一起来看看 《Python编程初学者指南》 这本书的介绍吧!