[fpc-devel] TList or TFPList - a Linked list ?

[Daniël Mantione]

Op Wed, 14 Dec 2005, schreef Micha Nelissen:

> On Wed, 14 Dec 2005 21:44:50 +0100 (CET)
> Daniël Mantione <daniel.mantione at freepascal.org> wrote:
> 
> > Op Wed, 14 Dec 2005, schreef Micha Nelissen:
> > 
> > Sorry to disappoint, but this doesn't look a very good idea to me; it 
> > would kill code that for example tries to sort a list. There will be also 
> > a lot of code that iterates using index[].
> 
> Did you read the paragraph, "to solve (2) ..." ? Sorting is also quite a
> "local" operation, no ? No truly random-access is needed.

Yes I did, but caching the previous and the next is no solution for 
sorting. There exists no magic data structure that can replace both the 
list and the array.

> > Programmers need both list like datastructures and array like data 
> > structures. It is part of converting mathematical abstraction principles 
> 
> Array like datastructures are provided by dynamic arrays, I'd say ?

Yes, but a linked list also can be implemented using a record with a 
pointer; object oriented libraries a little bit extra power to 
the code, which a dynamic array cannot provide.

> > like a sequence where every operation is O(1), to actual datastructures 
> > that are to be used inside a compiler. Programmers need both of them, not 
> > one or the other.
> 
> Yes, currently there is no linked list at all, is there ?

Afaik, no, we could use one, so please add it, and we're all happy :) 

> These issues are precisely the reason I'm writing to the list and gathering
> ideas first.

I know, no problem.

Daniël