How do I sort the nodes in add method of linked list?

Question

//Node Class
public class MyNode<T extends Comparable<T>> implements INode<T> {
    public T key;
    public MyNode next;

    public MyNode(T key) {
        this.key = key;
        this.next = null;
    }
    @Override
    public T getKey() {
        return key;
    }

    @Override
    public void setKey(T key) {
        this.key = key;
    }

    @Override
    public INode getNext() {
        return next;
    }

    @Override
    public void setNext(INode next) {
        this.next = (MyNode) next;
    }

    @Override
    public int compareTo(INode<T> o) {
        return this.getKey().compareTo(o.getKey());
    }
}

public interface INode<T> {
    T getKey();
    void setKey(T key);
    INode<T> getNext();
    void setNext(INode next);

}

//Linked List Logic 
public class LinkedList<T> {
    public INode head;
    public INode tail;

    public LinkedList() {
        this.head = null;
        this.head = null;
    }


    public void addToLinkedListTest(INode newNode) {
        if (head == null) {
            this.head = newNode;
        }
        if (tail == null) {
            this.tail = newNode;
        } else {
            INode temp = this.head;
            this.head = newNode;
            this.head.setNext(temp);
        }
    }


    public void popLastElement() {
        if (head != tail) {
            INode temp = head;
            while (temp.getNext() != tail) {
                temp = temp.getNext();
            }

            this.tail = temp;
            INode tempOne = temp.getNext();
            tempOne = null;
        }
    }

    public void appendToLinkedList(INode newNode) {
        if (head == null) {
            this.head = newNode;
        }
        if (tail == null) {
            this.tail = newNode;
        } else {
            this.tail.setNext(newNode);
            this.tail = newNode;
        }
    }

    public void insertToLinkedList(INode beforeNode, INode afterNode, INode newNode) {
        INode temp = beforeNode.getNext();
        beforeNode.setNext(newNode);
        newNode.setNext(afterNode);
    }

    public void popFirstElement() {
        this.head = this.head.getNext();
    }

    public void printLinkedList() {
        StringBuffer allNodes = new StringBuffer();
        INode temp = head;
        while (temp.getNext() != null) {
            allNodes.append(temp.getKey());
            if (!temp.equals(tail))
                allNodes.append("->");
            temp = temp.getNext();
        }
        allNodes.append(temp.getKey());
        System.out.println(allNodes);
    }

    public T searchUsingKey(T key) {
        INode temp = head;
        while (temp.getNext() != null) {
            if (temp.getKey().equals(key)) {
                System.out.println("Found");
            }
            temp = temp.getNext();
        }
        return key;
    }

    public void searchUsingKeyInsert(T key, INode newNode) {
        INode temp = head;
        INode tempAfter;
        while (temp.getNext() != null) {
            if (temp.getKey().equals(key)) {
                System.out.println("Found");
                tempAfter = temp.getNext();
                insertToLinkedList(temp, tempAfter, newNode);
            }
            temp = temp.getNext();
        }

    }

    public void deleteUsingKey(T key) {
        INode temp = head;
        INode tempAfter;
        while (temp.getNext() != null) {
            if (temp.getNext().getKey().equals(key)) {
                tempAfter = temp.getNext().getNext();
                temp.setNext(tempAfter);
                break;
            }
            temp = temp.getNext();

        }

    }

    public void printAfterPopLast() {
        StringBuffer allNodes = new StringBuffer();
        INode temp = head;
        while (temp.getNext() != null) {
            allNodes.append(temp.getKey());
            if (!temp.equals(tail))
                allNodes.append("->");
            temp = temp.getNext();
        }
        System.out.println(allNodes);
    }

}

// I have tried using comparator and comparable for comparing the nodes but none of them worked or I may have gone wrong with implementation Need to sort while adding the elements to linked list with genric type T. Or even sorting after insertion wouldd help me solve part of the problem. Not sure where to use compareTo method like in Node class or linkedlist loggic class.

score 0 · Answer 1 · answered Mar 01 '21 at 11:13

I would suggest the following changes to support addSorted() in LinkedList.

Type parameter for LinkedList needs to be changed to class LinkedList<T extends Comparable<? super T>>. Refer this for using ? super T.
Change INode signature to interface INode<T, S extends<T>>. This will avoid casting in subclasses.
It is better to make MyNode inner class of LinkedList so that it can share type parameter of outer class.

Source:

INode Changes:

interface INode<T, S extends INode<T, S>> {
    // ...
    void setNext(S next);
}

LinkedList Changes:

public class LinkedList<T extends Comparable<? super T>> {

    public MyNode head;

    public LinkedList() {
        this.head = null;
    }

    public void addSorted(MyNode newNode) {
        if (this.head == null) {
            this.head = newNode;
            return;
        }
        if (head.getKey().compareTo(newNode.getKey()) > 0) {
            newNode.next = head;
            this.head = newNode;
            return;
        }
        MyNode prev = head, cur;
        while ((cur = prev.next) != null && cur.getKey()
                                               .compareTo(newNode.getKey()) < 0) {
            prev = cur;
        }
        prev.next = newNode;
    }

    class MyNode implements INode<T, MyNode> {
        //...
        @Override
        public void setNext(MyNode next) {
        }
    }
}

How do I sort the nodes in add method of linked list?

1 Answers1