Что такое LinkedListNode в Java

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,Я не могу найти класс LinkedListNode в Java-документах.

Это может быть очень глупый вопрос, но если кто-то может указать мне правильное направление - это оценит.

EDIT

Спасибо за быстрые и полезные ответы.Я думаю, мой вопрос был не очень ясен.Приведенный выше алгоритм был представлен в качестве решения этого вопроса.Я хотел знать, как реализовать это в 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

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 3

Этот класс, скорее всего, является гипотетическим классом, используемым для этого Связанного списка пример вопроса.

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)