为什么我们可以将空元素添加到java LinkedList？

Question

我正在使用链表的java.util实现.我想知道为什么它允许我们添加null元素,我们甚至可以遍历它们？

这不是打败链表的点,我们有一个指向下一个元素的元素,如果我们添加了null元素并试图迭代它,链接列表的传统实现就会中断.

Answer 1

查看Java 7源代码,LinkedList实现为一系列节点.

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

每个节点都有对前一个节点和下一个节点的引用,以及一个item.当你插入一个空值到列表中,你将有一个节点null的值item,但next和prev指针非空.

Answer 2

从概念上讲,Java集合包含指向对象的指针,而不是对象本身.当你看到List<String>思考List<Pointer-to-String>.您可以在集合中存储相同字符串地址的多个副本.多个集合可以共享相同的对象指针,您可以将空指针存储在集合中.

您正在考虑一个"常规"实现,它将指针添加到结构本身.Java通过引入包含指向彼此的指针的"标题"对象和指向您放入的对象的指针,将"链接"的细节与代码分开.指向对象的指针可以为null.在内部,LinkedList代码使用"header"对象中的空指针来指定列表的末尾.这个额外的指针有点慢,因为你必须追逐它以获得"有效载荷".但它允许多态(4段向下).

我们通常根本不考虑List实现的细节.我们编码到"列表"界面.List允许我们插入和删除指向对象的指针,并通过索引访问这些指向对象的指针.指针可以为null.

LinkedList快速插入/删除但随机访问速度较慢(它必须追逐"标题"指针).ArrayList可以快速进行随机访问,但插入/删除速度很慢(它必须复制内存).您将代码编写到"List"界面并根据您的使用选择实现.您可以在不更改使用List接口的代码的情况下更改实现.

请注意,在C++标准模板库中,a std::list<std::string>自己创建一个对象集合(不是指向对象的指针),并且不能插入空值.类似Java的集合将是一个std::list<std::string *>,它是一组可以为null的指针.

收集"指针"具有允许多态性的优点.如果我收集对象而不是指针,那么我不能将SuperString放入字符串集合中,因为代码实际上将结构复制到自己的内存中.对于String插槽,SuperString太大了.但是指针的大小都是一样的; 我可以将指向SuperString的指针放入String指针的集合中.