Linkedlist implementation in Java Sorting not working

Question

I created my own linkedlist. I wanted to sort my linkedlist using Collections.sort method. So I extends MyLinkedList class to java.util.LinkedList. I also created Comparator and Comparable implementation. But both are not working. Please find below code.

// Linked List implementation.

package com.java.dsa;

class Node<E> {
    E data;
    Node<E> nextLink;
    public Node(E data) {
        this.data = data;
    }
}

public class MyLinkedList<E> extends java.util.LinkedList<E>{

    private static final long serialVersionUID = 1L;
    private Node<E> firstNodePointer;
    private Node<E> nodePointer;

    public boolean isEmpty() {
        return nodePointer == null;
    }

    public boolean add(E data) {
        super.add(data);

        Node<E> node = new Node<E>(data);

        if (firstNodePointer == null) {
            firstNodePointer = node;
            nodePointer = node;
        }else{
            nodePointer.nextLink = node;
        }
        nodePointer = node;
        return true;
    }

    public boolean remove(Object data){
        super.remove(data);

        Node<E> counterNodePointer = firstNodePointer;
        Node<E> tempNodePointer = firstNodePointer;

        while (counterNodePointer != null && !counterNodePointer.data.equals(data)) {
            tempNodePointer = counterNodePointer;
            counterNodePointer = counterNodePointer.nextLink;
        }
        if(tempNodePointer.equals(firstNodePointer)){
            firstNodePointer = firstNodePointer.nextLink;
            return true;
        }
        else if(counterNodePointer != null && tempNodePointer != null){
            tempNodePointer.nextLink = counterNodePointer.nextLink;
            return true;
        }
        return false;
    }

    public void printList() {
        Node<E> counterNodePointer = firstNodePointer;
        while (counterNodePointer != null) {
            System.out.println(counterNodePointer.data);
            counterNodePointer = counterNodePointer.nextLink;
        }
    }
}

// Test Linkedlist

package com.java.dsa;

import java.util.Collections;
import java.util.Comparator;

//Employee Class

class Employee implements Comparable<Employee> {
    private String name;
    private int id;

    public Employee(String name, int id) {
        super();
        this.name = name;
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    @Override
    public String toString() {
        return this.name + " " + this.id;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + id;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Employee other = (Employee) obj;
        if (id != other.id)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    @Override
    public int compareTo(Employee employee) {
        return this.id - employee.id;
    }
}

class EmployeeSort implements Comparator<Employee> {

    @Override
    public int compare(Employee emp1, Employee emp2) {

        if (emp2.getId() - emp1.getId() > 0)
            return 1;
        else
            return -1;
    }
}

public class TestLinkedList {
    public static void main(String[] args) {
        MyLinkedList<Employee> myList = new MyLinkedList<Employee>();

        for (int i = 10; i > 0; i--) {
            Employee emp = new Employee("Sohan "+i, i);
            myList.add(emp);
        }
        myList.printList();
        Collections.sort(myList, new EmployeeSort());
        myList.printList();
    }
}

Answer 1

Actually it works. It's just that your internal data structure is not updated by Collections.sort(), and since you base your assertion that the program doesn't work on the output of printList(), and this relies on that data structure, you see the order of elements untouched. Use this method instead:

public void printParentDataStructure() {
  for ( E e : this ) System.out.println( e );
}

and see that your comparator perfectly does its job. So your problem is that you have two data structures and don't keep them in sync. Your next question may be "And how can I keep them sync'ed?" - Well, essentially you should override each and every method, and call super() like you do in add() and remove(). Don't do that! It'd be a complete nonsense.

It's clear that you want to implement a linked list for learning the data strcuture, but maybe you should first better understand the basic principles of OOP programming.

Answer 2

java.util.LinkedList is not a class designed for subclassing and your code is probably just breaking its internals and invariants.

If you want to implement a linked list on your own, but want to save yourself the effort of implementing the full List interface, then use AbstractList as your base class. This class's express purpose is exactly what you are trying to do.