• Armando (38/38) Mar 19 2023 Say I have a DList. I am looking for a vanilla way to
• Armando (40/40) Mar 19 2023 ok there is the issue of not knowing how to traverse the list
• Bastiaan Veelo (48/52) Mar 25 2023 This is one way to do that:
• Armando (24/24) Mar 27 2023 Wonderful, that works like a treat, thank you so much! For those
• Gary Chike (2/4) Mar 27 2023 Very cool! Thanks for asking and sharing! :)

Armando <armando.sano gmail.com> writes:

Say I have a DList. I am looking for a vanilla way to 
insert/remove elements in place while traversing that list.

```d
import std.container : DList;

struct myType{
    int id;
    // [...] other stuff
}

auto list = DList!myType();

// [...] populate list with elements
```

To remove the element with id=3 I can do:
```d
list.linearRemove(list[].find!(a => a.id==3).take(1));
```
but according to [this 
post](https://forum.dlang.org/post/mailman.3110.1356864469.5162.digitalm
rs-d puremagic.com) linearRemove might be less efficient than remove and remove
can't be used. Also in the example above, finding the needle is easy but my
case would involve more complicated scenarios that I am relunctant to bury into
find's predicate.

I would like to do something like traversing a DList, operating 
on the current element, and potentially removing that element or 
inserting a new one before/after it - an easy operation if you 
code a DList yourself. Maybe I missed something?

```d
// Traverse and operate on current element
foreach(element; list)
{
     // [...] do something long and complicated with m, throw a 
random number rand

     if(rand < 0.5)
         list.removeInPlace(); // remove 'element'
     else
         list.insertInPlace(myType(...)); // insert a new element 
"here" (before/after 'element')
}
```

Any way to achieve this simply with D? E.g. is there a way to 
extract the 'reading head' of a list being traversed and to use 
that head as a range into the remove, insertAfter, insertBefore 
functions?

Armando <armando.sano gmail.com> writes:

ok there is the issue of not knowing how to traverse the list 
after removing the current element (=> the one that came after of 
course). But how about even just keeping a pointer (range) to 
'element' that can be used after the list has been traversed in 
full to use in remove / insertAfter?

I think I can achieve this with associative arrays (below) but it 
seems overkill to use an associative effectively as a DList?

```d
struct myType{
     int id;
     int prev, next; // id of prev and next
     // [...] other stuff

     this(int id_, int prev_, int next_)
     {
         //[...]
     }
}

myType[int] list; // key = id

int[] to_remove;
myType[] to_add;

foreach(elem; list)
{
     // [...] do something long and complicated with elem, throw a 
random number rand

     if(rand < 0.5)
         to_remove ~= elem.id; // flag for removal
     else
         to_add ~= myType(some_new_id, elem.id, elem.next); // add 
new elem after current
}

foreach(elem; to_add)
     list[elem.id] = elem;

foreach(id; to_remove)
{
     // reconnect: prev's next to next, and next's prev to prev
     list[list[id].prev].next = list[id].next;
     list[list[id].next].prev = list[id].prev;
     list.remove(id);
}

```

Bastiaan Veelo <Bastiaan Veelo.net> writes:

On Sunday, 19 March 2023 at 13:15:58 UTC, Armando wrote:
 I would like to do something like traversing a DList, operating 
 on the current element, and potentially removing that element 
 or inserting a new one before/after it - an easy operation if 
 you code a DList yourself. Maybe I missed something?

This is one way to do that:
```d
import std;

struct MyType
{
     int id;
     // [...] other stuff
}

void main()
{
     auto list = DList!MyType();

     // Fill the list.
     foreach (i; 0 .. 10)
         list.insertBack(MyType(i));

     // Traverse the list, conditionally remove one element.
     for (auto range = list[]; !range.empty;)
         if (range.front.id == 3)
             list.popFirstOf(range);
         else
             range.popFront();

     // Traverse the list, conditionally insert one element.
     for (auto range = list[]; !range.empty;)
     {
         if (range.front.id == 6)
             list.insertBefore(range, MyType(66));
         range.popFront();
     }

     // Print modified list.
     foreach (e; list)
         writeln(e);

}
```

Output:
```
MyType(0)
MyType(1)
MyType(2)
MyType(4)
MyType(5)
MyType(66)
MyType(6)
MyType(7)
MyType(8)
MyType(9)
```

https://run.dlang.io/is/kk80FD

-- Bastiaan.

Armando <armando.sano gmail.com> writes:

Wonderful, that works like a treat, thank you so much! For those 
who wonder, inserting after works too:
```d
   for (auto range = list[]; !range.empty;)
     {
         if (range.back.id == 8)
             list.insertAfter(range, MyType(88));
         range.popBack();
     }

```
which will give
```
MyType(0)
MyType(1)
MyType(2)
MyType(4)
MyType(5)
MyType(66)
MyType(6)
MyType(7)
MyType(8)
MyType(88)
MyType(9)
```

Gary Chike <chikega gmail.com> writes:

On Monday, 27 March 2023 at 15:05:16 UTC, Armando wrote:
 Wonderful, that works like a treat, thank you so much! For 
 those who wonder, inserting after works too:

Very cool! Thanks for asking and sharing! :)