www.digitalmars.com         C & C++   DMDScript  

D - linked lists and iterators

reply "Sean L. Palmer" <seanpalmer earthlink.net> writes:
I think we should take another look at the possibility of adding linked
lists directly to the language and formalizing the concept of iterator as a
basic language feature.  Can this be done?  If so, how?

A linked list is, as you know, a string of pointers

struct T
{
    T* next;
    T* prev;
    int data;
}

{
    T* head = new T;  // I really want constructors for structs!!!!!
    head->data = 0;
    head->next = 0;
    head->prev = 0;

    T* ins = new T;
    ins->data = 1;
    ins->next = 0;
    ins->prev = head;
    head->next = ins;

    T* iter = head;
    while(iter)
    {
        printf("Node %d\n", iter->data);
        iter = iter->next;
    }
}


As you can see, it's extremely boilerplate code.  Lists are so well known
that a compiler could use the ultimate best algorithm for manipulating them.
And they could be syntactically wrapped so they look more like
container/iterator.

It would be easy with generics.  In fact, how you implement list may be a
big clue as to how to go about implementing generics.  Maybe something along
the lines of:

struct T
{
    int data;
    T(int d) { data = d; }
}

dlist(T) mylist;
mylist.addtail(T(0));
mylist.addtail(T(1));
dlist(T).iterator iter = mylist.head;
while (iter)
{
    printf("Node %d\n",iter->data);
    ++iter;
}

Sean
Jul 20 2002
next sibling parent reply Patrick Down <pat codemoon.com> writes:
"Sean L. Palmer" <seanpalmer earthlink.net> wrote in
news:ahckjc$6mt$1 digitaldaemon.com: 


 I think we should take another look at the possibility of adding
 linked lists directly to the language and formalizing the concept of
 iterator as a basic language feature.  Can this be done?  If so, how?


I would like to see the concept of iterators added to the language.

I see two types of operations on on basic arrays and the other
a more generalized form.

int[] arr;

for(int i in arr) // i gets successive values from arr
{
  //...
}

class Iter // or struct
{
  bit getNext(out aType i) { }
}

obj = new Iter;

for(aType i in obj) // i gets values from successive calls to getNext
{
  //...
}

The linked list works well this way

struct ListIter
{
  ListNode cur;

  bit getNext(out aType data)
  {
    if(cur.Next)
    {
      data = cur.data;
      return true;
    }
    return false;
  }  
}

ListIter iter;
iter.cur = list.head; // I too wish of struct constructors

for(aType i in iter)
{
  //...
}
Jul 20 2002
parent Patrick Down <pat codemoon.com> writes:
Forgot the cur = cur.Next;  :)

Patrick Down <pat codemoon.com> wrote in 
news:Xns9251C45EE91F3patcodemooncom 63.105.9.61:


 struct ListIter
 {
   ListNode cur;
 
   bit getNext(out aType data)
   {
     if(cur.Next)
     {
       data = cur.data;


        cur = cur.Next;

       return true;
     }
     return false;
   }  
 }
Jul 20 2002
prev sibling next sibling parent reply Pavel Minayev <evilone omen.ru> writes:
On Sat=2C 20 Jul 2002 14=3A35=3A27 -0700 =22Sean L=2E Palmer=22
=3Cseanpalmer=40earthlink=2Enet=3E 
wrote=3A

=3E It would be easy with generics=2E  In fact=2C how you implement list may be
a
=3E big clue as to how to go about implementing generics=2E  Maybe something
along
=3E the lines of=3A
=3E 
=3E struct T
=3E {
=3E     int data=3B
=3E     T=28int d=29 { data =3D d=3B }
=3E }
=3E 
=3E dlist=28T=29 mylist=3B
=3E mylist=2Eaddtail=28T=280=29=29=3B
=3E mylist=2Eaddtail=28T=281=29=29=3B
=3E dlist=28T=29=2Eiterator iter =3D mylist=2Ehead=3B
=3E while =28iter=29
=3E {
=3E     printf=28=22Node %d=5Cn=22=2Citer-=3Edata=29=3B
=3E     ++iter=3B
=3E }

