什么是链表的“头”？

data-structures java linked-list

2022-09-02 05:30:47

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

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

head.next将为 12（也与节点 1 相同）。但是，那么什么是头部呢？

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

更新2：因此，如果 is 和 is ，那么是否意味着下面的这个函数跳过第一个节点以查看它是否为 null？head12head.next34

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

答案 1

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

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

根据上下文，尾巴可以指代不同的东西。我用来表示尾部对应于此示例中的术语，即尾部后面的列表。34 -> 56 -> null

在其他上下文中，它可能是对最后一个节点的引用。在这种解释中，尾部将引用示例中的节点。56

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

指针是对应于内存地址的值。引用是引用某个对象（或 null）的值。你不能在Java引用上做指针算术，但除此之外，我会说它们非常相似。

可能让你感到困惑的是，Java中的变量永远不能包含对象。对象始终位于堆上，变量包含基元数据类型或对堆上对象的引用。

关于您的第二次编辑：

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

head = new Node(null);

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

答案 2

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

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

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

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