LinkedList与LinkedHashMap的区别
程序员文章站
2022-04-15 19:03:49
LinkedList与LinkedHashMap的区别LinkedListLinkedList 底层数据结构是一个双向链表,链表的每个节点都可以向前或者向后传递。具有一下概念:链表的节点称为Node,有属性next,prev。分别指向后一个节点和前一个节点。first表示头节点,前一个节点为nulllast表示尾节点,后一个节点为nullLinkedList源码 public class LinkedList extends AbstractSequentialL...
LinkedList与LinkedHashMap的区别
LinkedList
LinkedList 底层数据结构是一个双向链表,链表的每个节点都可以向前或者向后传递。具有一下概念:
- 链表的节点称为Node,有属性next,prev。分别指向后一个节点和前一个节点。
- first表示头节点,前一个节点为null
- last表示尾节点,后一个节点为null
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;
}
}
LinkedHashMap
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
LinkedHashMap 继承了 HashMap 的,拥有 HashMap 的所有特性。并新增两个特性:
- 按照插入顺序进行访问。
- 按照访问顺序把经常访问的元素追加到队尾,就可以把很久都没有访问的key删除。
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
推荐阅读
-
display:none;与visibility:hidden;的区别_html/css_WEB-ITnose
-
jQuery中serializeArray()与serialize()的区别实例分析_jquery
-
PHP中isset与array_key_exists的区别实例分析_PHP教程
-
整理的比较全的event对像在ie与firefox浏览器中的区别_javascript技巧
-
php4与php5的区别小结(配置异同)
-
sql server跟my sql 命令(语句)的区别,sql server与mysql的比
-
PHP中isset、empty的用法与区别示例详解
-
Jquery AJAX POST与GET之间的区别
-
php字符串中的双引号与单引号区别_PHP教程
-
nodejs中的__filename与__dirname具体示例及区别讲解