LinkedList 底层数据结构是一个双向链表,链表的每个节点都可以向前或者向后传递。具有一下概念:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
/**
* Constructs an empty list.
*/
public LinkedList() {
}
........
}
Node的结构:
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;
}
}
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
LinkedHashMap 继承了 HashMap 的,拥有 HashMap 的所有特性。并新增两个特性:
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder) //true 按照访问顺序,会把经常访问的 key 放到队尾
afterNodeAccess(e);
return e.value;
}
先删除节点在追加到队尾:
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
put和get操作已存在的Entry时,都会把Entry移动到双向链表的表尾。
LinkedHashMap就是HashMap+LinkedList,可以看成HashMap的基础上,新增了双向链表来维持顺序。
本文地址:https://blog.csdn.net/Zhangxg0206/article/details/107875709
如对本文有疑问, 点击进行留言回复!!
Modem2G/3G/4G/5G:通信领域常见名词缩写释义(VoLTE,CSFB,CA,RAT...)
ROG游戏手机3对比拯救者游戏手机 ROG游戏手机3与拯救者游戏手机对比介绍
Unity Cloud Content Delivery(Unity云端资源分发#02)
F:大疆M300PSDKv2.1.0通过树莓派4B向pilot传输图片与视频。(只运行示例程序)
网友评论