digitalmars.D.learn - Length of an SLIst ?

• Chris Pons (4/4) Apr 02 2012 I'm trying to find the length of a Slist. I've tried using the
• Justin Whear (3/7) Apr 02 2012 Classic singly-linked lists must be iterated to determine length, so use...
• Andrej Mitrovic (10/12) Apr 02 2012 Specifically call it on its range. You can get a range by slicing the
• Andrej Mitrovic (5/6) Apr 02 2012 I'm no algorithms buff, but I don't understand the benefit of not
• =?UTF-8?B?QWxpIMOHZWhyZWxp?= (11/17) Apr 02 2012 Length is not a property of singly-linked lists partly because they are
• Steven Schveighoffer (10/16) Apr 02 2012 It all depends on how you model the data. If the data is contained/owne...
• Andrej Mitrovic (2/3) Apr 02 2012 I haven't thought of that, good point. :)
• bearophile (11/15) Apr 02 2012 Let me add something to your answer. With Dependent Types
• Justin Whear (8/15) Apr 02 2012 Generally a singly-linked list is not a single container object, but a
"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
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
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
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
=?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
"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
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
"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
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