什么是Java中的LinkedListNode [英] What is LinkedListNode in Java

问题描述

请原谅我的无知，但我开始准备我的第一次技术面试，并在主题链接列表中遇到了这个问题和答案

Excuse my ignorance but I am beginning to prepare for my first technical interview and came across this question and answer on the topic linkedlist

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

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类。

I want to start playing with this code (making changes compile test) but I'm not sure how to start doing this in Java. I cannot find the LinkedListNode class in Java docs.

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

This might be a very silly question but if someone can point me in the right direction - will appreciate it.

编辑

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

Thanks for the quick and useful responses. I guess my question was not very clear. The algorithm above was provided as a solution to that question. I wanted to know how to implement that in Java so I can play around with the code.

谢谢

推荐答案

如果列表中有尾节点，代码将只能正常工作。

The code will only work properly if there's a tail node on the list.

该算法使用以下逻辑

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的类。我应该注意，如果你申请一个程序员职位，你应该能够从记忆中做到这一点。 ： - ）

Here's a class that uses LinkedListNode. I should note that if you're applying for a position as a programmer, you should be able to do this basically from memory. :-)

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();
    }

}

这篇关于什么是Java中的LinkedListNode的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！