C linked lists in Perl

Discussion in 'Perl Misc' started by cartercc, Jul 16, 2008.

  1. cartercc

    cartercc Guest

    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.
    cartercc, Jul 16, 2008
    #1
    1. Advertising

  2. cartercc

    Uri Guttman Guest

    >>>>> "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 ---------
    Uri Guttman, Jul 16, 2008
    #2
    1. Advertising

  3. cartercc

    Guest

    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.
    , Jul 16, 2008
    #3
  4. 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
    Jürgen Exner, Jul 16, 2008
    #4
  5. cartercc

    Ben Morrow Guest

    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".
    []
    Ben Morrow, Jul 16, 2008
    #5
  6. 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
    Jens Thoms Toerring, Jul 16, 2008
    #6
  7. cartercc

    Guest

    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.
    , Jul 16, 2008
    #7
  8. 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/
    Joost Diepenmaat, Jul 16, 2008
    #8
  9. 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
    Jürgen Exner, Jul 17, 2008
    #9
  10. cartercc

    Ben Morrow Guest

    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 []
    Ben Morrow, Jul 17, 2008
    #10
  11. cartercc

    Ben Morrow Guest

    Quoth Joost Diepenmaat <>:
    >
    > 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

    --
    I have two words that are going to make all your troubles go away.
    "Miniature". "Golf".
    []
    Ben Morrow, Jul 17, 2008
    #11
  12. cartercc

    Jim Cochrane Guest

    On 2008-07-16, Uri Guttman <> wrote:
    >>>>>> "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


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



    --
    Jim Cochrane, Jul 17, 2008
    #12
  13. cartercc

    Peter Scott Guest

    On Wed, 16 Jul 2008 13:11:24 -0700, 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.


    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.

    --
    Peter Scott
    http://www.perlmedic.com/
    http://www.perldebugged.com/
    Peter Scott, Jul 17, 2008
    #13
  14. cartercc

    cartercc Guest

    On Jul 16, 6:58 pm, Joost Diepenmaat <>
    > 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
    cartercc, Jul 17, 2008
    #14
  15. >>>>> "cc" == cartercc <> writes:

    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
    Charlton Wilbur, Jul 17, 2008
    #15
  16. >>>>> "cc" == cartercc <> writes:

    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


    --
    Charlton Wilbur
    Charlton Wilbur, Jul 17, 2008
    #16
  17. cartercc

    cartercc Guest

    On Jul 17, 8:44 am, Charlton Wilbur <> wrote:
    > 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
    cartercc, Jul 17, 2008
    #17
  18. cartercc

    Ted Zlatanov Guest

    On Wed, 16 Jul 2008 20:43:27 GMT Uri Guttman <> wrote:

    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
    Ted Zlatanov, Jul 17, 2008
    #18
  19. cartercc

    Uri Guttman Guest

    >>>>> "TZ" == Ted Zlatanov <> writes:

    TZ> On Wed, 16 Jul 2008 20:43:27 GMT Uri Guttman <> wrote:
    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

    --
    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 ---------
    Uri Guttman, Jul 17, 2008
    #19
  20. smallpond <> writes:

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

    --
    Joost Diepenmaat | blog: http://joost.zeekat.nl/ | work: http://zeekat.nl/
    Joost Diepenmaat, Jul 17, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    478
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    464
    emerth
    Jul 10, 2003
  3. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    401
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  4. fool
    Replies:
    14
    Views:
    503
    Barry Schwarz
    Jul 3, 2006
  5. jawdoc
    Replies:
    9
    Views:
    750
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page