Thread overview
Length of an SLIst ?
Apr 02, 2012
Chris Pons
Apr 02, 2012
Justin Whear
Apr 02, 2012
Andrej Mitrovic
Apr 02, 2012
Andrej Mitrovic
Apr 02, 2012
Ali Çehreli
Apr 02, 2012
Andrej Mitrovic
Apr 02, 2012
bearophile
Apr 02, 2012
Justin Whear
April 02, 2012
I'm trying to find the length of a Slist. I've tried using the built in .length function but it generates this error: "Error: no property 'length' for type 'SList!(Node)'". Are there any other built in ways to find the length?
April 02, 2012
On Mon, 02 Apr 2012 22:42:23 +0200, Chris Pons wrote:

> I'm trying to find the length of a Slist. I've tried using the built in .length function but it generates this error: "Error: no property 'length' for type 'SList!(Node)'". Are there any other built in ways to find the length?

Classic singly-linked lists must be iterated to determine length, so use std.range.walkLength on it.
April 02, 2012
On 4/2/12, Justin Whear <justin@economicmodeling.com> wrote:
> Classic singly-linked lists must be iterated to determine length, so use std.range.walkLength on it.

Specifically call it on its range. You can get a range by slicing the slist, e.g.:

import std.range;
import std.container;

void main()
{
    auto s = SList!int(1, 2, 5, 10);
    assert(walkLength(s[]) == 4);
}
April 02, 2012
On 4/2/12, Justin Whear <justin@economicmodeling.com> wrote:
> Classic singly-linked lists must be iterated to determine length

I'm no algorithms buff, but I don't understand the benefit of not storing the length in the SList. What does it cost to maintain an extra variable? It's a single increment/decrement on each add/remove and a little bit of memory to store the count.
April 02, 2012
On 04/02/2012 02:10 PM, Andrej Mitrovic wrote:
> On 4/2/12, Justin Whear<justin@economicmodeling.com>  wrote:
>> Classic singly-linked lists must be iterated to determine length
>
> I'm no algorithms buff, but I don't understand the benefit of not
> storing the length in the SList. What does it cost to maintain an
> extra variable? It's a single increment/decrement on each add/remove
> and a little bit of memory to store the count.

Length is not a property of singly-linked lists partly because they are supposed to be very light weight data structures. Imagine a hash table with buckets based on singly-linked lists. The length property would not add any value there but would double the table size.

I remember Matt Austern's presentation on a C++ singly linked list implementation where he had explicitly mentioned that he had decided to not provide length for the same reason. (I vaguely remember that his implementation was for addition to the C++ library, perhaps only to support the hash table? I don't remember now.)

Ali

April 02, 2012
On Mon, 02 Apr 2012 17:10:40 -0400, Andrej Mitrovic <andrej.mitrovich@gmail.com> wrote:

> On 4/2/12, Justin Whear <justin@economicmodeling.com> wrote:
>> Classic singly-linked lists must be iterated to determine length
>
> I'm no algorithms buff, but I don't understand the benefit of not
> storing the length in the SList. What does it cost to maintain an
> extra variable? It's a single increment/decrement on each add/remove
> and a little bit of memory to store the count.

It all depends on how you model the data.  If the data is contained/owned by a single instance, then you can store the length inside that instance.  If it's not owned (i.e. sublists are also valid SLists) then you cannot do that.

In terms of tradeoffs, generally you have to choose between O(1) splicing (i.e. removing the tail elements of a list, or splicing in another list in the middle) and O(1) length.

-Steve
April 02, 2012
On Mon, 02 Apr 2012 23:10:40 +0200, Andrej Mitrovic wrote:

> On 4/2/12, Justin Whear <justin@economicmodeling.com> wrote:
>> Classic singly-linked lists must be iterated to determine length
> 
> I'm no algorithms buff, but I don't understand the benefit of not storing the length in the SList. What does it cost to maintain an extra variable? It's a single increment/decrement on each add/remove and a little bit of memory to store the count.

Generally a singly-linked list is not a single container object, but a chain of nodes. Each node knows only of the existence of the next node, so operations such as insertion and deletion require just snapping a new node into the chain and are constant-time. By contrast, random-access operations require walking the chain to find the requested node. In many respects, slists and arrays are opposites, with one's weakness being the other's strength.
April 02, 2012
On 4/2/12, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> (i.e. sublists are also valid SLists)

I haven't thought of that, good point. :)
April 02, 2012
Steven Schveighoffer:

> It all depends on how you model the data.  If the data is contained/owned by a single instance, then you can store the length inside that instance.  If it's not owned (i.e. sublists are also valid SLists) then you cannot do that.

Let me add something to your answer. With Dependent Types
(http://en.wikipedia.org/wiki/Dependent_types ) you are sometimes
able to use the list length, encoded in the types, despite at
run-time the lengths aren't stored in the run-time data structure
:-)

This is not always possible, and it generally requires a type
system more powerful than the D type system if you also want it
to be sufficiently handy to use.

Bye,
bearophile