欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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