Creating a Linked List that is Sorted in Descending order

user_17425767 0
Viewed 420

I am currently studying how a linked list works.

I am having a hard time figuring out why my linked list only has one element.

Method insert() is supposed to accept a parameter and create a linked list sorted in descending order.

/**
* this code is supposed to insert the elements from 
* a given input and sort it descendingly.
*/

public void insert(T el) {
    SLL<T> linkedList = new SLL();
    SLLNode<T> insert = this.head;
    if (linkedList.isEmpty()) {
        linkedList.addtoHead(el);
        linkedList.print();
    } else {
        linkedList.addtoHead(el);
        while (insert.next != null) {
            int i = ((Comparable) head.info).compareTo(el);
            if (i == 0) {
                linkedList.delete(el);
            } else if (i > 0) {
                linkedList.addtoHead(el);
            } else if (i < 0) {
                linkedList.addtoHead(el);
            }
        }
    }
}

main()

System.out.println("Enter s1: ");
sc.nextLine();
String s1 = sc.nextLine(); 
String[] a1 = s1.split(" ");
SLL<Integer> sll1 = new SLL<Integer>();
System.out.println("First Linked List Contents:");
for(int i=0;i<a1.length;i++){
    int w = Integer.valueOf(a1[i]);
    sll1.insert(w);
}

Here is the input:

Enter s1: 
1 2 3

Output is supposed to look like this:

Linked List Contents:
3 2 1
linked-list sorting algorithm generics java
1 Answers

Your method insert() has to be responsible for only one operation - inserting a new node with the given value to the list.

That is the most important thing that you need to understand. Method insert() is not meant to create a list as shown in code SLL<T> linkedList = new SLL(); etc., it only inserts a new node into the existing list.

When you are creating a new list inside the insert() and modifying it instead of changing the existing list (that can referred with a key word this) is both incorrect logically and violates the Single responsibility principle.

If you need to discard duplicates, and the given value is already present in the list, then it has to be ignored. No need to modify the list by invoking delete(el), you're simply not inserting it.

There's also a couple of enhancement that I suggest you to apply:

  • Methods that are responsible for modification of the data structure usually return a boolean value.
  • No need to type-cast the node in order to invoke the compare() method on it, use the following generic type instead <T extends Comparable<T>>.

I've reimplemented your list from scratch to demonstrate the logic of insertion.

There could be four cases:

  • new node has to be inserted to the head of the list;
  • new node needs to be inserted to the tail;
  • new node has to be inserted to the tail;
  • the given value is already present and has to be discarded.

I've also included a simple implementation of addToHead() and the toString() methods that is used for demo purposes.

public class SSL<T extends Comparable<T>> {
    private SSLNode<T> head;

    /**
     * inserts a new element to the list
     * so that this list will be sorted in descending order.
     */
    public boolean insert(T el) {
        if (this.isEmpty()) { // or head == null (the key word `this` can be omitted)
            return addToHead(el);
        }

        SSLNode<T> previous = null;
        SSLNode<T> current = head;

        while (current != null && current.info.compareTo(el) > 0) {
            previous = current;
            current = current.next;
        }

        if (current != null && current.info.compareTo(el) == 0) { // discarding the duplicate
            return false; // list wasn't modified
        }

        SSLNode<T> insert = new SSLNode<>(el); // new node

        if (previous == null) { // inserting to the head of the list
            insert.next = head;
            head = insert;
        } else if (current == null) { // inserting to the tail of the list
            previous.next = insert;
        } else { // inserting in the middle of the list (between the previous and current)
            previous.next = insert;
            insert.next = current;
        }
        return true; // list was modified, new element was successfully inserted
    }

    /**
     * if head is null the new node containing the given value
     * will be assigned to it
     */
    private boolean addToHead(T el) {
        if (head != null) {
            return false;
        } else {
            head = new SSLNode<>(el);
            return true;
        }
    }

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

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        SSLNode<T> current = head;
        while (current != null) {
            result.append(current.info + (current.next != null ? " -> " : ""));
            current = current.next;
        }
        return result.toString();
    }

    public class SSLNode<T extends Comparable<T>> {
        private T info;
        private SSLNode<T> next;

        public SSLNode(T info) {
            this.info = info;
        }
    }
}

main() - demo

public static void main(String[] args) {
    int[] source = {1, 2, 3, 5, 4, 6, 7};
    SSL<Integer> list = new SSL<>();
    for (int nextItem: source) {
        list.insert(nextItem);
    }
    System.out.println("list: " + list);
}

Output

list: 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
user_179499450
Related