C linked lists in Perl

[cartercc]

I guess like almost everybody, I like to discuss (argue) the merits of
different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.
him - Therefore, C is better than Perl because it has linked lists.
me - But Perl has other data structures that are easier to use than
linked lists.
him - So what? Perl still doesn't have linked lists.

I've never studied linked lists and certainly never coded one (in C or
anything else) but it aroused my curiosity. So after searching on
c.l.p.m. and online, I decided to see if I couldn't do a linked list
in Perl. My first thought is to do something like this:

%linked_list{$key} = { prev => $linked_list{$prev_key}{prev},
value => $value,
next => $linked_list{$next_key}
{next} };

I know that most people will think I'm an absolute moron for thinking
about this (and they likely would be right), but CAN you do a linked
list in Perl (never mind that you would never want to), and if so, how
would you go about it?

My motive is to say to my C friend, "Nya, nya, nya."

Thanks, CC.

 

[Uri Guttman]

c> I guess like almost everybody, I like to discuss (argue) the merits of
c> different technologies. In my world, the big two are Java and
c> ColdFusion. Recently, we had someone with a background in embedded
c> systems who has been advocating C. The conversation goes something
c> like this:

c> him - Does Perl have linked lists?
c> me - No.
c> him - Therefore, C is better than Perl because it has linked lists.
c> me - But Perl has other data structures that are easier to use than
c> linked lists.
c> him - So what? Perl still doesn't have linked lists.


your cow-orker is an idiot. and i say that from 20 years of deep c
experience (and more with assemblers and other langs) and 15 years of
perl. he is a total idiot. linked lists are NOT in c. in fact they
aren't in ANY language. linked lists are a general data structure built
upon various language constructs. you can make them from a single large
allocated array (use indexes for links and manage your own ram) or from
malloced buffers and hard pointers as in c, or in perl with references
(which are better and safer than pointers).

c> I've never studied linked lists and certainly never coded one (in C or
c> anything else) but it aroused my curiosity. So after searching on
c> c.l.p.m. and online, I decided to see if I couldn't do a linked list
c> in Perl. My first thought is to do something like this:

c> %linked_list{$key} = { prev => $linked_list{$prev_key}{prev},
c> value => $value,
c> next => $linked_list{$next_key}
c> {next} };

that is one way. i mentioned the large array with indexes and that is
another (i effectively did that for a large data tree in perl4 which
didn't have references).

c> My motive is to say to my C friend, "Nya, nya, nya."

and give him the finger from me. he is nuts if he keeps making that
claim. as i said above no lang HAS linked lists and ALL langs can build
them if they have even basic large array support.

uri

 

[xhoster]

I guess like almost everybody, I like to discuss (argue) the merits of
different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.
him - Therefore, C is better than Perl because it has linked lists.

Unless this is a huge gap in my C knowledge, which is entirely possible,
C doesn't have linked lists. C has pointers, which can be used to
implement linked lists. Perl has references, which can be used to
implement linked lists.

me - But Perl has other data structures that are easier to use than
linked lists.
him - So what? Perl still doesn't have linked lists.

You know what they say about arguing with a pig?

I've never studied linked lists and certainly never coded one (in C or
anything else) but it aroused my curiosity. So after searching on
c.l.p.m. and online, I decided to see if I couldn't do a linked list
in Perl. My first thought is to do something like this:

see perldoc -q linked for some ideas.

%linked_list{$key} = { prev => $linked_list{$prev_key}{prev},
value => $value,
next => $linked_list{$next_key}
{next} };

