static list initialization

[Steve Summit]

In article <196 at donk.UUCP> ajw at donk.UUCP (ajw) writes:
>Here's a fragment of code I find myself staring at glumly from
>time to time.  It sets up the nucleus of a 2-way list, into
>which extra malloc'd nodes will be inserted.

In general, I try not to have statically- and dynamically-
allocated elements in the same list, because of the possibility
of trying to free one of the statically-allocated ones.
Preventing this can require ugly special cases.

I usually use something like

	static struct whatever *head = NULL;
	static struct whatever *tail = NULL;

	insert_at_head(stuff)
	int stuff;
	{
	struct whatever *new;

	new = (struct whatever *)alloc(sizeof(struct whatever));

	new->eresting_stuff = stuff;
	new->next = head;
	head = new;
	new->prev = NULL;
	if(tail == NULL)
		tail = new;
	}

Note that head and tail are now pointers, not structures.  This
still requires one special case, to set tail initially, which is
one reason I don't like doubly-linked lists.  Complexity seems to
be O(n**2) with the number of links, so that doubly-linked lists
are four times as hard to get right as singly-linked ones.  (You
can insert at either the head or tail of a singly-linked list
without special casing the initial case, if you're clever.)

                                            Steve Summit
                                            scs at adam.pika.mit.edu