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
next sibling 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
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 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 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

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
prev sibling next sibling parent "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
prev sibling next 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
prev sibling 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