Might I propose another syntax=3F

=09int=5B*=5D mylist=3B=09=09=2F=2F linked list of ints
=09mylist ~=3D 0=3B=09=09=2F=2F add to back
=09mylist =3D 1 ~ mylist=09=2F=2F add to front =28compiler should optimize
this=29
=09int=5B*=5D=2Eiterator i=3B=09=2F=2F or could it be just mylist=2Eiterator=3F
=09for =28i =3D mylist=2Ehead=3B i=3B i++=29
=09=09printf=28=22Node %d=5Cn=22=2C *i=29=3B

Also=2C int=5B*=5D could be one-directional linked list=2C while int=5B**=5D
would be
two-directional=2E

Or is it better to use int=5B-=3E=5D and int=5B=3C-=3E=5D for this purpose=3F
Jul 20 2002
parent reply "Sean L. Palmer" <seanpalmer earthlink.net> writes:
This sounds fine to me!  ;)  Makes it look almost just like existing dynamic
array syntax.

I like int[->] and int[<->] actually.

Is there some kind of search for dynamic array yet?  What about erase entry?

Sean

"Pavel Minayev" <evilone omen.ru> wrote in message
news:CFN374584471657523 news.digitalmars.com...
On Sat, 20 Jul 2002 14:35:27 -0700 "Sean L. Palmer"
<seanpalmer earthlink.net>
wrote:


 It would be easy with generics.  In fact, how you implement list may be a
 big clue as to how to go about implementing generics.  Maybe something


along

 the lines of:

 struct T
 {
     int data;
     T(int d) { data = d; }
 }

 dlist(T) mylist;
 mylist.addtail(T(0));
 mylist.addtail(T(1));
 dlist(T).iterator iter = mylist.head;
 while (iter)
 {
     printf("Node %d\n",iter->data);
     ++iter;
 }


Might I propose another syntax?

int[*] mylist; // linked list of ints
mylist ~= 0; // add to back
mylist = 1 ~ mylist // add to front (compiler should optimize this)
int[*].iterator i; // or could it be just mylist.iterator?
for (i = mylist.head; i; i++)
printf("Node %d\n", *i);

Also, int[*] could be one-directional linked list, while int[**] would be
two-directional.

Or is it better to use int[->] and int[<->] for this purpose?
Jul 21 2002
parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"Sean L. Palmer" <seanpalmer earthlink.net> wrote in message
news:ahemp8$25c6$1 digitaldaemon.com...

 I like int[->] and int[<->] actually.


Me too.


 Is there some kind of search for dynamic array yet?  What about erase


entry?

Ha! You do it all "by hand". Reminds me of BASIC times.

Sandor
Jul 23 2002
parent reply Pavel Minayev <evilone omen.ru> writes:
On Tue=2C 23 Jul 2002 09=3A35=3A51 +0200 =22Sandor Hojtsy=22
=3Chojtsy=40index=2Ehu=3E wrote=3A

=3E 
=3E =22Sean L=2E Palmer=22 =3Cseanpalmer=40earthlink=2Enet=3E wrote in message
=3E news=3Aahemp8$25c6$1=40digitaldaemon=2Ecom=2E=2E=2E
=3E=3E I like int=5B-=3E=5D and int=5B=3C-=3E=5D actually=2E
=3E 
=3E Me too=2E
=3E 
=3E=3E Is there some kind of search for dynamic array yet=3F  What about erase
=3E entry=3F
=3E 
=3E Ha! You do it all =22by hand=22=2E Reminds me of BASIC times=2E

Well=2C erasing entry is easy=3A

=09=2F=2F delete Nth element
=09array =3D array=5B0 =2E=2E N=5D ~ array=5BN+1 =2E=2E array=2Elength=5D=3B

Still=2C some syntactic sugar would be great=2E
Jul 23 2002
parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"Pavel Minayev" <evilone omen.ru> wrote in message
news:CFN374606396220486 news.digitalmars.com...

