链表的"头"是什么？

Question

我正在使用Java链接列表,所以我试图掌握单个链表的概念.

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

head.next将是12(也与node1相同).然而,什么是头呢？

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

Update2:所以如果head是12和head.next是34,那么这并不意味着这个跟随函数会跳过第一个节点,看它是否为空？

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

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示例中的节点.

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

指针是与存储器地址对应的值.引用是指引用某个对象(或null)的值.你不能对Java引用做指针算术,但除此之外我会说它们非常相似.

令您困惑的是,Java中的变量永远不能包含对象.对象始终存在于堆上,变量包含原始数据类型或对堆上对象的引用.

关于你的第二次编辑:

在您提供的示例中,看起来add方法会跳过第一个元素,从某种意义上说它会跳过第一个元素.这是因为实现具有"虚拟"元素作为头部.查看构造函数中head-variable的初始化:

head = new Node(null);

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

Answer 2

术语"头部"有两个完全不相关的含义.最常见的(来自Lisp,我相信)是"列表的第一个元素."从你的图表来看,这不是你想到的意思.

第二个含义是指处理以下问题的技术:如果您将链表表示为仅包含数据的节点,那么当列表为空时,所有引用(和/或指针,取决于语言)到列表必须为null,因为没有什么可指的.这为使用列表的代码创建了大量的簿记问题.一个表头解决了这个问题.它是一个不包含实际数据的列表节点.指向列表的引用或指针始终是指向头节点的指针.列表的第一个元素始终是head.next.通常头部的存在隐藏在实现"带头的链表"的类中.

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

这些在文献中也被称为"哨兵节点"(包括链接列表上的维基百科文章).

Answer 3

是的，它只是一个指向第一个节点的指针

Answer 4

在做其他事情之前应该注意的是，head 不是一个单独的节点，而只是对第一个节点的引用。它通过存储指向第一个节点的指针来保留整个列表。

另一个值得注意的区别是 head 是一个普通的本地指针变量，存储在堆栈中，而列表节点存储在堆中。 因此，在大多数行话中，Head 只是一个本地指针，它保留对链表第一个元素的引用，并且通常使用 NULL 进行初始化，以区分空链表。