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.

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

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);
}
```

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

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.

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.

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

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

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.

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.