www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Looking for a Simple Doubly Linked List Implementation

reply Ron Tarrant <rontarrant gmail.com> writes:
Hi guys,

I've been banging my head on the screen with this one for the 
last week or so. For whatever reason, I'm having major problems 
understanding how to implement a doubly-linked list in D. I don't 
know if it's because I'm losing my ability to sort these things 
or if it's just that different from C.

If someone could please post a minimal example (if there's extra 
stuff in there, I'll get confused; I'm getting that old, dammit) 
I'd be ever so grateful.
Sep 20 2019
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Sep 20, 2019 at 08:26:03PM +0000, Ron Tarrant via Digitalmars-d-learn
wrote:

 Hi guys,
 
 I've been banging my head on the screen with this one for the last
 week or so. For whatever reason, I'm having major problems
 understanding how to implement a doubly-linked list in D. I don't know
 if it's because I'm losing my ability to sort these things or if it's
 just that different from C.
 
 If someone could please post a minimal example (if there's extra stuff
 in there, I'll get confused; I'm getting that old, dammit) I'd be ever
 so grateful.


Not a minimal example by any means, but Phobos *does* come with a
doubly-linked list implementation: std.container.dlist. Looking at the
code should help clarify whatever it is you're struggling with.


T

-- 
Elegant or ugly code as well as fine or rude sentences have something in
common: they don't depend on the language. -- Luca De Vitis
Sep 20 2019
parent reply Ron Tarrant <rontarrant gmail.com> writes:
On Friday, 20 September 2019 at 20:35:41 UTC, H. S. Teoh wrote:


 Not a minimal example by any means, but Phobos *does* come with 
 a doubly-linked list implementation: std.container.dlist.


Thanks, H.S. I did come across that in my search. Trouble is, 
with all the extra stuff in there, I'm having trouble separating 
what I need from what I don't.

On Friday, 20 September 2019 at 21:34:08 UTC, Dennis wrote:

 Below is a simple doubly linked list with Garbage Collected 
 memory.
 It's not performant or complete by any means, just a minimal 
 example in D like you wanted.


