万户网站制作,手机网站绑定域名,福永镇网站建设,扬州工程建设信息 网站一、List简介 List 的数据结构就是一个序列#xff0c;存储内容时直接在内存中开辟一块连续的空间#xff0c;然后将空间地址与索引对应。 以下是List集合简易架构图
由图中的继承关系#xff0c;可以知道#xff0c;ArrayList、LinkedList、Vector、Stack都是List的四个…一、List简介 List 的数据结构就是一个序列存储内容时直接在内存中开辟一块连续的空间然后将空间地址与索引对应。 以下是List集合简易架构图
由图中的继承关系可以知道ArrayList、LinkedList、Vector、Stack都是List的四个实现类。
AbstractCollection 是一个抽象类它唯一实现Collection接口的类。AbstractCollection主要实现了toArray()、toArray(T[] a)、remove()等方法。AbstractList 也是一个抽象类它继承于AbstractCollection。AbstractList实现List接口中除size()、get(int location)之外的函数比如特定迭代器ListIterator。AbstractSequentialList 是一个抽象类它继承于AbstractList。AbstractSequentialList 实现了“链表中根据index索引值操作链表的全部函数”。ArrayList 是一个动态数组它由数组实现。随机访问效率高随机插入、随机删除效率低。LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低但随机插入、随机删除效率高。Vector 也是一个动态数组和ArrayList一样也是由数组实现。但是ArrayList是非线程安全的而Vector是线程安全的。Stack 是栈它继承于Vector。它的特性是先进后出(FILO, First In Last Out)。
下面对各个实现类进行方法剖析
二、ArrayList ArrayList实现了List接口也是顺序容器即元素存放的数据与放进去的顺序相同允许放入null元素底层通过数组实现。 除该类未实现同步外其余跟Vector大致相同。 在Java1.5之后集合还提供了泛型泛型只是编译器提供的语法糖方便编程对程序不会有实质的影响。因为所有的类都默认继承至Object所以这里的数组是一个Object数组以便能够容纳任何类型的对象。 常用方法介绍
2.1、get方法
get()方法同样很简单先判断传入的下标是否越界再获取指定元素。
public E get(int index) {rangeCheck(index);return elementData(index);
}/*** 检查传入的index是否越界*/
private void rangeCheck(int index) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}2.2、set方法
set()方法也非常简单直接对数组的指定位置赋值即可。
public E set(int index, E element) {rangeCheck(index);E oldValue elementData(index);elementData[index] element;return oldValue;
}2.3、add方法
ArrayList添加元素有两个方法一个是add(E e)另一个是add(int index, E e)。 这两个方法都是向容器中添加新元素可能会出现容量capacity不足因此在添加元素之前都需要进行剩余空间检查如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。
grow方法实现
private void grow(int minCapacity) {// overflow-conscious codeint 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);
}添加元素还有另外一个addAll()方法addAll()方法能够一次添加多个元素根据位置不同也有两个方法一个是在末尾添加的addAll(Collection? extends E c)方法一个是从指定位置开始插入的addAll(int index, Collection? extends E c)方法。
**不同点addAll()的时间复杂度不仅跟插入元素的多少有关也跟插入的位置相关时间复杂度是线性增长 **
2.4、remove方法
remove()方法也有两个版本一个是remove(int index)删除指定位置的元素另一个是remove(Object o)通过o.equals(elementData[index])来删除第一个满足的元素。
需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用必须显式的为最后一个位置赋null值。
remove(int index)方法
public E remove(int index) {rangeCheck(index);modCount;E oldValue elementData(index);int numMoved size - index - 1;if (numMoved 0)System.arraycopy(elementData, index1, elementData, index,numMoved);elementData[--size] null; //赋null值方便GC回收return oldValue;
}remove(Object o)方法
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;
}三、LinkedList 在上篇文章中我们知道LinkedList同时实现了List接口和Deque接口也就是说它既可以看作一个顺序容器又可以看作一个队列Queue同时又可以看作一个栈Stack。 LinkedList底层通过双向链表实现通过first和last引用分别指向链表的第一个和最后一个元素注意这里没有所谓的哑元某个参数如果在子程序或函数中没有用到那就被称为哑元当链表为空的时候first和last都指向null。 public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{/**容量*/transient int size 0;/**链表第一个元素*/transient NodeE first;/**链表最后一个元素*/transient NodeE last;......
}/*** 内部类Node*/
private static class NodeE {E item;//元素NodeE next;//后继NodeE prev;//前驱Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}常用方法介绍
3.1、get方法
get()方法同样很简单先判断传入的下标是否越界再获取指定元素。
public E get(int index) {checkElementIndex(index);return node(index).item;
}/*** 检查传入的index是否越界*/
private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}3.2、set方法
set(int index, E element)方法将指定下标处的元素修改成指定值也是先通过node(int index)找到对应下表元素的引用然后修改Node中item的值。
public E set(int index, E element) {checkElementIndex(index);NodeE x node(index);E oldVal x.item;x.item element;return oldVal;
}3.3、add方法
同样的add()方法有两方法一个是add(E e)另一个是add(int index, E element)。 add(E e)方法
该方法在LinkedList的末尾插入元素因为有last指向链表末尾在末尾插入元素的花费是常数时间只需要简单修改几个相关引用即可。
public boolean add(E e) {linkLast(e);return true;
}/*** 添加元素*/
void linkLast(E e) {final NodeE l last;final NodeE newNode new Node(l, e, null);last newNode;if (l null)//原来链表为空这是插入的第一个元素first newNode;elsel.next newNode;size;modCount;
}add(int index, E element)方法
该方法是在指定下表处插入元素需要先通过线性查找找到具体位置然后修改相关引用完成插入操作。
具体分成两步1.先根据index找到要插入的位置2.修改引用完成插入操作。
public void add(int index, E element) {checkPositionIndex(index);if (index size)//调用add方法直接在末尾添加元素linkLast(element);else//根据index找到要插入的位置linkBefore(element, node(index));
}/*** 插入位置*/
void linkBefore(E e, NodeE succ) {// assert succ ! null;final NodeE pred succ.prev;final NodeE newNode new Node(pred, e, succ);succ.prev newNode;if (pred null)first newNode;elsepred.next newNode;size;modCount;
}同样的添加元素还有另外一个addAll()方法addAll()方法能够一次添加多个元素根据位置不同也有两个方法一个是在末尾添加的addAll(Collection? extends E c)方法另一个是从指定位置开始插入的addAll(int index, Collection? extends E c)方法。
里面也for循环添加元素addAll()的时间复杂度不仅跟插入元素的多少有关也跟插入的位置相关时间复杂度是线性增长
3.4、remove方法
同样的remove()方法也有两个方法一个是删除指定下标处的元素remove(int index)另一个是删除跟指定元素相等的第一个元素remove(Object o)。 两个删除操作都是1.先找到要删除元素的引用2.修改相关引用完成删除操作。
remove(int index)方法
通过下表找到对应的节点然后将其删除
public E remove(int index) {checkElementIndex(index);return unlink(node(index));
}remove(Object o)方法
通过equals判断找到对应的节点然后将其删除
public boolean remove(Object o) {if (o null) {for (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);return true;}}} else {for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}删除操作都是通过unlink(NodeE x)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。
/*** 删除一个Node节点方法*/
E unlink(NodeE x) {// assert x ! null;final E element x.item;final NodeE next x.next;final NodeE 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类属于一个挽救的子类早在jdk1.0的时候就已经存在此类但是到了jdk1.2之后重点强调了集合的概念所以先后定义了很多新的接口比如ArrayList、LinkedList但考虑到早期大部分已经习惯使用Vector类所以为了兼容性java的设计者就让Vector多实现了一个List接口这才将其保留下来。
在使用方面Vector的get、set、add、remove方法实现与ArrayList基本相同不同的是Vector在方法上加了线程同步锁synchronized所以执行效率方面会比较慢
4.1、get方法
public synchronized E get(int index) {if (index elementCount)throw new ArrayIndexOutOfBoundsException(index);return elementData(index);
}4.2、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;
}4.3、add方法
public synchronized boolean add(E e) {modCount;ensureCapacityHelper(elementCount 1);elementData[elementCount] e;return true;
}4.4、remove方法
public synchronized boolean removeElement(Object obj) {modCount;int i indexOf(obj);if (i 0) {removeElementAt(i);return true;}return false;
}五、Stack
在 Java 中 Stack 类表示后进先出LIFO的对象堆栈。栈是一种非常常见的数据结构它采用典型的先进后出的操作方式完成的在现实生活中手枪弹夹的子弹就是一个典型的后进先出的结构。
在使用方面主要方法有push 、peek 、pop 。
5.1、push方法
push方法表示向栈中添加元素
public E push(E item) {addElement(item);return item;
}5.2、peek方法
peek方法表示查看栈顶部的对象但不从栈中移除它
public synchronized E peek() {int len size();if (len 0)throw new EmptyStackException();return elementAt(len - 1);
}5.3、pop方法
pop方法表示移除元素并将要移除的元素方法 public synchronized E pop() {E obj;int len size();obj peek();removeElementAt(len - 1);return obj;
}关于 Java 中 Stack 类有很多的质疑声栈更适合用队列结构来实现这使得Stack在设计上不严谨因此官方推荐使用Deque下的类来是实现栈
六、总结 ArrayList(动态数组结构)查询快随意访问或顺序访问增删慢但在末尾插入速度与LinkedList相差无几LinkedList双向链表结构查询慢增删快Vector动态数组结构相比ArrayList都慢被ArrayList替代基本不在使用。优势是线程安全函数都是synchronized如果需要在多线程下使用推荐使用并发容器中的工具类来操作效率高Stack栈结构继承于Vector数据是先进后出基本不在使用如果要实现栈推荐使用Deque下的ArrayDeque效率比Stack高
七、参考
1、JDK1.7JDK1.8 源码
2、CarpenterLee - Java集合分析
3、博客园 - 朽木 - ArrayList、LinkedList、Vector、Stack的比较
八、写到最后
最近无意间获得一份阿里大佬写的技术笔记内容涵盖 Spring、Spring Boot/Cloud、Dubbo、JVM、集合、多线程、JPA、MyBatis、MySQL 等技术知识。需要的小伙伴可以点击如下链接获取资源地址技术资料笔记。 不会有人刷到这里还想白嫖吧点赞对我真的非常重要在线求赞。加个关注我会非常感激
