Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Insertion Sort on a Doubly Linked List

  1. #1
    Junior Member
    Join Date
    Jun 2011
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Insertion Sort on a Doubly Linked List

    I'm having some trouble on a problem. What is supposed to happen is that a list of integers is read into an unsorted Doubly Linked List, and then sorted using an insertion sort. The code I have for my Doubly Linked List class is
    class DoublyLinkedList
    {
    	private int size;
    	private Node first;
    	private Node last;
     
    	public DoublyLinkedList ()
    	{
    		first = null;
    		last = null;
    		size = 0;
    	}
     
    	public void add (int data)
    	{
    		if (first == null)
    		{
    			first = new Node(data, null, null);
    			last = new Node(data, null, null);
    		}
    		else if (size < 2)
    		{
    			Node newNode = new Node(data, first.getNext(), first);
    			first.setNext(newNode);
    			last = newNode;
    		}
    		else
    		{
    			Node newNode = new Node(data, null, last);
    			last.setNext(newNode);
    			last = newNode;
     
    		}
    		size++;
    	}
    	public int size()
    	{
    		return size;
    	}
     
    	public DoublyLinkedList sort()
    	{
    		DoublyLinkedList sortedList = new DoublyLinkedList();
     
    		sortedList.add(first.getData());
    		Node sortNode = first.getNext();
    		Node sortNode2 = first.getNext();
    		Node tempNode = sortedList.last;
    		Node tempNode2 = null;
     
    		for (int i = 0; i < size-1; i++)
    		{
    			if (sortNode.getData() >= sortedList.last.getData())
    			{
    				sortedList.add(sortNode.getData());
    			}
     
    			else
    			{
     
    				if (tempNode.getPrevious() != null)
    				{
    					for (int j = 0; j < sortedList.size-1; j++)
    					{
    						tempNode2 = tempNode.getPrevious();
    						Node tempNode3 = sortNode;
    						if (tempNode3.getData() >= tempNode2.getData())
    						{
    							tempNode2.setNext(tempNode3);
    							tempNode3.setPrevious(tempNode2);
    							tempNode3.setNext(tempNode);
    							tempNode.setPrevious(tempNode3);
    						}
     
    						else
    						{
    							tempNode = tempNode2;
    						}
    					}
    				}
     
    				sortedList.size++;
     
    			}
    			sortNode = sortNode2.getNext();
    			sortNode2 = sortNode2.getNext();
     
     
    		}
     
    		return sortedList;
    	}
     
     
    	public String toString ()
    	{
    		String temp = "";
    		Node printNode = first;
     
    		for (int i = 0; i < size(); i++)
    		{
    			temp += printNode.getData() + "\n";
    			printNode = printNode.getNext();
    		}
     
    		return temp;
    	}
     
    	public String backwards ()
    	{
    		String temp = "";
    		Node printNode = last;
     
    		for (int i = 0; i < size(); i++)
    		{
    			temp += printNode.getData() + "\n";
    			printNode = printNode.getPrevious();
    		}
     
    		return temp;
    	}
    }

    My Node class is
    class Node
    {
      private int data;
      private Node next;
      private Node previous;
     
      public Node(int data, Node next, Node previous)
      {
    	  this.data = data;
    	  this.next = next;
    	  this.previous = previous;
      }
     
      public int getData()
      {
    	  return data;
      }
     
      public Node getNext()
      {
    	  return next;
      }
     
      public Node getPrevious()
      {
    	  return previous;
      }
     
      public void setNext(Node next)
      {
    	  this.next = next;
      }
     
      public void setPrevious (Node previous)
      {
    	  this.previous = previous;
      }
    }

    And my main code which makes a new List then attempts to sort it.
    import java.io.*;
     
    public class A2Q1
    {
    	public static void main (String [] args)
    	{
    		String input = "";
    		int data;
    		DoublyLinkedList testList = new DoublyLinkedList();
    		try
    		{
     
    			BufferedReader br = new BufferedReader(new FileReader("unsorted.txt"));
    			while ((input = br.readLine()) != null)
    			{
    				data = Integer.parseInt(input);
    				testList.add(data);
    			}
     
    		}
     
    		catch (IOException E)
    		{
     
    		}
    		System.out.println("StartPreSort\n" + testList + "ENDED");
    		System.out.println("Backwards\n" + testList.backwards() + "Ended");
     
    		testList = testList.sort();
    		System.out.println("StratPostSort\n" + testList + "ENDED");
    	}
    }
    I think my problem is that my pointers are getting messed up, but I can't tell where. I've tried following my code by hand, but I can't see where the problem is. Any help would be greatly appreciated.


  2. #2
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,511
    My Mood
    Grumpy
    Thanks
    0
    Thanked 165 Times in 156 Posts

    Default Re: Insertion Sort on a Doubly Linked List

    Were you told to do the insertion sort this way? I ask because it can be performed in situ. That is you can sort the current List without creating a new List.

    You might want to Google the insertion sort algorithm. It appears you are making much harder than it needs to be with all those loops, if statements and Nodes. It should be achievable with only 2 Nodes, the Node you are attempting to insert and the current Node you are comparing it to.

  3. #3
    Junior Member
    Join Date
    Jun 2011
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Insertion Sort on a Doubly Linked List

    Ok, apparently I wildly misunderstood, I thought an insertion sort meant creating a new sorted list. I'm going to try and re-write it without making a new list.

  4. #4
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,511
    My Mood
    Grumpy
    Thanks
    0
    Thanked 165 Times in 156 Posts

    Default Re: Insertion Sort on a Doubly Linked List

    If this is a homework assignment then seek clarification from your teacher before trashing your code.

  5. #5
    Junior Member
    Join Date
    Jun 2011
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Insertion Sort on a Doubly Linked List

    It simply says "Insertion Sort", I got the idea that you needed two lists from my misunderstanding of the Wikipedia article on Insertion Sorts. My new Code is:
    	public void sort ()
    	{
    		if (size > 1)
    		{
    			Node sortNode = first.getNext();
    			Node currentNode = first;
     
    			sort1(sortNode, currentNode);
    		}
     
    	}
     
    	public void sort1 (Node sortNode, Node currentNode)
    	{
    		if (currentNode.getNext() != null)
    		{
    			if (sortNode.getData() > currentNode.getData())
    			{
    				sort1(sortNode, currentNode.getNext());
    			}
    			else
    			{
    				sortNode.setNext(currentNode.getNext());
    				currentNode.getNext().setPrevious(sortNode);
    				currentNode.setNext(sortNode);
    				sortNode.setPrevious(currentNode);
    			}
    		}
    		else
    		{
    			currentNode.setNext(sortNode);
    			sortNode.setNext(null);
    			sortNode.setPrevious(currentNode);
    			last = sortNode;
    		}
    	}

    It works, but I end up with the the 2nd node as all the nodes past the first.

Similar Threads

  1. From Doubly to Single linked list
    By Spamik in forum Collections and Generics
    Replies: 2
    Last Post: May 4th, 2011, 05:41 AM
  2. Help with a doubly linked circular list
    By TeamRival in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 3rd, 2011, 09:59 PM
  3. Sorting a doubly linked list
    By snufkin in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 26th, 2010, 11:01 AM
  4. Generic Doubly Linked List
    By javapenguin in forum What's Wrong With My Code?
    Replies: 23
    Last Post: October 23rd, 2010, 03:13 PM
  5. Pseudo code of insertion sort linked list
    By sungirl in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 23rd, 2010, 09:25 AM

Tags for this Thread