What is this supposed to do? (Once the %linked_list{ syntax error is
fixed). That is, what is the state of the linked_list supposed to be just
before and just after this code executes? It seems like node $key is going
to point to previous and next, but previous and next don't point back to
it. It is hard to see how that is correct.

I know that most people will think I'm an absolute moron for thinking
about this (and they likely would be right), but CAN you do a linked
list in Perl (never mind that you would never want to), and if so, how
would you go about it?

How I would go about would depend on why I wanted to do it, which I
wouldn't. You could just translate C code to perl, making the syntax
changes needed to change structs to hashes. It would be horrible memory
inefficient, because a lot of small hashes have too much overhead. So you
could use parallel hashes %value, %next, and (if doubly-linked) %previous.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.

 

[Jürgen Exner]

I guess like almost everybody, I like to discuss (argue) the merits of
different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.
him - Therefore, C is better than Perl because it has linked lists.

Mr. Him is mistaken: C does not have linked lists. It may have
primitives which allow a programmer to create a data structure that
behaves like a linked list. But there is no data type "linked list" in
C.

me - But Perl has other data structures that are easier to use than
linked lists.
him - So what? Perl still doesn't have linked lists.

But Perl has primitives which allow a programmer to create a data
structure that behaves like a linked list.

in Perl. My first thought is to do something like this:

%linked_list{$key} = { prev => $linked_list{$prev_key}{prev},
value => $value,
next => $linked_list{$next_key}
{next} };

I suppose that may work somehow.

But why not just use references where in C you would use pointers? Then
a single element would have a reference to the previous and the next
element plus a reference to the data section of this element.

I know that most people will think I'm an absolute moron for thinking
about this (and they likely would be right), but CAN you do a linked
list in Perl (never mind that you would never want to), and if so, how

Why wouldn't you want to? It's a totally valid request and if the nature
of a problem involves a sequential data structure with frequent add and
remove operations then a linked list should be much faster than doing
those operations on a large array.

would you go about it?

Just use Perl references instead of C pointers. The rest is virtually
identical excpet that you as a programmer don't have to worry about
memory management as in C. perl takes care of that for you.

jue

 

[Ben Morrow]

I guess like almost everybody, I like to discuss (argue) the merits of
different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.
him - Therefore, C is better than Perl because it has linked lists.
me - But Perl has other data structures that are easier to use than
linked lists.
him - So what? Perl still doesn't have linked lists.

I've never studied linked lists and certainly never coded one (in C or
anything else) but it aroused my curiosity. So after searching on
c.l.p.m. and online, I decided to see if I couldn't do a linked list
in Perl. My first thought is to do something like this:

%linked_list{$key} = { prev => $linked_list{$prev_key}{prev},
value => $value,
next => $linked_list{$next_key}
{next} };

That isn't even valid Perl... more importantly, I don't really
understand what you are trying to do here. A hash full of

{ prev => KEY, next => KEY, value => VALUE }

structures would be one way to do this (using the keys of your master
hash as a substitute for C pointers), but Perl already has a
pointer-substitute: references. The advantage of using references to
otherwise-unreferenced data structures is that when you drop the ref
they will be freed automatically. With your scheme you'd have to
manually delete the entry from the hash.

I know that most people will think I'm an absolute moron for thinking
about this (and they likely would be right), but CAN you do a linked
list in Perl (never mind that you would never want to), and if so, how
would you go about it?

The simplest implementation of a singly-linked list (as such) in Perl
would be something like (completely untested)

package LinkedList;

sub new { return bless [$_[1], undef], $_[0] }

sub get { return $_[0][0] }

sub set { $_[0][0] = $_[1] }

sub next { return $_[0][1] }

sub insert {
my ($self, $value) = @_;
my $next = $self->next;
$self->[1] = bless [$value, $next], ref $self;
}

sub remove_next {
my ($self) = @_;
$self->[1] = $self->next->next;
}

which you could use like

my $ll = LinkedList->new(1);

$ll->insert(2);
$ll->insert(3);
$ll->remove_next;
$ll->insert(4);
$ll->set(5);

$\ = "\n";

# notice how a C-ish structure lends itself to C-ish for loops
for (my $lp = $ll; $lp->next; $lp = $lp->next) {
print $lp->get;
}