Thanks, Dennis. Not performant... It doesn't work? I was hoping 
for a complete, working example, but maybe this'll help.


 You probably also want methods for removing nodes or inserting 
 in the middle (else why don't you use an array?)


Yup. That's where I'm running into trouble.


 I think you can think of an implementation for those yourself 
 (or look them up, there should be plenty examples online).


I thought I could, too. And I thought there'd be lots of examples 
online, too. (Otherwise, I wouldn't have embarrassed myself in 
public like this.) But if there are, I can't find them... not in 
D. And it seems that D is just different enough from the other 
examples I'm finding so that I can't use them as a guide.

Here's a question for the room:

Does a doubly-linked list always have to be done with structs? 
Can it be classes instead? (Maybe that's why I can't get it to 
work, because I've been trying to make an OOP version?)

When I run the following code, it gets through creating the list 
head and the first node, then seems to get stuck in an infinite 
loop. Here's the code:

import std.stdio;
import std.conv;

class TabList
{
	Tab _head;
	int lastUniqueID = 0;
	string labelText;
	
	this()
	{
		append();
	}
	
	
	void append()
	{
		string labelText = "Tab " ~ lastUniqueID.to!string();
		Tab* current;
		
		if(_head is null)
		{
			_head = new Tab(lastUniqueID, labelText);
		}
		else
		{
			current = &_head;
			
			while(current.getNext())
			{
				current = current.getNext();
			}

			Tab tab = new Tab(lastUniqueID, labelText);
			current.setNext(&tab);
			current.setPrev(current);
		}
		
		lastUniqueID++;
		
	} // append()


	Tab* getHead()
	{
		return(&_head);
		
	} // getHead()
	
} // class TabList


class Tab
{
	private:
	int _tabID;
	string _label;
	Tab* _prev = null, _next = null;
	
	public:
	this(int uniqueID, string labelText)
	{
		_tabID = uniqueID;
		_label = labelText;
		
	} // this()
	
	
	void destroy(int id)
	{
		if(_tabID is id)
		{
			_prev.setNext(_next);
			_next.setPrev(_prev);
		}
		
	} // destroy()


	Tab* getNext()
	{
		return(_next);
		
	} // getNext()
	
	
	Tab* getPrev()
	{
		return(_prev);
		
	} // getPrev()
	
	
	int getTabID()
	{
		return(_tabID);
		
	} // getTabID()
	
	
	void setNext(Tab* tab)
	{
		_next = tab;
		
	} // setNext()
	

	void setPrev(Tab* tab)
	{
		_prev = tab;
		
	} // setPrev()	
	
} // class Tab


void main(string[] args)
{
	TabList tabList;
	
	tabList = new TabList();
	
	for(int i = 0; i < 7; i++)
	{
		tabList.append();
	}
	
	writeln();
	writeln();
	
	Tab* tab = tabList.getHead();
	
} // main()
Sep 21 2019
next sibling parent reply ag0aep6g <anonymous example.com> writes:
On 21.09.19 10:34, Ron Tarrant wrote:

 Here's a question for the room:
 
 Does a doubly-linked list always have to be done with structs? Can it be 
 classes instead? (Maybe that's why I can't get it to work, because I've 
 been trying to make an OOP version?)


It can be done with classes.


 When I run the following code, it gets through creating the list head 
 and the first node, then seems to get stuck in an infinite loop. Here's 
 the code:


[...]

 class Tab
 {


[...]

      Tab* _prev = null, _next = null;


[...]

      Tab* getNext()


[...]

      Tab* getPrev()


[...]

      void setNext(Tab* tab)


[...]

      void setPrev(Tab* tab)


[...]

 } // class Tab


Your mistake is that you're using pointers. `Tab` is a class. That means 
values of the type are already references. There is no need for `Tab*`. 
Just use `Tab` wherever you have `Tab*` now, and get rid of any addr-ofs 
(`&foo`) and dereferendces (`*bar`) you have.
Sep 21 2019
parent reply Ron Tarrant <rontarrant gmail.com> writes:
On Saturday, 21 September 2019 at 08:49:48 UTC, ag0aep6g wrote:

 On 21.09.19 10:34, Ron Tarrant wrote:

 Here's a question for the room:
 
 Does a doubly-linked list always have to be done with structs? 
 Can it be classes instead? (Maybe that's why I can't get it to 
 work, because I've been trying to make an OOP version?)


 It can be done with classes.


 When I run the following code, it gets through creating the 
 list head and the first node, then seems to get stuck in an 
 infinite loop. Here's the code:


 [...]

 class Tab
 {


 [...]

      Tab* _prev = null, _next = null;


 [...]

      Tab* getNext()


 [...]

      Tab* getPrev()


 [...]

      void setNext(Tab* tab)


 [...]

      void setPrev(Tab* tab)


 [...]

 } // class Tab


 Your mistake is that you're using pointers. `Tab` is a class. 
 That means values of the type are already references. There is 
 no need for `Tab*`. Just use `Tab` wherever you have `Tab*` 
 now, and get rid of any addr-ofs (`&foo`) and dereferendces 
 (`*bar`) you have.


Ah! Thanks, ag0aep6g. I was wondering about that when I was 
writing the code. (If I already knew this, I'd forgotten.) I did 
as you suggested, took out all '*' and '&' and it works perfectly.
Sep 21 2019
parent Tobias Pankrath <tobias pankrath.net> writes:
On Saturday, 21 September 2019 at 09:03:13 UTC, Ron Tarrant wrote:

 Ah! Thanks, ag0aep6g. I was wondering about that when I was 
 writing the code. (If I already knew this, I'd forgotten.) I 
 did as you suggested, took out all '*' and '&' and it works 
 perfectly.


Is this what you want?
---
current.setPrev(current);
---
Sep 21 2019
prev sibling parent reply Dennis <dkorpel gmail.com> writes:
On Saturday, 21 September 2019 at 08:34:09 UTC, Ron Tarrant wrote:

 Thanks, Dennis. Not performant... It doesn't work? I was hoping 
 for a complete, working example, but maybe this'll help.


Bad word choice (it appears it's debatable whether 'performant' 
even is a word), I meant it was a simple implementation not 
optimized for speed / memory efficiency.
Making it 'complete' is a bit hard since I can think of tens of 
methods and operator overloads you could use, but if I include 
them all it's no longer minimal and it just becomes 
std.container.dlist.


 Does a doubly-linked list always have to be done with structs? 
 Can it be classes instead?


My example originally included classes actually. It was mostly 
the same, except that Node!T* was just Node!T. The only problem 
was with const:

```
size_t length() const {
     size_t result = 0;
     for(auto a = head; a !is null; a = a.next) result++;
     return result;
}

```

Since I marked the method as const, `auto a = head` got the type 
const(Node!T) and `a = a.next` no longer compiled. With structs 
you can declare a const(Node!T)* (mutable pointer to const node), 
but I don't know if I can declare a mutable reference to a const 
class, so I switched to structs.
Sep 21 2019
next sibling parent reply Ron Tarrant <rontarrant gmail.com> writes:
On Saturday, 21 September 2019 at 18:52:23 UTC, Dennis wrote:

 On Saturday, 21 September 2019 at 08:34:09 UTC, Ron Tarrant 
 wrote:

 Thanks, Dennis. Not performant... It doesn't work? I was 
 hoping for a complete, working example, but maybe this'll help.


 Bad word choice (it appears it's debatable whether 'performant' 
 even is a word), I meant it was a simple implementation not 
 optimized for speed / memory efficiency.
 Making it 'complete' is a bit hard since I can think of tens of 
 methods and operator overloads you could use, but if I include 
 them all it's no longer minimal and it just becomes 
 std.container.dlist.


 Does a doubly-linked list always have to be done with structs? 
 Can it be classes instead?


 My example originally included classes actually. It was mostly 
 the same, except that Node!T* was just Node!T. The only problem 
 was with const:

 ```
 size_t length() const {
     size_t result = 0;
     for(auto a = head; a !is null; a = a.next) result++;
     return result;
 }

 ```

 Since I marked the method as const, `auto a = head` got the 
 type const(Node!T) and `a = a.next` no longer compiled. With 
 structs you can declare a const(Node!T)* (mutable pointer to 
 const node), but I don't know if I can declare a mutable 
 reference to a const class, so I switched to structs.


I have no idea, either.

But I did come up with something that works, so for anyone else 
looking for a full, working version (nothing fancy, mind you) 
here's my code with lots of 'proofs' dumped to the command line:

```
import std.stdio;
import std.conv;

class TabList
{
	private:
	Tab _head;
	int _lastUniqueID = 0;
	string labelText;
	
	this()
	{
		append();
	}
	
	
	void append()
	{
		string labelText = "Tab " ~ _lastUniqueID.to!string();
		Tab current;
		
		if(_head is null)
		{
			_head = new Tab(_lastUniqueID, labelText);
			_head.setPrev(null);
			_head.setNext(null);
		}
		else
		{
			current = _head;
writeln("before the while loop");
current.showThings();

			while(current.getNext() !is null)
			{
				writeln("in the while loop...");
				current.showThings();
				
				if(current.getPrev() !is null)
				{
					writeln("prev = ", current.getPrev().getTabID());
				}
				else
				{
					writeln("prev = null");
				}
				current = current.getNext();
			}
writeln("out of the while loop\n");
			Tab tab = new Tab(_lastUniqueID, labelText);
			current.setNext(tab);
			tab.setPrev(current);
		}
		
		_lastUniqueID++;
		
	} // append()


	Tab getHead()
	{
		return(_head);
		
	} // getHead()
	
	
	void removeTab(int uniqueID)
	{
		// get the head
		Tab current = _head, prev, next;
		
		// walk the list to find the Tab with the uniqueID
		while(current.getNext() !is null)
		{
			// if the uniqueID matches the head's ID
			if(current.getTabID() is uniqueID)
			{
				// destroy the Tab object
				current.destroy(uniqueID);
			}
			// else
			else
			{
				// go to the next Tab
				current = current.getNext();
			}
		}
		
	} // removeTab()
	
} // class TabList


class Tab
{
	private:
	int _tabID;
	string _label;
	Tab _prev = null, _next = null;
	
	public:
	this(int uniqueID, string labelText)
	{
		_tabID = uniqueID;
		_label = labelText;
		
	} // this()
	
	
	void showThings()
	{
		writeln("Tab = ", getTabID());
		
		if(getPrev() !is null)
		{
			writeln("Tab.prev = ", getPrev().getTabID());
		}
		else
		{
			writeln("Tab.prev is null");
		}
		
		if(getNext() !is null)
		{
			writeln("Tab.next = ", getNext().getTabID());
		}
		else
		{
			writeln("Tab.next = null");
		}
		
	} // showThings()
	

	void destroy(int id)
	{
		if(_tabID is id)
		{
			// destroy the TextView
			// destroy the Label
			_prev.setNext(_next);
			_next.setPrev(_prev);
		}
		
	} // destroy()


	Tab getNext()
	{
		return(_next);
		
	} // getNext()
	
	
	Tab getPrev()
	{
		return(_prev);
		
	} // getPrev()
	
	
	int getTabID()
	{
		return(_tabID);
		
	} // getTabID()
	
	
	void setNext(Tab tab)
	{
		_next = tab;
		
	} // setNext()
	

	void setPrev(Tab tab)
	{
		_prev = tab;
		
	} // setPrev()	
	
} // class Tab


void main(string[] args)
{
	TabList tabList;
	
	tabList = new TabList();
	
	for(int i = 0; i < 7; i++)
	{

		tabList.append();
		writeln("------------------------------");
	}

	writeln();
	
	Tab tab = tabList.getHead();
	
	while(tab !is null)
	{
		tab.showThings();
		tab = tab.getNext();
		writeln("-----");
	}
	
} // main()

```
Sep 21 2019
parent reply Ron Tarrant <rontarrant gmail.com> writes:
Sorry. I posted the wrong file. This is the one that works:

```
import std.stdio;
import std.conv;

class TabList
{
	private:
	Tab _head;
	int _lastUniqueID = 0;
	string labelText;
	
	this()
	{
		append();
	}
	
	
	void append()
	{
		string labelText = "Tab " ~ _lastUniqueID.to!string();
		Tab current;
		
		if(_head is null)
		{
			_head = new Tab(_lastUniqueID, labelText);
			_head.setPrev(null);
			_head.setNext(null);
		}
		else
		{
			current = _head;
//writeln("before the while loop");
//current.showThings();

			while(current.getNext() !is null)
			{
//				writeln("in the while loop...");
//				current.showThings();
				
//				if(current.getPrev() !is null)
//				{
//					writeln("prev = ", current.getPrev().getTabID());
//				}
//				else
//				{
//					writeln("prev = null");
//				}
				current = current.getNext();
			}
//writeln("out of the while loop\n");
			Tab tab = new Tab(_lastUniqueID, labelText);
			current.setNext(tab);
			tab.setPrev(current);
		}
		
		_lastUniqueID++;
		
	} // append()


	Tab getHead()
	{
		return(_head);
		
	} // getHead()
	
	
	void removeTab(int uniqueID)
	{
		// get the head
		Tab current = _head;

		// walk the list to find the Tab with the uniqueID
		while(current.getNext() !is null)
		{
			// if the uniqueID matches the head's ID
			if(current.getTabID() is uniqueID)
			{
				// destroy the Tab object
				current.destroy(uniqueID);
				break;
			}

			// go to the next Tab
			current = current.getNext();
		}
		

	} // removeTab()
	
} // class TabList


class Tab
{
	private:
	int _tabID;
	string _label;
	Tab _prev = null, _next = null;
	
	public:
	this(int uniqueID, string labelText)
	{
		_tabID = uniqueID;
		_label = labelText;
		
	} // this()
	
	
	void showThings()
	{
		writeln("Tab = ", getTabID());
		
		if(getPrev() !is null)
		{
			writeln("Tab.prev = ", getPrev().getTabID());
		}
		else
		{
			writeln("Tab.prev is null");
		}
		
		if(getNext() !is null)
		{
			writeln("Tab.next = ", getNext().getTabID());
		}
		else
		{
			writeln("Tab.next = null");
		}
		
	} // showThings()
	

	void destroy(int id)
	{
		if(_tabID is id)
		{
			// destroy the TextView
			// destroy the Label
			_prev.setNext(_next);
			_next.setPrev(_prev);
		}
		
	} // destroy()


	Tab getNext()
	{
		return(_next);
		
	} // getNext()
	
	
	Tab getPrev()
	{
		return(_prev);
		
	} // getPrev()
	
	
	int getTabID()
	{
		return(_tabID);
		
	} // getTabID()
	
	
	void setNext(Tab tab)
	{
		_next = tab;
		
	} // setNext()
	

	void setPrev(Tab tab)
	{
		_prev = tab;
		
	} // setPrev()	
	
} // class Tab


void main(string[] args)
{
	TabList tabList;
	
	tabList = new TabList();
	
	for(int i = 0; i < 7; i++)
	{

		tabList.append();
//		writeln("------------------------------");
	}

	writeln();
	
	Tab tab = tabList.getHead();
	
	while(tab !is null)
	{
		tab.showThings();
		tab = tab.getNext();
		writeln("-----");
	}
writeln("------------------------------");
	
	// delete one
	tabList.removeTab(3);

	tab = tabList.getHead();

	while(tab !is null)
	{
		tab.showThings();
		tab = tab.getNext();
		writeln("-----");
	}
	
} // main()

```
Sep 21 2019
parent reply Ron Tarrant <rontarrant gmail.com> writes:
Well, it turns out, I didn't need a linked list, doubly or 
otherwise. That's what happens when a person quits coffee for a 
week: complete brain chaos.

For a full week, I banged on this, trying to work out a scheme 
whereby I could track GTK Notebook tabs with a doubly-linked 
list, an array, and any other mechanism that came to mind. That 
was my caffeine-free week of getting absolutely nothing done. 
(Twice, I actually forgot my name.)

This morning, I had a coffee, realized I was not just on the 
wrong track, but in the wrong train station and within 45 
minutes, I had eight Notebook demos working perfectly.

Let this serve as a warning, no matter how much you may think you 
need to go off the caffeine, it's just not worth it.
Sep 23 2019
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 09/23/2019 01:45 PM, Ron Tarrant wrote:

 Well, it turns out, I didn't need a linked list, doubly or otherwise.


So, what was it then? Append to an array, sort it, and be happy? :)

Ali
Sep 23 2019
parent Ron Tarrant <rontarrant gmail.com> writes:
On Monday, 23 September 2019 at 22:40:41 UTC, Ali Çehreli wrote:


 So, what was it then? Append to an array, sort it, and be 
 happy? :)

 Ali


Hi, Ali,

It turns out that the GTK Notebook has its own built-in mechanism 
for tracking tabs. Two things got me going down the wrong road on 
this:

1) the fact that Notebook.appendPage() returns an ever-increasing 
index each time a page is added, and
2) trying to quit caffeine.

I chased my tail for a full week (seriously: a full week!) trying 
to come up with a way to track tabs. Then I got tired of doing 
face-plants on my desk, took up coffee again, and solved it in 
three hours.

The moral of the story is: don't quit coffee until you have 
nothing left to contribute to this world. :)
Sep 25 2019
prev sibling next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Saturday, September 21, 2019 12:52:23 PM MDT Dennis via Digitalmars-d-
learn wrote:

 Since I marked the method as const, `auto a = head` got the type
 const(Node!T) and `a = a.next` no longer compiled. With structs
 you can declare a const(Node!T)* (mutable pointer to const node),
 but I don't know if I can declare a mutable reference to a const
 class, so I switched to structs.


