September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dennis | 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() ``` |
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | Sorry. I posted the wrong file. This is the one that works: ``` 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; // 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); break; } // 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("-----"); } writeln("------------------------------"); // delete one tabList.removeTab(3); tab = tabList.getHead(); while(tab !is null) { tab.showThings(); tab = tab.getNext(); writeln("-----"); } } // main() ``` |
September 21, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dennis | On Saturday, September 21, 2019 12:52:23 PM MDT Dennis via Digitalmars-d- learn wrote:
> 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.
You have to use std.typecons.Rebindable if you want to have the equivalent of const(T)* for class references, because the type system doesn't distinguish between a class and a reference to a class. As it is, Rebindable is pretty much a hack that's questionably legal per the type system (but it's in Phobos, so I'm sure that it will continue to work). Ideally, there would be a way to do it in the language, but the assumptions that the compiler currently makes when dealing with classes makes that difficult.
In general though, if you're not going to use inheritance, then there isn't much point in using a class instead of a struct unless you want to force it to live on the heap (and that only really matters if you're dealing with something that's publicly available for others to muck with, whereas nodes in a linked list are normally private to the list, so it's easy to ensure that they're only ever on the heap even if they're structs).
- Jonathan M Davis
|
September 23, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | Well, it turns out, I didn't need a linked list, doubly or otherwise. That's what happens when a person quits coffee for a week: complete brain chaos. For a full week, I banged on this, trying to work out a scheme whereby I could track GTK Notebook tabs with a doubly-linked list, an array, and any other mechanism that came to mind. That was my caffeine-free week of getting absolutely nothing done. (Twice, I actually forgot my name.) This morning, I had a coffee, realized I was not just on the wrong track, but in the wrong train station and within 45 minutes, I had eight Notebook demos working perfectly. Let this serve as a warning, no matter how much you may think you need to go off the caffeine, it's just not worth it. |
September 23, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ron Tarrant | On 09/23/2019 01:45 PM, Ron Tarrant wrote: > Well, it turns out, I didn't need a linked list, doubly or otherwise. So, what was it then? Append to an array, sort it, and be happy? :) Ali |
September 25, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ali Çehreli | On Monday, 23 September 2019 at 22:40:41 UTC, Ali Çehreli wrote:
> So, what was it then? Append to an array, sort it, and be happy? :)
>
> Ali
Hi, Ali,
It turns out that the GTK Notebook has its own built-in mechanism for tracking tabs. Two things got me going down the wrong road on this:
1) the fact that Notebook.appendPage() returns an ever-increasing index each time a page is added, and
2) trying to quit caffeine.
I chased my tail for a full week (seriously: a full week!) trying to come up with a way to track tabs. Then I got tired of doing face-plants on my desk, took up coffee again, and solved it in three hours.
The moral of the story is: don't quit coffee until you have nothing left to contribute to this world. :)
|
September 28, 2019 Re: Looking for a Simple Doubly Linked List Implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dennis | 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.
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).
|
Copyright © 1999-2021 by the D Language Foundation