4
\$\begingroup\$

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(n2). 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?

\$\endgroup\$
  • \$\begingroup\$ What makes you think that you does something wrong? Doesn't your code give you the results that you expect? \$\endgroup\$ – Simon Forsberg Nov 22 '14 at 22:46
  • \$\begingroup\$ @SimonAndréForsberg No my code works . I meant the code that I wrote still gives O(n^2) complexity which is not efficient . \$\endgroup\$ – maniac87 Nov 22 '14 at 23:10
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I know how to solve this in O(n) using external buffer but my question was how to make the solution efficient without using buffer . even though in the above code we dont compare each element with the rest of the elements but the complexity is still O(n2) \$\endgroup\$ – maniac87 Nov 22 '14 at 23:20
  • 1
    \$\begingroup\$ Ah ok that's what you meant by buffer... Without a map/set, there's no way around \$O(n^2)\$: you have to compare all elements against all other, unless there are other conditions you can benefit from, for example the list items being sorted. \$\endgroup\$ – Stop ongoing harm to Monica Nov 22 '14 at 23:24
  • 1
    \$\begingroup\$ Well another way is to sort the linkedList = O(nlogn) and then remove duplicates from sortedLinkedList = O(n) which is total O(nlogn) operation but this is not inplace algorithm . I guess you are right that without using external storage the complexity will be O(n2) \$\endgroup\$ – maniac87 Nov 22 '14 at 23:40
  • \$\begingroup\$ Good point! I updated my post to mention that. \$\endgroup\$ – Stop ongoing harm to Monica Nov 23 '14 at 22:35
  • \$\begingroup\$ If you control the linked list class you could let each node have two additional pointers (sorted next and previous) you could then implement say quick sort on these pointers and use those to remove duplicates. Without affecting the original ordering :) you will use additional memory per node but it will probably be small in comparison to the size of T. \$\endgroup\$ – Emily L. Apr 24 '17 at 10:07

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.