Java中的LinkedListNode是什么

Question

请原谅我的无知，但我正开始准备我的第一次技术面试，并遇到了有关链表主题的问题和答案

问题：实现一种算法来删除单个链表中间的节点，只允许访问该节点

public static boolean deleteNode(LinkedListNode n) {
if (n == null || n.next == null) {
   return false; // Failure
}
LinkedListNode next = n.next;
n.data = next.data;
n.next = next.next;
return true;
}

我想开始使用此代码（进行更改编译测试），但我不确定如何开始在 Java 中执行此操作。我在 Java 文档中找不到 LinkedListNode 类。

这可能是一个非常愚蠢的问题，但如果有人能指出我正确的方向 - 我会很感激。

编辑

感谢您的快速而有用的回复。我想我的问题不是很清楚。提供上述算法作为该问题的解决方案。我想知道如何在 Java 中实现它，以便我可以使用代码。

谢谢

Answer 1

仅当列表中有尾节点时，代码才能正常工作。

该算法按照以下逻辑工作：

When referring to the node to be deleted, call it "curr"
When referring to the node before "curr", call it "prev"
When referring to the node after "curr", call it "next"

To effectively delete our node, "prev".next should point to "next"
It currently points to "curr"

Our problem is that we have no reference to "prev"

We know "prev".next points to "curr"

Since we cannot change the fact that "prev".next points to "curr",
we must have "curr" gobble up "next"

We make "curr"s data be "next"s data
We make "curr"s next be "next"s next

The reason this only works if there's a tail guard 
is so we can make "next" be the "tail" node of the 
list. (Its data is null and it's next is null.) Otherwise, 
"prev".next would still be pointing to something.

这是一个使用 LinkedListNode 的类。我应该指出，如果您正在申请程序员职位，您应该能够基本上凭记忆完成此操作。 :-)

class LinkedList<E> {

    static class LinkedListNode<E> {
        E data;
        LinkedListNode<E> next;
    }

    /**
     * Not exactly the best object orientation, but we'll manage
     */
    static <E> E deleteNode(LinkedListNode<E> node) {
        if(node == null || node.next == null) return null;

        E retval = node.data;
        LinkedListNode<E> next = node.next;
        node.data = next.data;
        node.next = next.next;
        return retval;
    }

    private LinkedListNode<E> head;
    private LinkedListNode<E> tail;

    public LinkedList() {
        this.head = new LinkedListNode<E>();
        this.tail = new LinkedListNode<E>();
        head.next = tail;
    }

    public void addLast(E e) {
        LinkedListNode<E> node = new LinkedListNode<E>(); // e and next are null
        tail.data = e;
        tail.next = node;
        tail = node;
    }

    public void addFirst(E e) {
        LinkedListNode<E> node = new LinkedListNode<E>(); // e and next are null;
        node.next = head.next;
        node.data = e;
        head.next = node;
    }

    public E deleteFirst() {
        LinkedListNode<E> first = head.next;
        head.next = first.next;
        return first.data;
    }

    public E deleteLast() {
        // cannot do without iteration of the list! :-(
        throw new UnsupportedOperationException();
    }

    public LinkedListNode<E> findFirst(E e) {
        LinkedListNode<E> curr = head.next;
        while(curr != null) {
            if(curr.data != null && curr.data.equals(e)) return curr;
            curr = curr.next;
        }
        return null;
    }

    public void print() {
        LinkedListNode<E> curr = head.next;
        while(curr.next != null) {
            System.out.println(curr.data);
            curr = curr.next;
        }
    }


    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<String>();
        list.addLast("Apple");
        list.addLast("Bear");
        list.addLast("Chair");
        list.addLast("Dirt");

        //list.print();

        LinkedListNode<String> bear = list.findFirst("Bear");
        deleteNode(bear);

        list.print();
    }

}

Answer 2

该类很可能是用于此链接列表示例问题的假设类。

Answer 3

LinkedListNode 是一个您将定义来保存数据的类。为了让你上面的例子工作 - 我快速编写了这段代码（只是为了让你理解这个简单的概念），其中我创建了 3 个节点（彼此链接），然后删除中间的一个调用 deleteNode 您在问题中指定的方法。

该代码非常不言自明。让我知道这是否有帮助。
祝你好运

class LinkedListNode
{
    public Object data;
    public LinkedListNode next;

    public LinkedListNode(Object data) {
    this.data = data;
    }
}

class DeleteNodeLinkedList
{
    public static void main(String[] args) 
    {
        LinkedListNode node_1 = new LinkedListNode("first");        
        LinkedListNode node_2 = new LinkedListNode("second");
        node_1.next = node_2;
        LinkedListNode node_3 = new LinkedListNode("third");
        node_2.next = node_3;

        System.out.println("*** Print contents of linked list");
        LinkedListNode  current = node_1;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }

        System.out.println("*** Now delete second node");
        deleteNode(node_2);

        System.out.println("*** Print after deleting second node");
        current = node_1;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    public static boolean deleteNode(LinkedListNode n) 
    {
        if (n == null || n.next == null) {
            return false; // Failure
        }
        LinkedListNode next = n.next;
        n.data = next.data;
        n.next = next.next;
        return true;
    }
}

Answer 4

这个问题的重要细节与数据结构有关，java只是在这种情况下用于实现的语言。
您应该阅读有关链接列表的维基百科文章，对于这个问题，请注意您的解决方案不'不会产生任何悬空引用或孤立节点。
对这两个粗体术语进行一些搜索，并确保您理解它们

Answer 5

你的问题有点令人困惑。无论您想要一个删除单链表中节点的逻辑，还是想要学习和使用 java LinkedlistNode。

如果您处于第二位，以下链接将为您提供帮助

LinkedListNodee

或者如果你想要逻辑

let P the pointer to the current node
P->data = P->next->data
Q=P->next
P->next=Q->next
delete(Q)