Well, erasing entry is easy:
// delete Nth element
array = array[0 .. N] ~ array[N+1 .. array.length];
Still, some syntactic sugar would be great.




Why do I have the feeling that the underlying implementation for that
expression will be slower than it could be for an explicit erase method?

Sandor
Jul 30 2002
next sibling parent "Sean L. Palmer" <seanpalmer earthlink.net> writes:
"Sandor Hojtsy" <hojtsy index.hu> wrote in message
news:ai5klg$273n$1 digitaldaemon.com...

 "Pavel Minayev" <evilone omen.ru> wrote in message
 news:CFN374606396220486 news.digitalmars.com...

Well, erasing entry is easy:
// delete Nth element
array = array[0 .. N] ~ array[N+1 .. array.length];
Still, some syntactic sugar would be great.




 Why do I have the feeling that the underlying implementation for that
 expression will be slower than it could be for an explicit erase method?


I think you're right... especially in debug builds.

Sean
Jul 31 2002
prev sibling next sibling parent reply Burton Radons <loth users.sourceforge.net> writes:
Sandor Hojtsy wrote:


 "Pavel Minayev" <evilone omen.ru> wrote in message
 news:CFN374606396220486 news.digitalmars.com...
 

Well, erasing entry is easy:
// delete Nth element
array = array[0 .. N] ~ array[N+1 .. array.length];
Still, some syntactic sugar would be great.




 
 Why do I have the feeling that the underlying implementation for that
 expression will be slower than it could be for an explicit erase method?


You're wrong, it would be the same speed.  There would be some tiny 
difference in the temporaries, but that would be bulldozed by the huge 
similarity in the data moving.
Jul 31 2002
next sibling parent "Sean L. Palmer" <seanpalmer earthlink.net> writes:
Every little bit helps at that level.  Waste not, want not.

Sean

"Burton Radons" <loth users.sourceforge.net> wrote in message
news:3D47CF6C.1020201 users.sourceforge.net...

 Sandor Hojtsy wrote:


 "Pavel Minayev" <evilone omen.ru> wrote in message
 news:CFN374606396220486 news.digitalmars.com...


Well, erasing entry is easy:
// delete Nth element
array = array[0 .. N] ~ array[N+1 .. array.length];
Still, some syntactic sugar would be great.




 Why do I have the feeling that the underlying implementation for that
 expression will be slower than it could be for an explicit erase method?


 You're wrong, it would be the same speed.  There would be some tiny
 difference in the temporaries, but that would be bulldozed by the huge
 similarity in the data moving.
Aug 01 2002
prev sibling parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"Burton Radons" <loth users.sourceforge.net> wrote in message
news:3D47CF6C.1020201 users.sourceforge.net...

 Sandor Hojtsy wrote:


 "Pavel Minayev" <evilone omen.ru> wrote in message
 news:CFN374606396220486 news.digitalmars.com...


Well, erasing entry is easy:
// delete Nth element
array = array[0 .. N] ~ array[N+1 .. array.length];
Still, some syntactic sugar would be great.




 Why do I have the feeling that the underlying implementation for that
 expression will be slower than it could be for an explicit erase method?


 You're wrong, it would be the same speed.  There would be some tiny
 difference in the temporaries, but that would be bulldozed by the huge
 similarity in the data moving.


Hmm... lets go into details. AFAIK this expression is compiled to a code
doing:
1) creating two new array handles, pointing inside the old array,
calculating their length
2) creating a new dinamic array by allocating memory from the heap for all
elements
3) copy the old array elements into this newly created array, with some more
unneccessary data moving
4) overwrite the old array handle with the new one
5) let the GC free the whole memory of the old array at some uncertain
future time

Now, I would not call that optimal.
And the same cycle wasting goes, when you insert a single element inside an
array.

