Removing "custom" duplicates from a LinkedList

Question

I have a LinkedList collection that is already populated and each node contains a ID, Name, Age. I want to delete any nodes that have the same name and age in my LinkedList even if the ID is different. For example, if my list has

111, Joe, 21
222, Bob, 20
333, Bob, 20 //duplicate, should be deleted
444, Bob, 40

I would delete the 2nd "Bob" because it is considered a duplicate in my program, but would not delete the 3rd "Bob" because he has a different age. I did some googling and people would put the LinkedList into a Set (Since it can't have duplicates) then put it back into a LinkedList, but it wouldn't work for my case since the ID is different.

Answer 1

You can still use a set, you just have to override the hashCode and equals methods of your class having into account only the name and age fields.

public class Person{
    private int id;
    private String name;
    private int age;

    @Override
    public int hashCode(){
        int result = 17;
        result = 31 * result + name.hashCode();
        result = 31 * result + age;
        return result;
    }

    @Overrite
    public boolean equals(Object o) {

        if (o == this) return true;
        if (!(o instanceof Person)) {
            return false;
        }

        Person person = (Person) o;

        return person.name.equals(name) &&
                person.age == age ;
    }
}

Answer 2

The key is how you identify two elements as being "equal". To do this, you'd need to override the equals method from Object. Then once your two elements are considered equals, you can use a variety of possible methods to remove duplicates: iterating, using a Set implementation (eg. TreeSet), and so forth.

Here's a minimal example for how you might go about this.

public class Record {
  private String id;
  private String name;
  private int age;

  // getters, setters, and constructor go here

  @Override
  public boolean equals(Object other) {
    if(other == null || ! other instanceof Record) {
      return false;
    } else if (this == other) {
      return true;
    } else {
      return this.name.equals(other.name) && this.age == other.age; // possible NPE if name is null, handle as appropriate
    }
  }
}

Now if you have two identical records, you can remove them:

Record bob1 = new Record(222, "Bob", 20);
Record bob2 = new Record(333, "Bob", 20);
Record bob3 = new Record(444, "Bob", 40);

bob1.equals(bob2); //true -> remove one
bob1.equals(bob3); //false 
bob2.equals(bob3); //false 

Note that if you override equals, you'll want to override hashCode as well.

The problem with the data that you provided in your example is that the only differing characteristic between the two 20-year-old "Bob" records is the id number. Which one should be removed, 222 or 333?

Answer 3

Alternatively you could do this, order your list by name and then by age using a comparable, then if a name and age it's the same between i and i-1 index you can remove i Node.

public static class Node implements Comparable<Node>{
    int ID;
    String name;
    int age;

    //order by name
    public int compareTo( Node o ){
        if(name.equals(o.name)){
            return age - o.age;
        }
        return name.compareTo(o.name);
    }
}
 public static void main(String []args){

    LinkedList<Node> list = new LinkedList<Node>();
    //insert data...

    Collections.sort(list);
    int i = 1;
    while(i < list.size()){
        Node a = list.get(i-1);
        Node b = list.get(i);
        if( a.name.equals(b.name) && a.age == b.age ){
            list.remove(i);
        }else{
            i++;
        }
    }
 }

}

Answer 4

if your linked list is not sorted then use the following code in assumption that your linked list has no modified structure:

void removeDuplicates() {
    Node ptr1 = null, ptr2 = null, dup = null;
    ptr1 = head;

    // Pick elements one by one 
    while (ptr1 != null && ptr1.next != null) {
        ptr2 = ptr1;

        // Compare the picked element with rest of the elements
        while (ptr2.next != null) {

         // If duplicate then delete it 
         if (ptr1.name.equals(ptr2.next.name) && ptr1.age == ptr2.next.age){

                // sequence of steps is important here
                dup = ptr2.next;
                ptr2.next = ptr2.next.next;
                System.gc();
            } else {
                ptr2 = ptr2.next;
            }
        }
        ptr1 = ptr1.next;
    }
}