«

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.

>>>>> "c" == cartercc <> writes:

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

--
Uri Guttman ------ -------- http://www.sysarch.com --
----- Perl Code Review , Architecture, Development, Training, Support ------
--------- Free Perl Training --- http://perlhunter.com/college.html ---------
--------- Gourmet Hot Cocoa Mix ---- http://bestfriendscocoa.com ---------

cartercc <> wrote:
> 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.

cartercc <> wrote:
>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

Quoth 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} };

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

--
I have two words that are going to make all your troubles go away.
"Miniature". "Golf".
[]

cartercc <> wrote:
> 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
--
\ Jens Thoms Toerring ___
\__________________________ http://toerring.de

Jürgen Exner <> wrote:
>
> >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.

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.

cartercc <> writes:

> 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.

--
Joost Diepenmaat | blog: http://joost.zeekat.nl/ | work: http://zeekat.nl/

wrote:
>Jürgen Exner <> wrote:
>>
>> >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.
>
>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

Quoth :
> Jürgen Exner <> wrote:
> >
> > >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.
>
> 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

--
Many users now operate their own computers day in and day out on various
applications without ever writing a program. Indeed, many of these users
cannot write new programs for their machines...
-- F.P. Brooks, 'No Silver Bullet', 1987 []