www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Length of an SLIst ?

reply "Chris Pons" <cmpons gmail.com> writes:
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?
Apr 02 2012
parent reply Justin Whear <justin economicmodeling.com> writes:
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.
Apr 02 2012
next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
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);
}
Apr 02 2012
prev sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
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.
Apr 02 2012
next sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Apr 02 2012
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Apr 02 2012
next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
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. :)
Apr 02 2012
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Apr 02 2012
prev sibling parent Justin Whear <justin economicmodeling.com> writes:
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.
Apr 02 2012