What is LinkedListNode in Java

Question

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

Question: Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node

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

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.

EDIT

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.

thanks

Answer 1

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

The algorithm works with the following logic

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.

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

}

Answer 2

This class is most likely a hypothetical class used for this Linked List example question.

Answer 3

LinkedListNode is a class that you will define to hold data. To get your above example to work - I've quickly written this code (just to make you understand the simple concept) in which I am creating 3 nodes (which are linked to each other) and then deleting the middle one calling the deleteNode method that you have specified in your question.

The code is pretty self explanatory. Let me know if this helps. Good Luck

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

The important details in this question pertain to data structures, java is just the language that is being used to implement in this case.
You should read the wikipedia article about linked lists, and for this question be careful that your solution doesn't produce any dangling references or orphan nodes.
Do some searches on the two terms in bold, and make sure that you understand them

Answer 5

Your question is bit confusing. whether you want a logic to remove a node in a singly linkedlist or you want to learn and use java LinkedlistNode.

if you are in second the following link will help you

LinkedListNodee

or if you want the logic

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