Looking for a Simple Doubly Linked List Implementation

Ron Tarrant rontarrant at gmail.com
Sat Sep 21 08:34:09 UTC 2019

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;
	void append()
		string labelText = "Tab " ~ lastUniqueID.to!string();
		Tab* current;
		if(_head is null)
			_head = new Tab(lastUniqueID, labelText);
			current = &_head;
				current = current.getNext();

			Tab tab = new Tab(lastUniqueID, labelText);
	} // append()

	Tab* getHead()
	} // getHead()
} // class TabList

class Tab
	int _tabID;
	string _label;
	Tab* _prev = null, _next = null;
	this(int uniqueID, string labelText)
		_tabID = uniqueID;
		_label = labelText;
	} // this()
	void destroy(int id)
		if(_tabID is id)
	} // destroy()

	Tab* getNext()
	} // getNext()
	Tab* getPrev()
	} // getPrev()
	int getTabID()
	} // 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++)
	Tab* tab = tabList.getHead();
} // main()

More information about the Digitalmars-d-learn mailing list