Sorting a Linked List

Question

Suppose I have the following dataset stored in a linkedlist (excluding the header):

ID | Name
1 | John
2 | Albert
3 | Simon

Now, I would like to sort the nodes according to, say, alphabetical order.

I would like to know how I can come up with my own sorting method without using Arrays (and similar stuff like Lists, Vectors, ArrayLists etc.) and without using a library sorting method (e.g. Collections.sort).

In other words, I would like to know the concept of sorting and how one should go about arranging the nodes in a systematic manner. It doesn't have to be efficient - it just has to work.

I'll be trying this out in Java but I would appreciate pseudocodes or tips / hints / other resources as well.

Thank you.

Addendum:

LinkedList.java

class LinkedList
{

    private Node head;  // first node in the linked list
    private int count;

    public int getCount()
    {
        return count;
    }

    public Node getHead()
    {
        return head;
    }

    public LinkedList()
    {
        head = null;    // creates an empty linked list
        count = 0;
    }

    public void deleteFromFront()
    {
        if (count > 0)
        {
            Node temp = head;
            head = temp.getLink();
            temp = null;
            count--;
        }
    }

    public void AddToFront(Object cd)
    {
        Node newNode = new Node(cd);
        newNode.setLink(head);
        head = newNode;
        count++;
    }

    public void RemoveAtPosition(int n)
    {
        int counter=1;
        Node previous=null;
        if(n==1)
            deleteFromFront();
        else if(n<=getCount())
            for(Node j=head;j!=null;j=j.getLink())
            {
                if(counter==n&&previous!=null)
                {
                    previous.setLink(j.getLink());
                    j.setLink(null);
                }
                previous=j;
                counter++;
            }
        else
            System.out.println("Unable to remove object at position "+n);
    }

    public void AddAtPosition(int n, Object cd)
    {
        int counter=1;
        Node newNode=new Node(cd);
        Node previous=null;
        for(Node j=head;j!=null;j=j.getLink())
        {
            if(counter==n&&previous!=null)
            {
                newNode.setLink(j.getLink());
                j.setLink(newNode);
            }
            previous=j;
            counter++;
        }
    }

    public void Swap(int n1, int n2)
    {
        // how do I swap nodes?
    }

    public void Sort()
    {
       // how do I sort nodes?
    }
}

Node.java

public class Node {

    private Object data;
    private Node link;

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getLink() {
        return link;
    }

    public void setLink(Node link) {
        this.link = link;
    }

    public Node(Object data) {
        this.data = data;
        this.link = null;
    }
}

Search for "bubble sort" if you are new to sorting concept. May it be easy for a beginner since the efficiency is not important for you. — phantasmagoria
– phantasmagoria, Commented Dec 30, 2012 at 15:28
Mm - I think I must've phrased my question wrongly. I do have the sorting algorithm but I'm having difficulties manipulating the nodes in the linked list structure. — Or Svantovit
– Or Svantovit, Commented Dec 30, 2012 at 15:30
Are you using Java's LinkedList, or did you make something yourself? — bowmore
– bowmore, Commented Dec 30, 2012 at 15:34
Then we'd like to see that code, otherwise, we can't really tell what your problem is — bowmore
– bowmore, Commented Dec 30, 2012 at 15:35

lkamal · Accepted Answer · 2013-11-04 05:26:28Z

2

If you want to do it yourself, insertion sort is really easy on linked lists. Create a new empty linked list, then insert all elements from the old one into it. Wikipedia has a C code example.

edited Nov 4, 2013 at 5:26

lkamal

3,9781 gold badge28 silver badges38 bronze badges

answered Dec 30, 2012 at 15:31

lynn

10.9k1 gold badge48 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Peter Lawrey · Accepted Answer · 2012-12-30 15:28:25Z

1

If you want to know how the JDK does it... I copies the list into an array, sorts that and copies it back.

You can use a bubble sort for a linked list but it will be slower, so it makes no sense, unless you like pain. ;)

answered Dec 30, 2012 at 15:28

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Comments

Ludovic Aelbrecht · Accepted Answer · 2012-12-30 15:42:00Z

1

I realize you say you don't want to use Collections.sort, but just to make sure: you do realize that Collections.sort allows you to implement for yourself the sorting order, right? If not, http://www.digizol.com/2008/07/java-sorting-comparator-vs-comparable.html (and many other resources) will provide info on that.

Otherwise, there are a lot of sorting algorithms you can implement. One of the easier to understand is Bubble Sort. http://en.wikipedia.org/wiki/Bubble_sort contains a good explanation of it, including a nice visualization of the different sorting steps.

But Bubble Sort isn't (at all) an efficient way of sorting. There are many other sorting algorithms (merge sort, insertion sort, quicksort, ... see Wikipedia's article on "Sorting algorithm" for an overview), and they each have their advantages and disadvantages. It depends on the data you're sorting which algorithm will fit best.

answered Dec 30, 2012 at 15:42

Ludovic Aelbrecht

1663 bronze badges

1 Comment

Or Svantovit Over a year ago

I understand :) I'm trying to grasp the following: (1) Manipulation of nodes in Linked Lists. (2) Implementing sorting algorithm. Purely for conceptual purpose. I'm trying to understand how this works.

Swapnil · Accepted Answer · 2012-12-30 15:30:04Z

0

You can copy the list into an array and sort that. Otherwise, there are various sorting algorithms that can be used i.e. merge sort, bubble sort etc.

You can see this for merge sort implementation.

answered Dec 30, 2012 at 15:30

Swapnil

8,3665 gold badges41 silver badges59 bronze badges

Comments

Scott Hunter · Accepted Answer · 2012-12-30 15:36:29Z

0

While not exactly the same, look at external sorts (where the data isn't loaded into memory; for example, you want to sort a file bigger than your RAM). They generally work by moving data between files, in a manner similar to how you might move nodes between linked lists.

answered Dec 30, 2012 at 15:36

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Collectives™ on Stack Overflow

Sorting a Linked List

5 Answers 5

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related