Looking for a Simple Doubly Linked List Implementation

[Ron Tarrant]

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++)
	{
		writeln("building Tab #", i);
		tabList.append();
		writeln("------------------------------");
	}

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

```