4
\$\begingroup\$

This sorts a linked list using mergegort. Can you please critique my code and provide your thoughts on where I should improve my code?

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList<T extends Comparable<T>> implements Iterable<T> {

    private Node<T> head;

    public LinkedList() {
        head = null;
    }

    @Override
    public String toString() {
        StringBuffer result = new StringBuffer();

        for (Iterator<T> i = this.iterator(); i.hasNext();) {
            result.append((Object) i.next() + " ");
        }
        return result.toString();
    }

    /*******************************************************
     *
     * add first element
     *
     ********************************************************/
    public void addFirst(T item) {
        head = new Node<T>(item, head);
    }

    /*******************************************************
     *
     * merge sort linked list
     *
     ********************************************************/
    public void mergeSortLinkedList(LinkedList<T> linkedList) {
        head = sortLinkedList(linkedList.head);
    }

    private Node<T> sortLinkedList(Node<T> head) {

        if (head == null || head.next == null)
            return head;

        int totalNumberOfElements = getCount(head);

        int mid = totalNumberOfElements / 2;

        Node<T> currentNode = head;
        Node<T> left = head;
        Node<T> right = null;

        int countHalf = 0;
        while (currentNode != null) {
            countHalf++;
            Node<T> next = currentNode.next;

            if (countHalf == mid) {
                currentNode.next = null;
                right = next;
            }
            currentNode = next;
        }

        Node<T> leftHalf = sortLinkedList(left);
        Node<T> rightHalf = sortLinkedList(right);
        Node<T> mergedLinkedList = merge(leftHalf, rightHalf);

        return mergedLinkedList;
    }

    private Node<T> merge(Node<T> left, Node<T> right) {
        Node<T> leftNode = left;
        Node<T> rightNode = right;

        Node<T> duplicateHead = new Node<T>(null, null);
        Node<T> currentNode = duplicateHead;

        while (leftNode != null || rightNode != null) {

            if (leftNode == null) {
                currentNode.next = new Node<T>(rightNode.data, null);
                rightNode = rightNode.next;
                currentNode = currentNode.next;

            } else if (rightNode == null) {
                currentNode.next = new Node<T>(leftNode.data, null);
                leftNode = leftNode.next;
                currentNode = currentNode.next;

            } else {
                if (compare(leftNode.data, rightNode.data) < 0) {
                    currentNode.next = new Node<T>(leftNode.data, null);
                    leftNode = leftNode.next;
                    currentNode = currentNode.next;

                } else if (compare(leftNode.data, rightNode.data) == 0) {
                    currentNode.next = new Node<T>(leftNode.data, null);
                    currentNode.next.next = new Node<T>(rightNode.data, null);
                    currentNode = currentNode.next.next;
                    leftNode = leftNode.next;
                    rightNode = rightNode.next;

                } else {
                    currentNode.next = new Node<T>(rightNode.data, null);
                    rightNode = rightNode.next;
                    currentNode = currentNode.next;
                }
            }
        }

        return duplicateHead.next;
    }

    private int getCount(Node<T> head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }

    private int compare(T a, T b) {
        return a.compareTo(b);
    }

    /*******************************************************
     *
     * node class
     *
     ********************************************************/
    private static class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    /*******************************************************
     *
     * iterator class
     *
     ********************************************************/
    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements Iterator<T> {

        private Node<T> temp;

        public LinkedListIterator() {
            temp = head;
        }

        @Override
        public boolean hasNext() {
            return temp != null;
        }

        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            T item = temp.data;
            temp = temp.next;
            return item;
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> list1 = new LinkedList<Integer>();
        list1.addFirst(4);
        list1.addFirst(2);
        list1.addFirst(5);
        list1.addFirst(8);
        System.out.println(list1);

        list1.mergeSortLinkedList(list1);
        System.out.println(list1);
    }
}
\$\endgroup\$
2
\$\begingroup\$

First of all you should use StringBuilder, not StringBuffer. Unless you have a good reason in a multithreading environment, then you probably could use StringBuffer. (Just replace the class names, everything else stays the same).


I think this is a exercise for university. So I divide my review in two parts. First I don't ask 'why' on many places, then I ask 'why' ;-)


The algorithm seems to be fine to me. I found only one hidden bug, but the bug has nothing to do with the merge sort:

The signature of this method seems to be strange to me:

public void mergeSortLinkedList(LinkedList<T> linkedList)

You have a linked list, you call this method of the linked list and have to give it a linked list. For me this looks like you can merge two lists together and then sort the result... merge, sort... not the behavior you want to express.

But what happens if you call this method this way:

userNameList.mergeSortLinkedList( addressList );

Now the userNameList will contain addresses in sorted order, but addressList is unchanged.

I think you have to change the signature and there are two choices:

public static void mergeSortLinkedList(LinkedList<T> linkedList)
public void mergeSortLinkedList()

and maybe you shouldn't call it mergeSortLinkedList(). It is a method of a LinkedList, so you could call it mergeSort() but the used algorithm is a implementation detail, so sort() would be enough (you could explain the used algorithm in the documentation comment above the method, which is missing right now).

I like the merge() method. You can see the functionality in a second. The only thing: you get two parameters, assign them to two variables and ignore the parameters after this. You don't need those two variables, you can simply use the parameters.


Now the 'why' part:

Why did you reinvented the LinkedList? There is a java.util.LinkedList. If this is an exercise, you have to, ok.

Why didn't you implement simple accessor and manipulation methods like get(int index), remove(int index) (or removeFirst because of your addFirst), isEmpty() and so on. Together with a sublist(int start, int length) you could do implement merge sort on a higher level.

Then you have to operate on the LinkedList instead of Nodes. But in merge() you can do something like this to move an element:

if (left.isEmpty()) {
    mergedList.addFirst(right.removeFirst());
}

or removeLast() to get the ordering right.

Why do you add new elements at the head? It'll me more natural when you add it at the tail of the list.

Why did you implement an iterator? In your case you didn't really need it.


A performance hints:

the sortLinkedList should take the length of the list as parameter. Then you don't have to count the number of elements of each (sub-) list each time, and for the recursive calls of sortLinkedList you can calculate the lengths of the sublists.

You can see the difference by executing the sort method 1.000.000 times in a for loop and measuring the elapsed time with System.currentTimeMillis(). Even though you gonna sort a sorted list, you will see a difference.

\$\endgroup\$

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.