SPAM: Re: modprobe and lists

[Michael S. Zick]

On Fri May 19 2006 08:33, Yann E. MORIN wrote:
> Michael,
> All,
> 
> On Friday 19 May 2006 152, Michael S. Zick wrote:
> > The choices are un-directional or bi-directional; single or double link; lists
> uni-directional, right?
> 
> > A single linked, bi-directional list does not have a "next" or "previous" its
> > only "link" is both next and previous.
> > In tight memory situations that need a bi-directional, linked list; the
> > bi-directional, single-linked, list will save you an entry per element.
> 
> Sorry, I don't get it... :-/ Would you care to better explain?
> 

Ignoring single direction linked lists (ui-directional);

Bi-directional linked lists come in two flavors; single entry link
or double entry link.

Both support {add,remove}{head,tail} of the list.
Both support walking the list head->tail or tail->head.

Both support {insert,delete} of a member of the list, with a difference:
In a double linked list, the member can be {inserted,deleted} knowing only 
its base address;
In a single linked list, the you have to walk the list to find (either)
the previous or the next member.
The same applies with the delete function.

But if your {insert,delete} of list members (other than at head/tail) is
a rare operation, then you can cut your list member overhead in half using
a single linked, bi-directional list.

The single linked, bi-directional list has advantages doing insert list into
a list and the fact you can join the head and tail, rotate the list, and
split it at the new point.

- - - -

Single linked lists:
one link entry, named one of fwd_link, rev_link, or bi_link

Double linked lists:
two link entries, named next_link and prior_link

Or the code author's choice of some equivalent names.

Mike
> Regards,
> Yann E. MORIN.
>