Re: Looking for a Simple Doubly Linked List Implementation
On Thursday, 29 October 2020 at 22:02:52 UTC, Paul Backus wrote: I'm pretty sure the post you replied to is spam. Yes, when I read the post again it is kind of hollow.
Re: Looking for a Simple Doubly Linked List Implementation
On Thursday, 29 October 2020 at 18:10:28 UTC, IGotD- wrote: Is this what you are looking for? https://dlang.org/phobos/std_container_dlist.html I'm pretty sure the post you replied to is spam.
Re: Looking for a Simple Doubly Linked List Implementation
On Thursday, 29 October 2020 at 18:06:55 UTC, xpaceeight wrote:
https://forum.dlang.org/post/bpixuevxzzltiybdr...@forum.dlang.org
It contains the data and a pointer to the next and previous
linked list node. This is given as follows. struct Node { int
data; struct Node *prev; struct Node *next; }; The function
insert() inserts the data into the beginning of the doubly
linked list. https://jiofilocalhtml.run https://forpc.onl
Is this what you are looking for?
https://dlang.org/phobos/std_container_dlist.html
Re: Looking for a Simple Doubly Linked List Implementation
On Tuesday, 28 January 2020 at 20:20:25 UTC, Barry allen wrote:
your linked list seems very complex https://get-shareit.com
https://get-vidmateapk.com
/* Node of a doubly linked list */
struct Node {
int data;
struct Node* next; // Pointer to next node in DLL
struct Node* prev; // Pointer to previous node in DLL
};
Re: Looking for a Simple Doubly Linked List Implementation
your linked list seems very complex
Re: Looking for a Simple Doubly Linked List Implementation
On Saturday, 28 September 2019 at 16:21:10 UTC, snow jhon wrote: On Saturday, 21 September 2019 at 18:52:23 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. 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). https://tutuapp.uno/ , https://9apps.ooo/ , https://showbox.kim/
Re: Looking for a Simple Doubly Linked List Implementation
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).
Re: Looking for a Simple Doubly Linked List Implementation
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. :)
Re: Looking for a Simple Doubly Linked List Implementation
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
Re: Looking for a Simple Doubly Linked List Implementation
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.
Re: Looking for a Simple Doubly Linked List Implementation
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
Re: Looking for a Simple Doubly Linked List Implementation
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("--");
}
Re: Looking for a Simple Doubly Linked List Implementation
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");
}
Re: Looking for a Simple Doubly Linked List Implementation
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.
Re: Looking for a Simple Doubly Linked List Implementation
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.
Re: Looking for a Simple Doubly Linked List Implementation
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
Re: Looking for a Simple Doubly Linked List Implementation
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); ---
Re: Looking for a Simple Doubly Linked List Implementation
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 (``) 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.
Re: Looking for a Simple Doubly Linked List Implementation
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
(``) and dereferendces (`*bar`) you have.
Re: Looking for a Simple Doubly Linked List Implementation
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();
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()
Re: Looking for a Simple Doubly Linked List Implementation
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);
}
```
Re: Looking for a Simple Doubly Linked List Implementation
On Fri, Sep 20, 2019 at 08:26:03PM +, 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