which would print

5
4
2

Extending this to a doubly-linked list is trivial for anyone who's ever
written C . Of course, the most common use of linked lists in C is to
compensate for the fact C arrays don't auto-extend; for these cases, a
Perl array is much more useful, and much faster. However, the
generalisations of linked lists (trees and such, and more general
iterators) are very much useful, and used, in Perl.

Ben

 

[Jens Thoms Toerring]

I guess like almost everybody, I like to discuss (argue) the merits of
different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.
him - Therefore, C is better than Perl because it has linked lists.
me - But Perl has other data structures that are easier to use than
linked lists.
him - So what? Perl still doesn't have linked lists.

As I see it it's actually the other way round. C doesn't
"have" linked lists, i.e. there aren't any built-in fea-
tures in the C language especially made for linked lists.
On the other hand in Perl normal arrays can do what makes
linked lists in C so attractive: you can remove and insert
elements at arbitrary places. So, if your collegue says
that C "has" linked lists then you could very well argue
that that's not true and instead Perl "has" linked lists,
just going by a different name, arrays.

In Perl, you don't have to do any book-keeping for getting
the pointers pointing into the right places. And you don't
have to write any special functions for insertion, deleting,
appending etc. Everything can be done with the functions for
dealing with arrays (push/pop/shift/unshift/splice etc.) In-
stead of explicitely iterating over a linked list you can
use map and grep to write things in a single line of code
for which you would need dozends of lines in C with a linked
list. Actually, you mostly need linked lists in C because
those functionalities aren't available.

But if he insists on what he calls linked lists even then
he isn't right. You can create data structures that are
exactly like traditional linked lists in Perl as easily
as you can do it in C. If you do in C

struct node {
Payload_T data
struct node * next;
};

and then create objects of this type ('strcut node') you can
do in Perl exactly the same

my %elem = ( payload => $date,
next => \%some_other_elem );

In C you then would e.g. iterate over the linked list with

for ( l = &list_head; l; l = l->next )
/* do something here for each elements playload l->data */ ;

while in Perl you could do it with

for ( my $l = \%list_head; $l; $l = $l->{ next } )
# do something here for each elements payload $l->{ payload }
;

Not too much of a difference, is there?

See also 'perldoc perlfaq4' and look for "How do I handle
linked lists?".

Being more a C than a Perl programmer I just can say that in C
I use linked lists all of the time. But in nearly ten years of
dabbling with Perl from time to time I never ever had to resort
to using a traditional kind of linked list...

Regards, Jens

 

[xhoster]

Why wouldn't you want to? It's a totally valid request and if the nature
of a problem involves a sequential data structure with frequent add and
remove operations then a linked list should be much faster than doing
those operations on a large array.

Maybe, but I'm having a hard time thinking up a real problem that would
benefit in this way. As long as the add and remove operations are happing
at or near the ends of the list, you would be hard pressed to implement
linked lists in Perl that are faster than perl's splice on a large array.
If you are doing a bunch of adds and removes from the middle of the list,
then splicing a big array would be more problematic. But with linked
lists, getting to the middle is usually a performance problem in the first
place.

Maybe something where you have two super-imposed data structures. Like a
cache where you can instantly jump to any node via hash-key, but then
move that node in a LRU linked-list that threads the nodes.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.

 

[Joost Diepenmaat]

I guess like almost everybody, I like to discuss (argue) the merits of
different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.

Perl does have linked lists at least as much as C does.

my $ll = [ 'bla', [ 'blie', [ 'bloe' ]]];

etc.

But expect perl's garbage collector to get in your face if you create
giant linked lists. Not that you'd want to do that, anyway.

him - Therefore, C is better than Perl because it has linked lists.
me - But Perl has other data structures that are easier to use than
linked lists.

As I said, C doesn't have linked lists either.

him - So what? Perl still doesn't have linked lists.

