Removing duplicates from unsorted LinkedList

Question

Removing Duplicates:

/**
 * Remove duplicates without using a buffer.
 * 
 * @param head
 */
public static void removeUnsortedDuplicatesWithoutBuffer(final LinkedListNode head) {

    //if the linked list is empty
    if(head == null) {
        throw new RuntimeException("linked list is empty");
        //return;
    }       
    LinkedListNode current = head;
    LinkedListNode runner = null ;
    LinkedListNode previous = null ;
    boolean flag = false ;

    while(current != null) {        
        runner = head;
        while(runner != current) {
            if(current.getData() != runner.getData()) {
                runner = runner.getNext();
                flag = false;
            } else {
                previous.setNext(current.getNext());
                current = previous.getNext();
                flag = true;
                break;
            }
        }       
        if(!flag) {
            previous = current;
            current = current.getNext();
        }       
    }
}

LinkedListNode:

class LinkedListNode {
    private int data;
    private LinkedListNode next ;

    public LinkedListNode(final int data) {
        this.data = data;
        this.next = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public LinkedListNode getNext() {
        return next;
    }
    public void setNext(LinkedListNode next) {
        this.next = next;
    }

    public void appendAtTail(final int data) {  
        LinkedListNode newNode = new LinkedListNode(data);
        LinkedListNode current = this;
        while(current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
}

Test Case:

@Test
public void testRemoveDuplicatesFromUnsortedSortedLL() {                
    LinkedListNode head = new LinkedListNode(30);
    head.appendAtTail(20);
    head.appendAtTail(20);
    head.appendAtTail(30);
    head.appendAtTail(10);
    head.appendAtTail(50);
    head.appendAtTail(10);
    head.appendAtTail(10);
    head.appendAtTail(20);
    head.appendAtTail(50);
    head.appendAtTail(50);
    head.appendAtTail(100);
    RemoveDuplicates.removeUnsortedDuplicatesWithoutBuffer(head);
}

I wrote this code recently to remove duplicates from linked list without using buffer and was trying to analyze its complexity : Time taken for traversing is O(n) For each operation we need to move runner node n times to remove duplicates Total Complexity : O(n²). Is this correct ?? I guess not because this is no better than using two for loops and comparing each element with the rest of the elements in the LinkedList . What am I doing wrong here?

Answer 1

Yes, this looks \$O(n^2)\$: when all elements are unique, the program will compare all elements with all other elements.

A better solution will be to use a Set to keep track of the already seen items. You will still have to iterate over all items, but you won't have to compare to all other elements, but simply do a lookup in the Set, which in case of a HashSet will be \$O(1)\$ complexity. Of course, when all elements are unique, then this method will use twice as much memory as your original. That's a trade-off you'll have to consider.

Unfortunately you didn't provide the implementation of LinkedListNode so it's not easy to play with this code. But looking at it I'm wondering if it correctly removes all duplicates, for example will it turn 1->2->2->2->2->3 into 1->2->3. (Maybe it does, a bit hard to decipher, but I suggest to do a quick test. And maybe next time include enough code so that reviewers can test run easily.)

UPDATE

As you remarked in your last comment, another way, without using a buffer / Set is to sort the list first, and remove the duplicates after. That would have \$O(n\log n)\$ complexity. However, keep in mind that the elements will be reordered with that approach (if they were not ordered to begin with). Depending on your use case, that may be perfectly acceptable, of course.