Looking for a Simple Doubly Linked List Implementation

[Ron Tarrant]

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()