I've never studied linked lists and certainly never coded one (in C or
anything else) but it aroused my curiosity.

Get a copy of "practical common lisp", or browse the book for free
online at http://gigamonkeys.com/book/

It's not about perl, but it *will* show you some interesting uses of
linked lists and teach you the basics of lisp, so good things can be
expected.

 

[Jürgen Exner]

Maybe, but I'm having a hard time thinking up a real problem that would
benefit in this way.

Me too

As long as the add and remove operations are happing
at or near the ends of the list, you would be hard pressed to implement
linked lists in Perl that are faster than perl's splice on a large array.
If you are doing a bunch of adds and removes from the middle of the list,
then splicing a big array would be more problematic. But with linked
lists, getting to the middle is usually a performance problem in the first
place.

Unless the linked list supports a concept of "current element", i.e. a
current location that could point anywhere in that list. Still, I am
hard pressed to find a real-world application for such data structure.

jue

 

[Ben Morrow]

Quoth (e-mail address removed):

Maybe, but I'm having a hard time thinking up a real problem that would
benefit in this way.

It's important to understand linked lists, though, and know how to
implement them, as they are a simple case of trees.

Ben

 

[Ben Morrow]

Perl does have linked lists at least as much as C does.

my $ll = [ 'bla', [ 'blie', [ 'bloe' ]]];

etc.

But expect perl's garbage collector to get in your face if you create
giant linked lists.

What do you mean by this? Are you referring to Perl's inability to
collect cyclical garbage (which is not a problem with a singly-linked
list like the one above, but definitely is a problem with a
doubly-linked)? This can be solved with appropriate application of
weakrefs, though it can be a little awkward to work out which refs to
weaken under some circumstances.

Otherwise: what problem does Perl have with large data structures?

Ben

 

[Jim Cochrane]

c> I guess like almost everybody, I like to discuss (argue) the merits of
c> different technologies. In my world, the big two are Java and
c> ColdFusion. Recently, we had someone with a background in embedded
c> systems who has been advocating C. The conversation goes something
c> like this:

c> him - Does Perl have linked lists?
c> me - No.
c> him - Therefore, C is better than Perl because it has linked lists.
c> me - But Perl has other data structures that are easier to use than
c> linked lists.
c> him - So what? Perl still doesn't have linked lists.


your cow-orker is an idiot. and i say that from 20 years of deep c
experience (and more with assemblers and other langs) and 15 years of
perl. he is a total idiot. linked lists are NOT in c. in fact they

As well, the standard C library does not implement linked lists.

aren't in ANY language. linked lists are a general data structure built
upon various language constructs. you can make them from a single large
allocated array (use indexes for links and manage your own ram) or from
malloced buffers and hard pointers as in c, or in perl with references
(which are better and safer than pointers).
...

--

 

[Peter Scott]

I guess like almost everybody, I like to discuss (argue) the merits of
different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.
him - Therefore, C is better than Perl because it has linked lists.
me - But Perl has other data structures that are easier to use than
linked lists.
him - So what? Perl still doesn't have linked lists.

That is the most asinine reasoning I have seen quoted on this group for at
least the last five minutes. Not only is it just as easy if not more so
to create linked lists in Perl as in C, but most of the reasons for
wanting to do so are rendered moot by Perl because of things that its
arrays can do that C's can't.

 

[cartercc]

Get a copy of "practical common lisp", or browse the book for free
online athttp://gigamonkeys.com/book/

I have PCL (Seibel), ACL (Graham), SL (Lamkins), Little Lisper, and
have a longstanding objective of learning and using Lisp, which
unfortunantly appears to be receding into the distant future.
Currently, I have fallen into lust with Erlang, which I have used to
complete a couple of small projects. I think that Erlang has a future,
while Lisp may only have a past.

It's not about perl, but it *will* show you some interesting uses of
linked lists and teach you the basics of lisp, so good things can be
expected.