Sandor
Aug 06 2002
parent Burton Radons <loth users.sourceforge.net> writes:
Sandor Hojtsy wrote:


 "Burton Radons" <loth users.sourceforge.net> wrote in message
 news:3D47CF6C.1020201 users.sourceforge.net...
 

Sandor Hojtsy wrote:



"Pavel Minayev" <evilone omen.ru> wrote in message
news:CFN374606396220486 news.digitalmars.com...



Well, erasing entry is easy:
// delete Nth element
array = array[0 .. N] ~ array[N+1 .. array.length];
Still, some syntactic sugar would be great.




Why do I have the feeling that the underlying implementation for that
expression will be slower than it could be for an explicit erase method?


You're wrong, it would be the same speed.  There would be some tiny
difference in the temporaries, but that would be bulldozed by the huge
similarity in the data moving.


 
 Hmm... lets go into details. AFAIK this expression is compiled to a code
 doing:
 1) creating two new array handles, pointing inside the old array,
 calculating their length
 2) creating a new dinamic array by allocating memory from the heap for all
 elements
 3) copy the old array elements into this newly created array, with some more
 unneccessary data moving
 4) overwrite the old array handle with the new one
 5) let the GC free the whole memory of the old array at some uncertain
 future time



Er, yes, it's slower if the pop method can modify the array data 
directly.  I'd assumed it would be a safe operation.  I wouldn't have 
any real problem with a pop method that changes the data, so long as the 
standard is clear.
Aug 06 2002
prev sibling parent reply "Walter" <walter digitalmars.com> writes:
"Sandor Hojtsy" <hojtsy index.hu> wrote in message
news:ai5klg$273n$1 digitaldaemon.com...

 "Pavel Minayev" <evilone omen.ru> wrote in message
 news:CFN374606396220486 news.digitalmars.com...

Well, erasing entry is easy:
// delete Nth element
array = array[0 .. N] ~ array[N+1 .. array.length];
Still, some syntactic sugar would be great.




 Why do I have the feeling that the underlying implementation for that
 expression will be slower than it could be for an explicit erase method?


It doesn't have to be. Better compilers can be tuned to recognize common
idioms.
Aug 11 2002
next sibling parent reply "Sean L. Palmer" <seanpalmer earthlink.net> writes:
It's useful for a programmer to have an idea what the average compiler will
do with a given language construct.  If the naive compilation will result in
huge bloat or inefficiency, it will be avoided by most careful programmers.

This is what language spec guarantees are useful for;  even better would be
a way to express such an operation that doesn't involve copying.  Copying is
not what you want, so why tell the compiler to copy something and then have
to rely on the compiler maker's good graces that it will figure out what you
mean, which is to delete an element?

I'm guessing here but I'd expect 9 out of 10 D implementations to suck to
the point of not doing that kind of complex optimization.  I'm a big fan of
saying exactly what you mean;  then the compiler doesn't have to be very
smart--it just has to follow instructions.

Sean

"Walter" <walter digitalmars.com> wrote in message
news:aj69tv$260u$1 digitaldaemon.com...

 "Sandor Hojtsy" <hojtsy index.hu> wrote in message
 news:ai5klg$273n$1 digitaldaemon.com...

 "Pavel Minayev" <evilone omen.ru> wrote in message
 news:CFN374606396220486 news.digitalmars.com...

Well, erasing entry is easy:
// delete Nth element
array = array[0 .. N] ~ array[N+1 .. array.length];
Still, some syntactic sugar would be great.




 Why do I have the feeling that the underlying implementation for that
 expression will be slower than it could be for an explicit erase method?


 It doesn't have to be. Better compilers can be tuned to recognize common
 idioms.
Aug 11 2002
parent "Walter" <walter digitalmars.com> writes:
"Sean L. Palmer" <seanpalmer earthlink.net> wrote in message
news:aj6i5d$2dsi$1 digitaldaemon.com...

 It's useful for a programmer to have an idea what the average compiler


will

 do with a given language construct.  If the naive compilation will result


in

 huge bloat or inefficiency, it will be avoided by most careful


programmers.

 This is what language spec guarantees are useful for;  even better would


