www.digitalmars.com         C & C++   DMDScript  

D - How to implement a linked list in D?

reply Friedrich Dominivud <Friedrich_member pathlink.com> writes:
I'm totally new to D so this may be a bit way over my head, but I know 
OO quite well and do think that I'm not too bad in C too. Now my question:

How do I implement a class Linked List?
I want it to have an item field and a next field which should probably be
Linked List again. 

I wrote this stuff which is so bad, that it does not even compile.

Could anyone give me a hand on how to achieve in D what I tries to explain?


what I want is something along this lines (Pseudo D)
class LinkedList
template Item (T){
T item;
LinkedList next;
... 



Is there a way to achieve that?

Or do I have to implement it in a more C-ish way (e.g with a struct?

Thanks for your time 

Friedrich
Jun 03 2003
next sibling parent reply "Sean L. Palmer" <palmer.sean verizon.net> writes:
try it like this:


template LinkedListTemplate(T)
{
    class LinkedList : T
    {
        LinkedList next;
    }
}

alias instance LinkedListTemplate(Foo).LinkedList FooLinkedList;


Unfortunately that way, it's not acceptable for Foo to be an alias for, say,
int or some other basic type.

You can still do it via inclusion instead of inheritance:

template LinkedListTemplate(T)
{
    class LinkedList
    {
        T item;
        LinkedList next;
    }
}

alias instance LinkedListTemplate(Foo).LinkedList FooLinkedList;

Sean

"Friedrich Dominivud" <Friedrich_member pathlink.com> wrote in message
news:bbif3a$14s5$1 digitaldaemon.com...

 I'm totally new to D so this may be a bit way over my head, but I know
 OO quite well and do think that I'm not too bad in C too. Now my question:

 How do I implement a class Linked List?
 I want it to have an item field and a next field which should probably be
 Linked List again.

 I wrote this stuff which is so bad, that it does not even compile.

 Could anyone give me a hand on how to achieve in D what I tries to


explain?

 what I want is something along this lines (Pseudo D)
 class LinkedList
 template Item (T){
 T item;
 LinkedList next;
 ...



 Is there a way to achieve that?

 Or do I have to implement it in a more C-ish way (e.g with a struct?

 Thanks for your time

 Friedrich
Jun 03 2003
next sibling parent reply Stephan Wienczny <wienczny web.de> writes:
Shouldn't we have a linked list template inside phobos?
I think phobos should get important standard containers like list, map 
(other types than char[]), stack etc.
What do you think about it?

Cu Stephan
Jun 03 2003
parent Friedrich <Friedrich_member pathlink.com> writes:
In article <bbinin$1d53$1 digitaldaemon.com>, Stephan Wienczny says...

Shouldn't we have a linked list template inside phobos?
I think phobos should get important standard containers like list, map 
(other types than char[]), stack etc.
What do you think about it?

Cu Stephan


Well as posted before I'm new to D, but have a good working knowledge in Eiffel
and developed quite a few libraries. I can assure you that writing good
libraries is hard work and time consuming. But yes I think having a good
standard library is  important. 


Regards
Friedrich
Jun 03 2003
prev sibling parent Friedrich Dominicus <Friedrich_member pathlink.com> writes:
Thanks, I'll try it the latter way. Which seems to be the "right" way.

Regards
Friedrich
Jun 03 2003
prev sibling parent Bill Cox <bill viasic.com> writes:
Hi, Friedrich.

Linked lists are the simplest of all data structures that most modern OO 
languages do poorly at.  In a Sather-like language, it is much simpler 
(please forgive the non-Sather syntax):

module LinkedList;

class Parent {
     Child *head;
}

class Child {
     Child *next;
}

To reuse this code in Sather takes an "include" statement like:

include LinkedList {
     Parent -> MyDocumentManager;
     Child -> MyDocument;
}

The guy who wrote the C++ STL said he uses the "max" function as a 
simple test of code reusability in a language.  That's a good one.  I 
also like the linked list.  Even in Eiffel, the implementation of linked 
lists is terrible.

Bill

Friedrich Dominivud wrote:

 I'm totally new to D so this may be a bit way over my head, but I know 
 OO quite well and do think that I'm not too bad in C too. Now my question:
 
 How do I implement a class Linked List?
 I want it to have an item field and a next field which should probably be
 Linked List again. 
 
 I wrote this stuff which is so bad, that it does not even compile.
 
 Could anyone give me a hand on how to achieve in D what I tries to explain?
 
 
 what I want is something along this lines (Pseudo D)
 class LinkedList
 template Item (T){
 T item;
 LinkedList next;
 ... 
 
 
 
 Is there a way to achieve that?
 
 Or do I have to implement it in a more C-ish way (e.g with a struct?
 
 Thanks for your time 
 
 Friedrich
Jun 09 2003