From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.c
Subject: Re: Making a linked list...
Date: 29 Sep 92 04:23:54 GMT
Organization: Comp Sci, RMIT, Melbourne, Australia

In article <1992Sep24.091108.29805@dxcern.cern.ch>, riipinen@dxcern.cern.ch (Petri Juhani Riipinen) writes:
> The problem: To do a linked list with one function.

What does it mean "to DO a linked list"?  Create?  Traverse?

> typedef struct { int a_somedata;   /* I should make a list of these */
> 		 int b_somedata;
> 		 void *next;
> 	       } ONE_NODE;

You do not want to use void* .  What is void* for?  When you need a pointer
to a data object, but you do not know which type (perhaps because you need
to handle several known types, perhaps because, like qsort(), you need to 
handle _any_ reasonable type).  For a linked list, you know _exactly_ what
you are pointing to and should say so.

When you have a linked list in Pascal or C, you have two types:
    a record type (C struct)
    a pointer type
These types are mutually recursive:  the pointers point to the records,
and the records contain pointers.  You need some special hack so that you
can declare these things.  In Pascal, you do

	type
	    NodePtr = ^NodeRec;
	    NodeRec = record
		next: NodePtr;
		item: ItemType;
	    end;

In C you have more choices, but to keep it like the Pascal version, do

	typedef struct Node *NodePtr;
	typedef struct Node
	    {
		NodePtr  next;
		ItemType item;
	    } NodeRec;

In both languages, whenever you have a dynamically allocated record type,
it is a good idea to write a function that allocates records of that type
and fills in all the fields.  If my types are NodePtr and NodeRec, I often
use consNode as the function name.

	function consNode(next: NodePtr; item: ItemType): NodePtr;
	    var result: NodePtr;
	    begin
		new(result);
		result^.next := next;
		result^.item := item;
	    end;

	NodePtr consNode(NodePtr next, ItemType item)
	    {
		NodePtr result = malloc(sizeof *result);
		assert(result != NULL);
		result->next = next,
		result->item = item;
		return result;
	    }

Note the use of the assert() macro from the <assert.h> header; Pascal's
"new" statement reports "out of memory" by killing your program, while
C's "malloc()" function returns NULL.  ALWAYS CHECK THE RESULT OF A FUNCTION
WHICH CAN "GO WRONG" (this includes malloc(), realloc(), fopen(), fwrite(),
and a cast of thousands).

How to build up a linked list by adding new nodes at the front.

    In Pascal
	var
	    theList: NodePtr;
	    ...
	begin
	    theList := NULL;
	    ...
	        theList := consNode(theList, newFirstItem);
	    ...
	    (* don't forget to dispose() the memory you allocated! *)
	end;

    In C:
	{
	    NodePtr theList = NULL;
	    ...
	        theList = consNode(theList, newFirstItem);
	    ...
	    /* don't forget to free() the memory you allocated! */
	}

It is often better to build up a linked list by adding new nodes at the end.

    In Pascal
	var
	    theList, itsLastNode, temp: NodePtr;
	    ...
	begin
	    theList := NIL;
	    itsLastNode := NIL;
	    ...
		temp := consNode(NIL, newLastItem);
	        if itsLastNode = NIL then theList := temp
	        else itsLastNode^.next := temp;
	        itsLastNode := temp;
	    ...
	end;

    In C this can be considerably simplified by using a pointer to a
    field, something which is syntactically impossible in Pascal.

	{
	    NodePtr theList = NULL;
	    NodePtr *itsLastPtr = &(theList);
	    ...
	        *itsLastPtr = consNode(NULL, newLastItem);
		itsLastPtr = &((*itsLastPtr)->next);
	    ...
	}

    If you want to package that up as a function, then

	void addNode(NodePtr **last, ItemType item)
	    {
		NodePtr temp = consNode(NULL, item);
		**last = temp;
		*last = &(temp->next);
	    }

    and use
		addNode(&itsLastPtr, newLastItem);

If you are really unhappy about this technique, the classic technique
in Pascal was to build the list from right to left, and then reverse it.

-- 
RMIT policy requires the use of Gender Inclusive Language in all publications
and in all information conveyed to students, staff, and potential job
applicants.  Lapses into English are the sole responsibility of the author.
The Constitution of Australia does _not_ guarantee Freedom of Speech.