be

 a way to express such an operation that doesn't involve copying.  Copying


is

 not what you want, so why tell the compiler to copy something and then


have

 to rely on the compiler maker's good graces that it will figure out what


you

 mean, which is to delete an element?

 I'm guessing here but I'd expect 9 out of 10 D implementations to suck to
 the point of not doing that kind of complex optimization.  I'm a big fan


of

 saying exactly what you mean;  then the compiler doesn't have to be very
 smart--it just has to follow instructions.


Early in the life cycle of a language, you are correct. Early C++ compilers
did not recognize common C++ idioms, and as a result generated horrible
code. As the competition between implementations heated up, the idioms were
fertile ground for optimization, and you can expect those idioms to be
recognized and custom code generated for them from every commercial
compiler.
Aug 14 2002
prev sibling parent reply Pavel Minayev <evilone omen.ru> writes:
On Sun=2C 11 Aug 2002 11=3A24=3A40 -0700 =22Walter=22
=3Cwalter=40digitalmars=2Ecom=3E wrote=3A

=3E It doesn't have to be=2E Better compilers can be tuned to recognize common
=3E idioms=2E

Well=2C for now we only have DMD fully working=2E=2E=2E does it able to optimize
this case=3F If not=2C will it be able to do so in near future=3F=2E=2E

Deleting an element is a basic operation=2C and it might be better to 
provide a distict method for it=2E Since you already use delete=5B=5D for
associative arrays=2C then it could be used here as well=3A


=09

=09
Aug 11 2002
next sibling parent reply "Walter" <walter digitalmars.com> writes:
"Pavel Minayev" <evilone omen.ru> wrote in message
news:CFN374801183164468 news.digitalmars.com...
On Sun, 11 Aug 2002 11:24:40 -0700 "Walter" <walter digitalmars.com> wrote:


Well, for now we only have DMD fully working... does it able to optimize
this case? If not, will it be able to do so in near future?..


No, and not in the near future. There are many more common idioms to do
first... and get the complete language done...
Aug 14 2002
parent reply Pavel Minayev <evilone omen.ru> writes:
On Wed, 14 Aug 2002 22:10:12 -0700 "Walter" <walter digitalmars.com> wrote:


Well, for now we only have DMD fully working... does it able to optimize
this case? If not, will it be able to do so in near future?..


 
 No, and not in the near future. There are many more common idioms to do
 first... and get the complete language done...


And I think it won't be that easy to implement, especially
for those guys who'll write other D compilers...

So, what about using delete[] to remove items from array?
Aug 15 2002
parent "Walter" <walter digitalmars.com> writes:
"Pavel Minayev" <evilone omen.ru> wrote in message
news:CFN374834661828819 news.digitalmars.com...

 So, what about using delete[] to remove items from array?


I don't have a good answer <g>.
Aug 15 2002
prev sibling parent reply Patrick Down <pat codemoon.com> writes:
Pavel Minayev <evilone omen.ru> wrote in
news:CFN374801183164468 news.digitalmars.com: 


 On Sun, 11 Aug 2002 11:24:40 -0700 "Walter" <walter digitalmars.com>
 wrote: 
 

 It doesn't have to be. Better compilers can be tuned to recognize
 common idioms.


 
 Well, for now we only have DMD fully working... does it able to
 optimize this case? If not, will it be able to do so in near future?..
 
 Deleting an element is a basic operation, and it might be better to
 provide a distict method for it. Since you already use delete[] for
 associative arrays, then it could be used here as well:
 



I like this.  Isn't it also consistant with the delete syntax
for associative arrays?
Aug 15 2002
parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"Patrick Down" <pat codemoon.com> wrote in message
news:Xns926B918ECEE58patcodemooncom 63.105.9.61...

 Pavel Minayev <evilone omen.ru> wrote in
 news:CFN374801183164468 news.digitalmars.com:


 On Sun, 11 Aug 2002 11:24:40 -0700 "Walter" <walter digitalmars.com>
 wrote:


 It doesn't have to be. Better compilers can be tuned to recognize
 common idioms.


 Well, for now we only have DMD fully working... does it able to
 optimize this case? If not, will it be able to do so in near future?..

 Deleting an element is a basic operation, and it might be better to
 provide a distict method for it. Since you already use delete[] for
 associative arrays, then it could be used here as well:




 I like this.  Isn't it also consistant with the delete syntax
 for associative arrays?


