12

This may be a dumb question as I am not majoring in the computer. I am reading Cracking the coding interview and it has the following codes.

But Java (in eclipse) cannot recognize LinkedListNode but it recognize LinkedList. Am I supposed to create a class name LinkedListNode, a double linked list? Shouldn't java already have that in import java.util.* as it does for LinkedList?

import java.util.*;
public static void deleteDups2(LinkedListNode head) {
    if (head == null) return;
    LinkedListNode previous = head;
    LinkedListNode current = previous.next;
    while (current != null) {
        LinkedListNode runner = head;
        while (runner != current) { // Check for earlier dups
            if (runner.data == current.data) {
                LinkedListNode tmp = current.next; // remove current
                previous.next = tmp; 
                current = tmp; // update current to next node
                break; // all other dups have already been removed
            }
            runner = runner.next;
        }
        if (runner == current) { // current not updated - update now
            previous = current;
            current = current.next;
        }
    }
}
4
  • 3
    Maybe the author has designed LinkedListNode in the previous chapters. Look carefully. Jan 4, 2017 at 5:18
  • As suggested by the other comment, author may have mentioned it in previous chapter. If not, you may simply treat it as a typical Linked List Node implementation (for which each node contains the data, and the next pointer) Jan 4, 2017 at 6:20
  • Yeah I am going over the same course in C++ and they are accessing a member variable called next. Not even providing a definition for what the LinkedListNode class actually is. I cant find a definition of it online. Seems like they slapped this together from one language and translated to another assuming the user would know what it is. Had this been an actual interview question I would just have just incremented the pointer and told the interviewer that its an unknown class.
    – Mi Po
    Aug 15, 2020 at 17:22
  • You may want to check the source code of the LinkedList.java. In there there is a private class Node<E>. You may want to create a class named LinkedListNode with the same content as Node class. Aug 20, 2022 at 18:49

3 Answers 3

21

LinkedListNode isn't a class included with Java. The "Code Library" section (section XI) in the back of the book contains the implementation of LinkedListNode.

I would include the code here, but the copyright notice in the book doesn't allow for that.

1
1

Using the existing LinkedList in java it is quite straight forward to implement this solution, maybe author wants to empathies more on the concept of LinkedList so they have their own implementation as LinkedListNode.

However, this sample code below uses Java's Built in LinkedList to remove the duplicates:

package com.linkedlist;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
public class RemDupUnsortedLL
{
    public static void deleteDups(LinkedList node)
    {
        HashSet<Integer> set = new HashSet<Integer>();
        LinkedList previous=new LinkedList();
        int i=0;
        while(node.getLast() !=null && i < node.size())
        {
            int elem = (int) node.get(i);
            if(! set.contains(elem)){
                set.add((Integer) node.get(i));
                previous.add(node.get(i));
            }
            i++;
        }
        System.out.print("\n  After function call ");
        for(int j=0;j<previous.size();j++) {

            System.out.print(" " +previous.get(j));

        }
    }

    public static void main(String[] args) {

        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3); list.add(4); list.add(4);
        list.add(4); list.add(5); list.add(6);
        System.out.print("Before function call ");
       for(int i=0;i<8;i++) {

            System.out.print(" " +list.get(i));

        }
        deleteDups(list);

    }

}
1
  • The second part of the question emphasizes using constant space, which seems difficult to use with just LinkedList
    – Jolt151
    Feb 25, 2022 at 2:11
-3

LinkedListNode is not one of the standard Java API types, as can be seen by searching through https://docs.oracle.com/javase/8/docs/api/. That means that importing from java.util will not help, since that package does not contain that type. What package does contain that type? Does your source for that source tell you?

There are three major kinds of Java package, distinguished by the reversed-order domain names or domain-like names of the packages:

  • java.** and javax.**. These packages come with the language.
  • org.**. These are "non-profit" packages from places like apache.org
  • com.**. These are "commercial" packages, as from Oracle or yourself.

java.util.** is of the first kind, packages that come with the language. LinkedListNode isn't there. That means it comes from one of the other two, perhaps org.apache.**, packages that are sourced from http://apache.org. One way to find out is to do a google search, say on LinkedListNode. Several candidates appear.

Perhaps you misread the type and it's LinkedList.Node, a private type within LinkedList. http://www.docjar.com/docs/api/java/util/LinkedList$Node.html

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.