You have to use std.typecons.Rebindable if you want to have the equivalent
of const(T)* for class references, because the type system doesn't
distinguish between a class and a reference to a class. As it is, Rebindable
is pretty much a hack that's questionably legal per the type system (but
it's in Phobos, so I'm sure that it will continue to work). Ideally, there
would be a way to do it in the language, but the assumptions that the
compiler currently makes when dealing with classes makes that difficult.

In general though, if you're not going to use inheritance, then there isn't
much point in using a class instead of a struct unless you want to force it
to live on the heap (and that only really matters if you're dealing with
something that's publicly available for others to muck with, whereas nodes
in a linked list are normally private to the list, so it's easy to ensure
that they're only ever on the heap even if they're structs).

- Jonathan M Davis
Sep 21 2019
prev sibling parent snow jhon <sportsdz25 gmail.com> writes:
On Saturday, 21 September 2019 at 18:52:23 UTC, Dennis wrote:

 On Saturday, 21 September 2019 at 08:34:09 UTC, Ron Tarrant 
 wrote:

 Thanks, Dennis. Not performant... It doesn't work? I was 
 hoping for a complete, working example, but maybe this'll help.


 Bad word choice (it appears it's debatable whether 'performant' 
 even is a word), I meant it was a simple implementation not 
 optimized for speed / memory efficiency.
 Making it 'complete' is a bit hard since I can think of tens of 
 methods and operator overloads you could use, but if I include 
 them all it's no longer minimal and it just becomes 
 std.container.dlist.


 Does a doubly-linked list always have to be done with structs? 
 Can it be classes instead?


 My example originally included classes actually. It was mostly 
 the same, except that Node!T* was just Node!T. The only problem 
 was with const:

 ```
 size_t length() const {
     size_t result = 0;
     for(auto a = head; a !is null; a = a.next) result++;
     return result;
 }

 ```

 Since I marked the method as const, `auto a = head` got the 
 type const(Node!T) and `a = a.next` no longer compiled. With 
 structs you can declare a const(Node!T)* (mutable pointer to 
 const node), but I don't know if I can declare a mutable 
 reference to a const class, so I switched to structs.