Consider the C++ code

int **a = new int *[200];
a[123] = new int;
delete a[123];

In C++ this deletes the memory allocated with the second "new", and leaves
the array size 200. It would be clearer for C++ coders to use some other
syntax in D for a completely different task. For example,

int []a;
a.length = 200;
a.erase(123);

The same goes for associative arrays.
Also I would be happy to see a syntax to write the first two lines of this
last example in one single line.

Sandor
Aug 21 2002
next sibling parent Pavel Minayev <evilone omen.ru> writes:
On Wed=2C 21 Aug 2002 11=3A41=3A51 +0200 =22Sandor Hojtsy=22
=3Chojtsy=40index=2Ehu=3E wrote=3A

=3E 
=3E Consider the C++ code
=3E 
=3E int **a =3D new int *=5B200=5D=3B
=3E a=5B123=5D =3D new int=3B
=3E delete a=5B123=5D=3B
=3E 
=3E In C++ this deletes the memory allocated with the second =22new=22=2C and
leaves
=3E the array size 200=2E It would be clearer for C++ coders to use some other
=3E syntax in D for a completely different task=2E For example=2C
=3E 
=3E int =5B=5Da=3B
=3E a=2Elength =3D 200=3B
=3E a=2Eerase=28123=29=3B
=3E 
=3E The same goes for associative arrays=2E

That syntax for D associative arrays exists for a long time already=2C
I don't think it would be wise to change it now=2E=2E=2E on the other hand=2C
applying it to simple arrays seems logical=2E

The simplest way to ensure correct behaviour is to use brackets=3A

=09delete=28a=5B123=5D=29=3B=09=2F=2F delete block pointer by a=5B123=5D
Aug 21 2002
prev sibling parent reply Russell Lewis <spamhole-2001-07-16 deming-os.org> writes:
Sandor Hojtsy wrote:

 "Patrick Down" <pat codemoon.com> wrote in message
 news:Xns926B918ECEE58patcodemooncom 63.105.9.61...
 

Pavel Minayev <evilone omen.ru> wrote in
news:CFN374801183164468 news.digitalmars.com:



On Sun, 11 Aug 2002 11:24:40 -0700 "Walter" <walter digitalmars.com>
wrote:



It doesn't have to be. Better compilers can be tuned to recognize
common idioms.


Well, for now we only have DMD fully working... does it able to
optimize this case? If not, will it be able to do so in near future?..

Deleting an element is a basic operation, and it might be better to
provide a distict method for it. Since you already use delete[] for
associative arrays, then it could be used here as well:




I like this.  Isn't it also consistant with the delete syntax
for associative arrays?


 
 
 Consider the C++ code
 
 int **a = new int *[200];
 a[123] = new int;
 delete a[123];
 
 In C++ this deletes the memory allocated with the second "new", and leaves
 the array size 200. It would be clearer for C++ coders to use some other
 syntax in D for a completely different task. For example,


How about "remove" instead of "delete"?
Aug 21 2002
next sibling parent Pavel Minayev <evilone omen.ru> writes:
On Wed, 21 Aug 2002 11:56:26 -0700 Russell Lewis 
<spamhole-2001-07-16 deming-os.org> wrote:


 How about "remove" instead of "delete"?


 
I don't mind. Not sure if Walter doesn't, though. =)
Aug 21 2002
prev sibling parent "Martin M. Pedersen" <mmp www.moeller-pedersen.dk> writes:
Hi,

"Russell Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3D63E25A.3020108 deming-os.org...

 How about "remove" instead of "delete"?


