Linked list as a bidirectional range? I have some questions...

H. S. Teoh via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Mon Aug 11 11:19:11 PDT 2014


On Mon, Aug 11, 2014 at 05:51:11PM +0000, Gary Willoughby via Digitalmars-d-learn wrote:
> Just for a bit a fun i've implemented a simple doubly linked list and
> trying out some range based stuff. Whilst doing so i have some
> questions which you guys might be able to answer.
> 
> 1. In your opinion when accessing the elements of a linked list should
> they yield the data stored within the nodes or the entire nodes
> themselves?  Different languages do this differently. For example, C#
> yields nodes[1], Java yields data[2].
> 
> 2. Suppose when accessing my linked list, it yields data and not
> nodes, how do iterate in reverse? I don't want to add unnecessary
> methods or properties.
> 
> 3. How would you implement the 'save' method of a forward range in the
> context of a linked list? If my understanding is correct the 'saved'
> range is iterated and discard, so cannot use any references to the
> underlying range. This might also solve question 2.
[...]

IMO, it's a bad idea to conflate the container with the range over its
contents. If you make your linked list container the same thing as a
range over it, then iterating over the range will empty the container as
well, which generally isn't what you want.

It's much better to separate the container itself from ranges over the
container. This then allows you to have separate container methods that
return ranges of different types, for example:

	class LinkedList {
		... // implementation here

		auto byNode() {
			return ... /* range over nodes */
		}

		auto byData() {
			return ... /* range over data */
		}
	}

	LinkedList l = ...;
	foreach (node; l.byNode()) {
		// you get nodes here
	}
	foreach (data; l.byData()) {
		// you get data items here
	}

Which answers your original question: you can have it both ways. :-)

Unfortunately, built-in arrays are a bad example for this, because it
conflates the container (the slice) with the range. This tends to
mislead people into thinking it's OK to conflate the container with a
range over its contents. In general, you *don't* want to do this.
Unless you're trying to simulate built-in arrays.


T

-- 
Recently, our IT department hired a bug-fix engineer. He used to work for Volkswagen.


More information about the Digitalmars-d-learn mailing list