Double link list

ag0aep6g anonymous at example.com
Sat Feb 24 14:22:54 UTC 2018


On 02/24/2018 11:26 AM, TheFlyingFiddle wrote:
> On Saturday, 24 February 2018 at 09:48:13 UTC, Joel wrote:
[...]
>> void popFront() { head = head.next;  if (head !is null) head.prev = 
>> null; }
>> void popBack() { tail = tail.prev; if (tail !is null) tail.next = null; }
> 
> Head and tail will point to the same nodes and you are setting the 
> head.prev to null. Which would make the tail.prev null when iterating it 
> backwards. Similarly if you started iterating it backwards and then 
> iterating it forward it would not work.

To expand on this:

The goal of this was apparently to have `popBack` stop before reaching 
nodes that have already been `popFront`ed. I.e., `retro` should respect 
the earlier `dropOne`.

To do that properly, you can look for `head is tail`. If `head is tail`, 
the range is at its last element. Doesn't matter if there is another 
`next` or `prev`. `popFront` and `popBack` can just declare the range as 
empty then, e.g. by setting `head = null; tail = null;`.

So:

----
void popFront()
{
     if (head is tail) { head = null; tail = null; }
     else head = head.next;
}
void popBack()
{
     if (head is tail) { head = null; tail = null; }
     else tail = tail.prev;
}
----

Generally, don't change the data's structure in a range. In a range over 
a linked list, don't touch the links.

Also, the `List` here functions both as a container (adding/removing 
links) and as a range (traversing the links). Separating the two into 
different types might make it easier to see what a method should be 
allowed to do.


More information about the Digitalmars-d-learn mailing list