单向链表和双向链表的区别的意义 - Java篇

夹胡碰

发布于 2020-12-18 14:33:01

1.2K0

发布于 2020-12-18 14:33:01

文章被收录于专栏：程序猿~

众所周知，链表是常用的数据结构，在Java中有很多基于链表的容器实现类，例如HashMap、LinkedList。但是这些链表有的是单向链表，有的是双向链表，那么他俩有什么不同呢？(以下源码均属于jdk1.8.0_101)

双向链表有前后两个节点指针，可以回溯指针，方便节点删除，移动，在做删除操作时只需要将索引节点前后两个节点连接即可，但是相比单向链表会耗费额外资源。 单向链表只有后一节点指针，在节点删除，移动的时候，需要暂存前一节点，删除的时候将前一节点和后一节点连接，因为比双向链表少维护一个前节点，只在删除的时候暂存，所以比单向链表节省资源，但是增加了操作的复杂性。

单向链表

image.png

双向链表

image.png

源码分析

1. HashMap - 单向链表

暂存前一节点，前后节点连接

Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    ...
}

removeNode

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e; // 暂存前一节点
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next; // 前一节点和后一节点连接
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

2. 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;
    }
}

unlink

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> 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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法