Question

How would I make a generic insertion sort for a doubly linked list in java?

or is it even possible to make it generic in the first place?

Answer 1

CODE

static Node<T> sortedInsert(Node<T> head_ref, Node<T> newNode)

{

Node<T> current;

if (head_ref == null)

head_ref = newNode;

else if ((head_ref).data.compareTo(newNode.data) >= 0)

{

newNode.next = head_ref;

newNode.next.prev = newNode;

head_ref = newNode;

} else

{

current = head_ref;

while (current.next != null && current.next.datA.compareTo(newNode.data) < 0)

current = current.next;

newNode.next = current.next;

if (current.next != null)

newNode.next.prev = newNode;

current.next = newNode;

newNode.prev = current;

}

return head_ref;

}

static Node<T> insertionSort(Node<T> head_ref)

{

Node<T> sorted = null;

Node<T> current = head_ref;

while (current != null)

{

Node<T> next = current.next;

current.prev = current.next = null;

sorted = sortedInsert(sorted, current);

current = next;

}

head_ref = sorted;

return