Re: single linked list header in kernel?

[Tonnerre <tonnerre@thundrix.ch>]

[-- Attachment #1: Type: text/plain, Size: 799 bytes --]

Salut,

On Wed, Oct 13, 2004 at 08:25:43PM +0200, Matthias Urlichs wrote:
> I dunno, though -- open-coding a singly-linked list isn't that much of a
> problem; compared to a doubly-linked one, there's simply fewer things that
> can go horribly wrong. :-/

The problem is that 

1. you have to use circular lists

2. going forward is  O(1), going backward is O(N).  This doesn't sound
   like a problem,  but deleting from lists and  alike requires you to
   go back in the list.

I guess  that if  you have lists  that you  edit a lot,  double linked
lists should be  less overhead. However, if you only  walk the lists a
lot, both models should perform equally well.

Insertion is faster, but that's the only good news..

I'm all against them, though. ;)

			    Tonnerre


[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]