1

我正在读这本书，在喜欢的列表上有这一章，它从单个链表的实现开始，它是这样的：

创建链接列表：

class Node {
    Node next = null;
    int data;

    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

我的问题：

首先：我无法理解这是如何工作的。理解它真的那么复杂还是我错过了什么？

第二：这个“节点”类可以被认为是一个链表吗？我知道它缺少一些功能，但这是一个独立的链接列表吗？

第三：我用谷歌搜索了 java 中的 LinkedList 实现，并查看了 java api 中的原始类，这是一种完全不同的方法。我应该坚持什么方法？

4

3 回答 3

2

这段代码的问题在于，Node类同时是一个节点和一个链表，比较混乱。除此之外，它应该非常简单。

class Node {
    Node next = null;
    int data;

保存列表中的next下一个节点。如果是最后一个节点，则持有null. 是与此节点关联的data数据，在这种情况下是类型int（顺便说一句，它应该是final）。

public Node(int d) {
    data = d;
}

这是一个简单的constructor方法，它只是将参数复制到它的字段。它代表列表的头部和列表本身。

void appendToTail(int d) {        
    Node n = this;
    while (n.next != null) {
        n = n.next;
    }

这是找到见面的地方。我重新排列了代码以使其更易于理解。该appendToTail方法在列表的和处添加一个节点。在上面的代码中，它遍历列表（从列表this的头部开始）以找到最后一个节点（next字段设置为的那个null）。

    Node end = new Node(d);
    n.next = end;
}

这里创建了一个新节点并将其作为下一个节点添加到当前最后一个节点，从而使其成为列表的最后一个节点。

于 2012-11-27T22:12:55.807 回答
1

接下来是下一条数据的链接。

[数据|next->][数据|next->] .... [ ]

next 就像一个指针，它指向下一个 Node。

appendToTail 创建一个节点和链接。

于 2012-11-27T22:15:04.003 回答
0

一般来说，Node类应该尽可能小。节点的主要功能是；

  • 存储节点的值
  • 存储对下一个 Node实例的引用（或指针）

最简单的 Node 类的写法应该和上面类似；

public class Node<E> {
    protected E value;
    protected Node<E> next;

    public Node(E value) {
        this.value = value;
    }
}

然后，您可以使用此通用Node类编写自定义LinkedList实现。

在您问题中的特定示例代码中，他们已经在Node类中实现了append方法，我认为这不是一个好习惯。相反，追加应该在LinkedList类中，因为该方法不属于Node类的职责。

LinkedList 中的追加方法

在不同来源上实施的方法可能会有所不同。但是 append 方法本身看起来基本相同。在实现之前，您必须了解 append 方法的逻辑。

当链表为空时，head 指向一个空值。Head 是字段，LinkedList 类的成员，用于存储 Linked List 的起始节点。

当您将值附加到链接列表时，首先，head 与第一个附加值一起存储，然后，第二个值将是一个新节点，head 的下一个引用或指针指向该节点。等等。您可以在下面查看状态；

// Initial state of the Linked List
// Head is null

HEAD = NULL

// Append 40 to the Linked List 
// Head stores value 40, but next reference is null.

HEAD(40) --> NULL

// Append 10

HEAD(40) --> (10) --> NULL

// Append 20

HEAD(40) --> (10) --> (20) --> NULL

// Append 50

HEAD(40) --> (10) --> (20) --> (50) --> NULL

// Append 100

HEAD(40) --> (10) --> (20) --> (50) --> (100) --> NULL

很明显，Linked List 总是以 NULL 引用结束，这在遍历列表时非常有用。必须有一个点，一个暗示“这是路的尽头，终止穿越这条路”的标记

您还可以查看我为下面的示例编写的简约简单的链表实现；

LinkedList 的极简实现

public class CustomLinkedList<E> {

    private Node<E> head;

    public CustomLinkedList() {
        this.head = null;
    }

    public void appendToList(E value) {
        if(head == null)
            head = new Node<E>(value);
        else {
            Node<E> temp = head;

            // get the end node into the temp
            while(temp.next != null)
                temp = temp.next;

            // temp is the tail now
            // append new Node next to the tail
            temp.next = new Node<E>(value);
        }
    }

    public void printList() {
        if(head == null)
            return;

        System.out.print("List: ");

        Node<E> temp = head;
        while( temp != null ) {
            System.out.print(temp.value.toString() + " ");
            temp = temp.next;
        }

        System.out.println();
    }

}

演示代码

public class DemoCustomLinkedList {

    public static void main(String[] args) {
        CustomLinkedList<Integer> linkedList = new CustomLinkedList<>();

        linkedList.appendToList(40);
        linkedList.appendToList(10);
        linkedList.appendToList(20);
        linkedList.appendToList(50);
        linkedList.appendToList(100);

        linkedList.printList();
    }

}

演示输出

List: 40 10 20 50 100
于 2016-03-12T22:26:32.253 回答