Thread: 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.

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.

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.

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

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.