五、双向链表

双向链表

此前介绍的链表，也叫做单向链表
使用双向链表可以提升链表的综合性能

修改之前的单链表的源码：

双向链表 – findNode(int index)方法

private Node<E> findNode(int index){
    rangeCheck(index);
    Node<E> node;
    if(index < (size >> 1)) {//小于size的一半
        node = first;
        for(int i=0;i < index;i++) {
            node = node.next;
        }
    }else {//大于size的一半
        node = last;
        for(int i = size - 1;i > index;i--) {
            node = node.prev;
        }
    }
    return node;
}

双向链表 – add(int index, E element)

双向链表 – remove(int index)

双向链表 – clear()

public void clear() {
    size = 0;
    first = null;
    last = null;
}

双向链表 –接口测试

public class Main {

    public static void main(String[] args) {
        testList(new ArrayList<>());
        testList(new LinkedList<>());
    }
    
    public static void testList(List<Integer> list) {
        list.add(11);
        list.add(22);
        list.add(33);
        list.add(44);

        list.add(0, 55); // [55, 11, 22, 33, 44]
        list.add(2, 66); // [55, 11, 66, 22, 33, 44]
        list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]

        list.remove(0); // [11, 66, 22, 33, 44, 77]
        list.remove(2); // [11, 66, 33, 44, 77]
        list.remove(list.size() - 1); // [11, 66, 33, 44]

        Asserts.test(list.indexOf(44) == 3);
        Asserts.test(list.indexOf(22) == List.ELEMENT_NOT_FOUND);
        Asserts.test(list.contains(33));
        Asserts.test(list.get(0) == 11);
        Asserts.test(list.get(1) == 66);
        Asserts.test(list.get(list.size() - 1) == 44);
        
        System.out.println(list);
    }
}

public class Asserts {
    public static void test(boolean value) {
        try {
            if (!value) throw new Exception("测试未通过");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

运行结果：

为了让链表的打印好看一些，改造一下链表的toString方法

Node的类里也增加toString方法

此时打印效果如下：

双向链表 vs 单向链表

粗略对比一下删除的操作数量

1. 单向链表：，除以n平均一下是
2. 双向链表：，除以n平均一下是
3. 操作数量缩减了近一半

：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容解决）
：开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费

有了双向链表，单向链表是否就没有任何用处了？

• 并非如此，在哈希表的设计中就用到了单链表
• 至于原因，在哈希表章节中会讲到

代码链接