For about ten years I have attempted to 'learn' one new language a
year. These have included XSLT and Scheme and Python. I am now
'learning' C as a reaction to my continuing conversations. IMO, you
can't be good in more than two or three at a time, and my present list
includes Perl, Java, Erlang, with PowerShell a distant fourth.

CC

 

[Charlton Wilbur]

cc> him - Does Perl have linked lists? me - No.

This is where you went wrong. The answer is not "no," but "perldoc -q
linked". Indeed, you'll see that Perl *does* have linked lists, but
that the built-in list type makes them pretty much useless.

Charlton

 

[Charlton Wilbur]

cc> For about ten years I have attempted to 'learn' one new language
cc> a year. These have included XSLT and Scheme and Python. I am now
cc> 'learning' C as a reaction to my continuing conversations.

If what you say in your initial post is true -- that you have never
coded a linked list, or seriously thought about doing so -- then you're
wasting a lot of time playing with the superficial syntax of various
languages. You need to sit down and study data structures and
algorithms, independent of any language. This will get you a lot
farther than learning whether yet another language uses := or = to set a
variable's value.

Charlton

 

[cartercc]

If what you say in your initial post is true -- that you have never
coded a linked list, or seriously thought about doing so -- then you're
wasting a lot of time playing with the superficial syntax of various
languages. You need to sit down and study data structures and
algorithms, independent of any language. This will get you a lot
farther than learning whether yet another language uses := or = to set a
variable's value.

Not that it makes any difference, but my undergraduate background was
English, I got a law degree and practiced law for 17 years before
changing professions, I have two MS (CS and SWE) but have never had an
undergraduate CS course, so I never had discrete math, algorithms,
data structures, etc. I agree fully with your recommendation. I have
done well in graduate courses because the instructors presuppose that
the students have the foundations so they focus on higher level
things, but I'll tell you from extensive personal experience that not
having the basics is a real handicap.

OTOH, I have found that technical people have a really narrow focus
and a very narrow range of knowledge, and I believe that on the whole
we are better served by a breadth of knowledge that allows us to make
connections. I find that I am able to make contributions to the
discussions that others cannot make because of my background.

CC

 

[Ted Zlatanov]

UG> as i said above no lang HAS linked lists

Java has them as part of the standard java.util libraries that come with
the standard JRE.

Lisp pretty much is all about linked lists, they are built into
everything.

I'm sure there are others.

Ted

 

[Uri Guttman]

UG> as i said above no lang HAS linked lists

TZ> Java has them as part of the standard java.util libraries that come with
TZ> the standard JRE.

i wouldn't call that part of the lang. but some would.

TZ> Lisp pretty much is all about linked lists, they are built into
TZ> everything.

sure but other than car and cdr (great names! and i know why) and dotted
pair, it doesn't have any builtin support for linked lists. you still
need to work at making them with primitives. i have made linked list
libs in c on more than one project and it is the same in lisp at that
level. the problem with built in linked lists is the data. in c you need
custom structures to hold a link and data or an opaque pointer to the
data off a generic link structure. in lisp you need to do the same
(actually make a tree) if you want more than a atom value at each link
node. that is why linked lists are taught as a data structure and
algorithm and hopefully independent of the language used. as i said
earlier, any large array can be used as the basis for a linked list
structure with no outside data. once you understand that algorithm and
such, all other versions are just variants.

and i want to kill the cow-orker who said perl has no linked lists. or
better, make him code in cobol for 10 years!

uri

 

[Joost Diepenmaat]

In lisp a list can be built from cons cells. It is not a data type in
lisp any more than in C.

Te question isn't whether linked lists is a datatype in lisp (it
isn't), the question is if the language has supports for linked lists
"build in" which it clearly does - as a simple example, the (list)
function builds a linked list. Similarily the (first) (second) etc
functions act on linked lists.

It's fairly trivial to build this kind of support in C or perl, but
you still have to do it yourself (or use some non-standard library).