Linked List Insertion Sort

[Samadhi69]

I'm familiar with java and have made many data structures there. Not so much in C and to complicate it the professor wants the LL set up LISP style.

I know I need to iteratively sort the tail then insert, but the setup we were given lacks some of the pointers I'm used to. Here is the relevent code so far:

typedef struct Node{
	int data;
	struct Node *nextPtr;
}Node;

typedef Node *List;

List sortList (List L){
	if (isEmpty(L)||getRest(L)==NULL) return L;
	List rest = getRest(L);
	int val = getFirst L;
	if (val<=getFirst(rest)) rest = makeList(val, rest);
	else rest = insertInto(val, rest);
}

int getFirst (List L) { return L->data;}

List getRest (List L) { return L->nextPtr;}

int isEmpty (List L){
	return L==NULL;
}

List emptyList() {
	return (List) 0;
}

List makeList (int x, List L){
	List result = (List) malloc(sizeof(Node));
	result->data = x;
	result->nextPtr = L;
	return result;
}

So the only thing I'm missing is insertInto. The main thing I'm not sure of is how to step through the list like I would with java.
IE

public void insert (E data){
	Node<E> newNode = new Node<E> (data);
	Node<E> previous = null, current = head;

	while (current!= null && ((Comparable<E>) data).compareTo (current.data) > 0)
	{
		previous = current;
		current = current.next;
	}

	if (current == null) tail = newNode;

	if (previous==null){
		newNode.next = head;
		head = newNode;
	}
	else
	{
		previous.next = newNode;
		newNode.next = current;
	}
}

Any help would be most appreciated.

[WaltP]

The main thing I'm not sure of is how to step through the list like I would with java.

Stepping through the list is done by calling getFirst() which, I assume, returns the first node in the list. Then passing that node into getRest() returns the next node. Keep calling getRest() to step through the rest of the list.

To insert a node, find the position (the node that should follow your new node) always remembering the node you just left. Then readjust the pointers to insert your new node.

[Samadhi69]

Here's what I ended up using

List sortList (List L){
	if (isEmpty(L)||getRest(L)==NULL) return L;
	List rest = getRest(L);
	rest = sortList(rest);
	int val = getFirst(L);
	rest = insertInto(val, rest);
	return rest;
}

List insertInto (int v, List L){
	if (isEmpty(L)) return makeList(v, L);
	List result, temp;
	int x;
	temp = getRest(L);
	if (getFirst(L)<v) {
		x = v;
		v = getFirst(L);
		L = insertInto(x, temp);
	}
	result = makeList(v, L);
	return result;
}

[WaltP]

You sure do like recursion, don't you? Can't you just use a standard loop?

[Samadhi69]

The professor made us use the particular getFirst method that I specified above which returns an integer (the data value of the first node) not the node.

I used recursion because it fails fast which optimizes it and recursion is easy to code (if obscene sometimes in big O.....but it's already O(n^2) from insertion sort so...).

I'm very interested in seeing how this could be done with a loop.

[WaltP]

Get start NODE
While NODE exists
    do something
    NODE = NODE->next
end-loop

It's quite simple.