链表的“头”是什么？

Question

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

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

head.next

将为 12（也与节点 1 相同）。然而，什么是头呢？

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

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_structs/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 = new Node(null);

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

Answer 2

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

第二个含义是指处理以下问题的技术：如果将链表表示为仅包含数据的节点，那么当链表为空时，所有对链表的引用（和/或指针，取决于语言） list 必须为 null，因为没有任何内容可指向。这会给使用列表的代码带来很多簿记问题。 列表头解决了这个问题。它是一个不包含实际数据的列表节点。指向列表的引用或指针始终是指向头节点的指针。列表的第一个元素始终是

head.next

。通常，头的存在隐藏在实现“带头链表”的类中。

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

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

Answer 3

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

Answer 4

Before Anything else 需要注意的是，head 并不是一个单独的节点，而只是对第一个节点的引用。它通过存储指向第一个节点的指针来保留整个列表。

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

Answer 5

我理解的是简单的区别。使用

head

指针

list

创建由

LinkedList

类本身管理，但是如果没有

head

指针 - 客户端代码需要首先跟踪，然后添加

nodes

的其余部分

但是，无论有或没有

head

指针 - 都会创建功能性

LinkedList

没有

Head

指针的现代 go-to 风格链表（来自 Leetcode）

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

创建

LinkedList

ListNode listNode = new ListNode(4, new ListNode());
listNode.next = new ListNode(1, listNode1);

现在使用

head

指针：

public class SingleList {
    Node head;

    static class Node{
        int data;
        Node next;
        Node(int d){data = d;}
    }

    public void insertNode(int n){
        Node new_node = new Node(n);
        if(head == null){
            head = new_node;
        } else{
            Node cur_node = head;
            while(cur_node.next !=null){
                cur_node = cur_node.next;
            }
            cur_node.next = new_node;
        }
    }
}

创建

Linkedlist

SingleList singleList1 = new SingleList(6);
singleList1.insertNode(3);

参见 - 在客户端程序中创建链表 - 对于上述不同的

Linkedlist

实现。