One of the strengths of D, is its ability to use the C libraries directly.
It wouldn't be wise to have a keyword that is also a function in the C
standard libraries, because it would prevent you from calling it.

Regards,
Martin M. Pedersen
Aug 21 2002
prev sibling parent Burton Radons <loth users.sourceforge.net> writes:
Sean L. Palmer wrote:


 I think we should take another look at the possibility of adding linked
 lists directly to the language and formalizing the concept of iterator as a
 basic language feature.  Can this be done?  If so, how?
 
 A linked list is, as you know, a string of pointers
 
 struct T
 {
     T* next;
     T* prev;
     int data;
 }
 
 {
     T* head = new T;  // I really want constructors for structs!!!!!
     head->data = 0;
     head->next = 0;
     head->prev = 0;
 
     T* ins = new T;
     ins->data = 1;
     ins->next = 0;
     ins->prev = head;
     head->next = ins;
 
     T* iter = head;
     while(iter)
     {
         printf("Node %d\n", iter->data);
         iter = iter->next;
     }
 }
 
 
 As you can see, it's extremely boilerplate code.  Lists are so well known
 that a compiler could use the ultimate best algorithm for manipulating them.
 And they could be syntactically wrapped so they look more like
 container/iterator.



The best generic algorithm with lists tends to be the same as the worst 
generic algorithm.  There's not a hell of a lot you can optimise.  But 
they are a useful generic type.



 It would be easy with generics.  In fact, how you implement list may be a
 big clue as to how to go about implementing generics.  Maybe something along
 the lines of:
 
 struct T
 {
     int data;
     T(int d) { data = d; }
 }
 
 dlist(T) mylist;
 mylist.addtail(T(0));
 mylist.addtail(T(1));
 dlist(T).iterator iter = mylist.head;
 while (iter)
 {
     printf("Node %d\n",iter->data);
     ++iter;
 }


-1 linked lists as a language feature, +1 iterators, -1 making it look 
anything at all like STL's.  I prefer Patrick's method, but using next, 
and without any special syntax.  A new extension to while, perhaps, to 
take for-style ';' separators for local variables.  I'm not opposed to 
for .. in, but getting over the Bright Barrier will require something 
more general, methinks.

Implementation hm.  I always need first/last, so I want a header, and 
prefer using List and Node for each:

     struct Node (TypeInfo $type)
     {
         List ($type) *list;
         Node ($type) *next;
         Node ($type) *prev;
         $type value;

         void remove ()
         {
             synchronize (list)
             {
                 if (next) next.prev = prev;
                 else list.last = prev;
                 if (prev) prev.next = next;
                 else list.first = next;
                 next = prev = null;
             }
         }
     }

     class List (TypeInfo $type)
     {
         Node ($type) *first;
         Node ($type) *last;

         Node ($type) *alloc ()
         {
             return new Node ($type); /* Should use block allocation */
         }

         Node ($type) *append ($type value)
         {
             synchronize (this)
             {
                 Node ($type) *node = alloc ();

                 node.next = null;
                 node.prev = last;
                 if (last) last.next = node;
                 else first = node;
                 last = node;

                 return node;
             }
         }

         ListIter ($type) iter ()
         {
             return ListIter ($type) (this);
         }
     }

     struct ListIter (TypeInfo $type)
     {
         List ($type) list;
         Node ($type) *node;

         this (List ($type) list)
         {
             this.list = list;
             node = this.first;
         }

         bit next (out $type value)
         {
             synchronize (list)
             {
                 if (!node) return false;
                 value = node.value;
                 node = node.next;
                 return true;
             }
         }

         bit next (out $type *value)
         {
             synchronize (list)
             {
                 if (!node) return false;
                 value = &node.value;
                 node = node.next;
                 return true;
             }
         }

         bit next (out Node ($type) *value)
         {
             synchronize (list)
             {
                 if (!node) return false;
                 value = node;
                 node = node.next;
                 return true;
             }
         }
     }

Plus many other methods.
Jul 21 2002