Thread overview | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
September 20, 2019 Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
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. |
September 20, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | 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 |
September 20, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | 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);
}
```
|
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | 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() |
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | 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. |
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to ag0aep6g | 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.
|
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | 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);
---
|
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | 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 |
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Alex | 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. |
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | 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. |
Copyright © 1999-2021 by the D Language Foundation