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