Member Avatar for 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.

  • 2 Contributors
  • 5 Replies
  • 118 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by WaltP

Dani AI

Generated

Both approaches already shown in the thread have merit: implemented a neat recursive insertInto that builds the sorted list by allocating new nodes, and correctly pointed out that an iterative loop is often simpler. A couple of practical pitfalls worth calling out:

  • Rebuilding the list with makeList for every insertion (the recursive approach) allocates N new nodes while leaving the originals reachable nowhere — that is a memory leak unless the original nodes are freed.
  • Recursion uses O(n) stack space and can overflow for long lists. The overall time complexity remains O(n^2) either way.

A robust alternative is an in-place iterative insertion sort that reuses nodes and needs only O(1) extra memory. The usual pattern is to maintain a sentinel (dummy) head for the sorted list, then iterate the input list, extracting the current node and inserting it into the correct place in the sorted list by adjusting nextPtr. This avoids allocations and simplifies head-insert logic.

Example sketch of the core loop (uses the same nextPtr field shown earlier):

List insertionSort(List head) {
    Node dummy;
    dummy.nextPtr = NULL;
    List cur = head;
    while (cur) {
        List next = cur->nextPtr;
        List prev = &dummy;
        while (prev->nextPtr && prev->nextPtr->data < cur->data)
            prev = prev->nextPtr;
        cur->nextPtr = prev->nextPtr;
        prev->nextPtr = cur;
        cur = next;
    }
    return dummy.nextPtr;
}

Notes and troubleshooting:

  • If the assignment forbids direct field access and forces getFirst/getRest/makeList, implement an iterative "extract-and-rebuild" that calls getFirst/getRest to read values and makeList to prepend into the sorted list — but free the processed original nodes or this will leak memory.
  • Use a dummy head to avoid special-casing head insertion.
  • Test edge cases: empty list, single element, all-equal values, strictly descending input.
  • Keep an eye on nextPtr updates (always save next before re-linking a node).

Recommended Answers

All 5 Replies

Member Avatar for 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.

Member Avatar for 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;
}
Member Avatar for WaltP

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

Member Avatar for 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.

Member Avatar for WaltP 
Get start NODE
While NODE exists
    do something
    NODE = NODE->next
end-loop

It's quite simple.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.