链表的“头”是什么？

Question

我在 Java 的链表中工作，所以我试图掌握单个链表的概念。

head -> 12 -> 34 -> 56 -> null

head.next 将是 12（也与 node1 相同）。然而，什么是头呢？

更新： 引用和指针有什么区别？

Update2: So if head is 12 and head.next is 34 , then doesn’t mean this following function skips the first node to see如果它为空？

 public void add(Object data, int index)
    // post: inserts the specified element at the specified position in this list.
    {
        Node temp = new Node(data);
        Node current = head;
        // crawl to the requested index or the last element in the list,
        // whichever comes first
        for(int i = 1; i < index && current.getNext() != null; i++)
        {
            current = current.getNext();
        }
        // set the new node's next-node reference to this node's next-node reference
        temp.setNext(current.getNext());
        // now set this node's next-node reference to the new node
        current.setNext(temp);
        listCount++;// increment the number of elements variable
    }

来源： http ://www.mycstutorials.com/articles/data_structures/linkedlists

原文由 Strawberry 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

表头指的是表的第一个节点。它将为存储该节点引用的变量起一个好名字，如果列表为空，我希望它包含空引用

someLinkedList.head
         |
         |
         v
        ______        ______        ______
       |    |n|      |    |n|      |    |n|
       |    |e|      |    |e|      |    |e|
       | 12 |x| -->  | 34 |x| -->  | 56 |x| --> null
       |    |t|      |    |t|      |    |t|
       |____|_|      |____|_|      |____|_|

根据上下文，尾巴可以指代不同的事物。我惯用的术语是说尾部对应于 34 -> 56 -> null 在这个例子中，也就是头部后面的列表。

在其他情况下，它可能是对最后一个节点的引用。在这样的解释中，尾部将指代您示例中的 56 节点。

---

关于您的第一次编辑，这恰好是一个 _完全不同的问题_：

指针是对应于内存地址的值。引用是引用某个对象（或空值）的值。您不能对 Java 引用进行指针运算，但除此之外我会说它们非常相似。

可能会让您感到困惑的是，Java 中的变量 _永远不能包含对象_。对象总是存在于堆上，变量包含原始数据类型，或对堆上对象的引用。

---

关于您的第二次编辑：

在您提供的示例中，add 方法似乎跳过了第一个元素，从某种意义上说确实如此。这是因为实现有一个“虚拟”元素作为头部。查看构造函数中head-variable的初始化：

 head = new Node(null);

我不明白他们为什么决定这样做。对我来说，这看起来很愚蠢。

原文由 aioobe 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

“头”一词有两个完全不相关的含义。最常见的（我相信来自 Lisp）是“列表的第一个元素”。从你的图表来看，这不是你想要的意思。

第二个含义指的是一种处理以下问题的技术：如果将链表表示为仅包含数据的节点，那么当列表为空时，所有对列表的引用（和/或指针，取决于语言）必须为空，因为没有什么可指向的。这会为使用该列表的代码带来很多簿记问题。 列表头 解决了这个问题。它是一个不包含实际数据的列表节点。指向列表的引用或指针始终是指向头节点的指针。列表的第一个元素始终是 head.next 。通常，头部的存在隐藏在实现“带头部的链表”的类中。

根据所支持的操作，列表末尾可能存在类似的簿记问题，特别是对于双向链表。 列表尾 节点简化了簿记。

这些在文献中也被称为“哨兵节点”（包括 关于链表的维基百科文章）。

原文由 Ted Hopp 发布，翻译遵循 CC BY-SA 4.0 许可协议