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

1. ## 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;

{
first = null;
last = null;
size = 0;
}

{
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;
}

{

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())
{
}

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;
try
{

while ((input = br.readLine()) != null)
{
data = Integer.parseInt(input);
}

}

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. ## 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. ## 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. ## 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. ## 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.