Below is a simple doubly linked list with Garbage Collected 
memory.
It's not performant or complete by any means, just a minimal 
example in D like you wanted.
You probably also want methods for removing nodes or inserting in 
the middle (else why don't you use an array?), I think you can 
think of an implementation for those yourself (or look them up, 
there should be plenty examples online).
Sep 28 2019
prev sibling next sibling parent Dennis <dkorpel gmail.com> writes:
On Friday, 20 September 2019 at 20:26:03 UTC, Ron Tarrant wrote:

 If someone could please post a minimal example (if there's 
 extra stuff in there, I'll get confused; I'm getting that old, 
 dammit) I'd be ever so grateful.


Below is a simple doubly linked list with Garbage Collected 
memory.
It's not performant or complete by any means, just a minimal 
example in D like you wanted.
You probably also want methods for removing nodes or inserting in 
the middle (else why don't you use an array?), I think you can 
think of an implementation for those yourself (or look them up, 
there should be plenty examples online).

If not, just ask again.

```

struct Node(T) {
     private T value;
     private Node!T* next = null;
     private Node!T* previous = null;

     this(T value) {
         this.value = value;
     }
}

struct DoublyLinkedList(T) {
     Node!T* head = null;
     Node!T* tail = null;

     import std.range: isInputRange, ElementType;
     this(R)(R initialList) if (isInputRange!R && is(ElementType!R 
: T)) {
         foreach(elem; initialList) {
             addLast(elem);
         }
     }

     void addFirst(T value) {
         auto n = new Node!T(value);
         if (head !is null) {
             head.previous = n;
         } else {
             tail = n;
         }
         n.next = head;
         head = n;
     }

     void addLast(T value) {
         if (head is null) {
             addFirst(value);
         } else {
             auto n = new Node!T(value);
             tail.next = n;
             n.previous = tail;
             tail = n;
         }
     }

     size_t length() const {
         size_t result = 0;
         for(const(Node!T)* a = head; a !is null; a = a.next) 
result++;
         return result;
     }

     T opIndex(size_t pos) const {
         const(Node!T)* p = head;
         for(; p !is null && pos-- != 0; p = p.next) {}
         return p.value;
     }
}

unittest {
     auto a = DoublyLinkedList!int([10, 20, 30]);
     assert(a[2] == 30);
     assert(a.length == 3);
     a.addFirst(-10);
     a.addLast(100);
     assert(a[0] == -10);
     assert(a.tail.value == 100);
}
```
Sep 20 2019
prev sibling parent reply Alex <sascha.orlov gmail.com> writes:
On Friday, 20 September 2019 at 20:26:03 UTC, Ron Tarrant wrote:

 Hi guys,

 I've been banging my head on the screen with this one for the 
 last week or so. For whatever reason, I'm having major problems 
 understanding how to implement a doubly-linked list in D. I 
 don't know if it's because I'm losing my ability to sort these 
 things or if it's just that different from C.

 If someone could please post a minimal example (if there's 
 extra stuff in there, I'll get confused; I'm getting that old, 
 dammit) I'd be ever so grateful.


rosetta code is quite good for such problems

http://rosettacode.org/wiki/Doubly-linked_list/Definition#D
Sep 21 2019
parent Ron Tarrant <rontarrant gmail.com> writes:
Thanks for all the responses, y'all.

I got it figured out thanks to ag0aep6g pointing out something I 
forgot about the nature of class objects in D (Damn my failing 
memory). The results will show up on the gtkDcoding blog sometime 
in (I'm guessing) November as part of the the Notebook discussion 
series.
Sep 21 2019