View mode: basic / threaded / horizontal-split · Log in · Help
April 02, 2012
Length of an SLIst ?
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
Re: Length of an SLIst ?
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
Re: Length of an SLIst ?
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
Re: Length of an SLIst ?
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
Re: Length of an SLIst ?
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
Re: Length of an SLIst ?
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
Re: Length of an SLIst ?
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
Re: Length of an SLIst ?
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
Re: Length of an SLIst ?
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
Top | Discussion index | About this forum | D home