Java 使用带有 LinkedList 的节点

Java Using Nodes with LinkedList

提问by jeffkempf

I've been working through some standard coding interview questions from a book I recently bought, and I came across the following question and answer:

我一直在研究我最近购买的一本书中的一些标准编码面试问题，我遇到了以下问题和答案：

Implement an algorithm to find the nth to last element in a linked list.

实现一个算法来查找链表中倒数第 n 个元素。

Here's the provided answer:

这是提供的答案：

public static LinkedListNode findNtoLast(LinkedListNode head, int n) { //changing LinkedListNode to ListNode<String>
        if(head == null || n < 1) {
            return null;
        }
        LinkedListNode p1 = head;
        LinkedListNode p2 = head;
        for(int j = 0; j < n-1; ++j) {
            if(p2 == null) {
                return null;
            }
            p2 = p2.next;
        }
        if(p2 == null) {
            return null;
        }
        while(p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

I understand the algorithm, how it works, and why the book lists this as its answer, but I'm confused about how to access the LinkedListNodes to send as an argument to the method. I know that I'd have to create a LinkedListNode class (since Java doesn't already have one), but I can't seem to figure out how to do that. It's frustrating because I feel like I should know how to do this. Here's something that I've been working on. I'd greatly appreciate any clarification. You can expand/comment on my code or offer your own alternatives. Thanks.

我了解算法，它是如何工作的，以及为什么这本书将其列为答案，但我对如何访问 LinkedListNodes 以作为方法的参数发送感到困惑。我知道我必须创建一个 LinkedListNode 类（因为 Java 还没有一个），但我似乎无法弄清楚如何做到这一点。这很令人沮丧，因为我觉得我应该知道如何做到这一点。这是我一直在做的事情。我将不胜感激任何澄清。您可以扩展/评论我的代码或提供您自己的替代方案。谢谢。

class ListNode<E> {
    ListNode<E> next;
    E data;

    public ListNode(E value) {
        data = value;
        next = null;
    }

    public ListNode(E value, ListNode<E> n) {
        data = value;
        next = n;
    }

    public void setNext(ListNode<E> n) {
        next = n;
    }
}

public class MyLinkedList<E> extends LinkedList {
    LinkedList<ListNode<E>> list;
    ListNode<E> head;
    ListNode<E> tail;
    ListNode<E> current;
    ListNode<E> prev;

    public MyLinkedList() {
        list = null;
        head = null;
        tail = null;
        current = null;
        prev = null;
    }

    public MyLinkedList(LinkedList<E> paramList) {
        list = (LinkedList<ListNode<E>>) paramList; //or maybe create a loop assigning each ListNode a value and next ptr
        head = list.getFirst();
        tail = list.getLast(); //will need to update tail every time add new node
        current = null;
        prev = null;
    }

    public void addNode(E value) {
        super.add(value);
        //ListNode<E> temp = tail;
        current = new ListNode<E>(value);
        tail.setNext(current);
        tail = current;
    }

    public LinkedList<ListNode<E>> getList() {
        return list;
    }

    public ListNode<E> getHead() {
        return head;
    }

    public ListNode<E> getTail() {
        return tail;
    }

    public ListNode<E> getCurrent() {
        return current;
    }

    public ListNode<E> getPrev() {
        return prev;
    }


}

How can the LinkedListNode head from a LinkedList?

LinkedListNode 如何从 LinkedList 开始？

Update: I think part of my confusion comes from what to put in the main method. Do I need to create a LinkedList of ListNode? If I do that, how would I connect the ListNodes to each other? How would I connect them without using a LinkedList collection object? If someone could show me how they would code the main method, I think that would put things into enough perspective for me to solve my issues. Here's my latest attempt at the main method:

更新：我认为我的部分困惑来自在主要方法中放入什么。我需要创建一个 ListNode 的 LinkedList 吗？如果我这样做，我将如何将 ListNode 相互连接？如何在不使用 LinkedList 集合对象的情况下连接它们？如果有人能告诉我他们将如何编写 main 方法，我认为这会让我有足够的视角来解决我的问题。这是我对主要方法的最新尝试：

public static void main(String args[]) {
        LinkedList<ListNode<String>> list = new LinkedList<ListNode<String>>();
        //MyLinkedList<ListNode<String>> list = new MyLinkedList(linkedList);
        list.add(new ListNode<String>("Jeff"));
        list.add(new ListNode<String>("Brian"));
        list.add(new ListNode<String>("Negin"));
        list.add(new ListNode<String>("Alex"));
        list.add(new ListNode<String>("Alaina"));
        int n = 3;
        //ListIterator<String> itr1 = list.listIterator();
        //ListIterator<String> itr2 = list.listIterator();
        LinkedListNode<String> head = new LinkedListNode(list.getFirst(), null);
        //String result = findNtoLast(itr1, itr2, n);
        //System.out.println("The " + n + "th to the last value: " + result);
        //LinkedListNode<String> nth = findNtoLast(list.getFirst(), n);
        ListNode<String> nth = findNtoLast(list.getFirst(), n);
        System.out.println("The " + n + "th to the last value: " + nth);
    }

In an attempt to connect the nodes without using a custom linked list class, I have edited my ListNode class to the following:

为了在不使用自定义链表类的情况下连接节点，我将 ListNode 类编辑为以下内容：

class ListNode<E> {
    ListNode<E> next;
    ListNode<E> prev; //only used for linking nodes in singly linked list
    ListNode<E> current; //also only used for linking nodes in singly linked list
    E data;
    private static int size = 0;

    public ListNode() {
        data = null;
        next = null;
        current = null;
        if(size > 0) { //changed from prev != null because no code to make prev not null
            prev.setNext(this);
        }
        size++;
    }
    public ListNode(E value) {
        data = value;
        next = null;
        current = this;
        System.out.println("current is " + current);
        if(size > 0) {
            prev.setNext(current);//this line causing npe
        }
        else
        {
            prev = current;
            System.out.println("prev now set to " + prev);
        }
        size++;
        System.out.println("after constructor, size is " + size);
    }

    public ListNode(E value, ListNode<E> n) {
        data = value;
        next = n;
        current = this;
        if(size > 0) {
            prev.setNext(this);
        }
        size++;
    }

    public void setNext(ListNode<E> n) {
        next = n;
    }
}

As is right now, the program will run until it reaches prev.setNext(current); in the single argument constructor for ListNode. Neither current nor prev are null at the time this line is reached. Any advice would be greatly appreciated. Thanks.

就像现在一样，程序会一直运行到 prev.setNext(current); 在 ListNode 的单参数构造函数中。到达此行时 current 和 prev 都不为空。任何建议将不胜感激。谢谢。

采纳答案by sprinter

You don't actually need a separate LinkedList class; the ListNode class isa linked list. Or, to state it differently, a reference to the head of the list is a reference to the list.

您实际上并不需要单独的 LinkedList 类；ListNode 类是一个链表。或者，换一种说法，对列表头部的引用就是对列表的引用。

The use of head, tail, current, prev in the sample code you posted has come from a double-linked list which is a data type that has links in both directions. This is more efficient for certain types of applications (such as finding the nth last item).

您发布的示例代码中使用的 head、tail、current、prev 来自双链表，这是一种双向链接的数据类型。这对于某些类型的应用程序（例如查找倒数第 n 个项目）更有效。

So I would recommend renaming your ListNode class to LinkedList and renaming nextto tail.

所以我建议将 ListNode 类重命名next为LinkedList 并重命名为tail.

To add a new item to the list you need a method that creates a new list with the new item at it's head. Here is an example:

要将新项目添加到列表中，您需要一种方法来创建一个以新项目开头的新列表。下面是一个例子：

class LinkedList<E> {
    ...

    private LinkedList(E value, LinkedList<E> tail) {
        this.data = value;
        this.tail = tail;
    }

    public LinkedList<E> prependItem(E item) {
        return new LinkedList(item, this);
    }
}

Then to add a new item ito listyou use list = list.prependItem(i);

然后添加一个新项目i给list你使用list = list.prependItem(i);

If for some reason you need to always add the items to the end, then:

如果由于某种原因您需要始终将项目添加到末尾，则：

private LinkedList(E value) {
    this.data = value;
    this.tail = null;
}

public void appendItem(E item) {
    LinkedList<E> list = this;
    while (list.tail != null)
        list = list.tail;
    list.tail = new LinkedList<>(item);
}

However this is obviously pretty inefficient for long lists. If you need to do this then either use a different data structure or just reverse the list when you have finished adding to it.

然而，这对于长列表来说显然效率很低。如果您需要这样做，那么要么使用不同的数据结构，要么在完成添加后反转列表。

Incidentally, an interesting side effect of this is that a reference to any item in the list is a reference to a linked list. This makes recursion very easy. For example, here's a recursive solution for finding the length of a list:

顺便说一句，这样做的一个有趣的副作用是对列表中任何项目的引用都是对链接列表的引用。这使得递归非常容易。例如，这是用于查找列表长度的递归解决方案：

public int getLength(LinkedList list) {
    if (list == null) {
        return 0;
    } else {
        return 1 + getLength(list.getTail());
    }
}

And using this a simple (but very inefficient!) solution to the problem you provided - I've renamed the method to make its function more obvious:

并使用这个简单（但非常低效！）解决您提供的问题的方法 - 我已重命名该方法以使其功能更加明显：

public LinkedList getTailOfListOfLengthN(LinkedList list, int n) {
    int length = getLength(list);
    if (length < n) {
        return null;
    } else if (length == n) {
        return list;
    } else {
        return getTailOfLengthN(list.getTail(), n);
    }
}

And to reverse the list:

并反转列表：

public LinkedList<E> reverse() {
    if (tail == null) {
        return this;
    } else {
        LinkedList<E> list = reverse(tail);
        tail.tail = this;
        tail = null;
        return list;
    }
}

As I hope you can see this makes the methods a lot more elegant than separating the node list classes.

我希望你能看到这使得这些方法比分离节点列表类更优雅。

回答by Nicola Ferraro

Actually you have created a linked list with you class ListNode.

实际上，您已经使用 ListNode 类创建了一个链表。

A linked list is made of a node and a reference to another linked list (see the recursion?).

链表由一个节点和对另一个链表的引用组成（参见递归？）。