最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

环球新资讯:【collection】4.java容器之LinkedList,Stack,CopyOnWriteArrayList

来源:博客园

LinkedList

节点数据结构

/** * 泛型结构 * @param  node */private static class Node {E item;// 双向链表,向前和向后Node next;Node prev;Node(Node prev, E element, Node next) {this.item = element;this.next = next;this.prev = prev;}}

add

结论:新节点是插入到原来index的前面,原来index以及以后的节点,整体后移一位

/** * Returns the (non-null) Node at the specified element index. * 这里索引用了二分的思想,但是不是二分的算法 * 首先区分index是否小于一般,如果是,那么从前往后找 * 如果大于一般,那么从后往前找 */Node node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) {// 从first往后Node x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {// 从last往前Node x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}/** * 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++;}

reomove,removeFirst,remove(index)

remove默认移除首节点,于removefirst作用相同

/** * 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 GCfirst = next;if (next == null)last = null;else {// 更新完first之后,这里只需要把next.prev对象设置为null即可next.prev = 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;// 前置节点为空,那么直接把first移动到nextif (prev == null) {first = next;} else {// 把前面节点的后置设置为下一个,跳过当前节点prev.next = next;x.prev = null;}// 如果next本来是空的,那么把last指针前移if (next == null) {last = prev;} else {// 不为空,那么把后面节点的前置指针跳过当前,设置前面一个节点next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}

remove(index)和 remove(Object)类似


【资料图】

但是remove(object)的意思是判断空和非空,因为空的无法进行equals比较,循环查找

另外remove(index)也是先根据node方法定位关联节点

get,indexof查找

get方法也是用node(index)定位,indexof方法:判断空和非空,因为空的无法进行equals比较,循环查找

参考

https://pdai.tech/md/java/collection/java-collection-LinkedList.html#queue-方法

Stack

栈的实现主要依赖的是vector

这里主要是push和pop操作

扩容参考arraylist

push就是类似add,但是这里的操作都加了synchronized关键字,所以stack是线程安全的

CopyOnWriteArrayList

add操作

public boolean add(E e) {// 加锁final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;// 先直接复制一个新的数组出来,并且直接把长度+1Object[] newElements = Arrays.copyOf(elements, len + 1);// 然后设置最后一个位置的节点newElements[len] = e;setArray(newElements);return true;} finally {lock.unlock();}}

扩容

这个结构的扩容方式很简单暴力

直接复制出来一份满足要求大小的数组

newElements = Arrays.copyOf(elements, len + 1);

get

没有加锁

private E get(Object[] a, int index) {    return (E) a[index];}

总结:

数据一致性问题:CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性。

这句话的意思是在循环操作的过程中,这个get结果是不可知的,只能保证在set的时候没问题,然后所有数据add完毕之后的结果符合预期

内存占用问题:因为CopyOnWrite的写时复制机制,所以在进行写操作的时候,内存里会同时驻扎两个对象的内存,旧的对象和新写入的对象(注意:在复制的时候只是复制容器里的引用,只是在写的时候会创建新对象添加到新容器里,而旧容器的对象还在使用,所以有两份对象内存)

关键词: 数据结构 数据一致性 循环操作