Thread: Linked List Question

  1. #16
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Quote Originally Posted by iMalc
    Oh so, that's why it says "Liberally stupid" under your name! Makes perfect sense now.
    Does it? I'm glad you figured it out because I'm sure it would have been weird for you if you didn't. I'm sure it could be done, but can you name five of tasks that a linked list would be your best option to use to accomplish it as efficiently as possible?
    Sent from my iPadŽ

  2. #17
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    Quote Originally Posted by SlyMaelstrom
    Does it? I'm glad you figured it out because I'm sure it would have been weird for you if you didn't. I'm sure it could be done, but can you name five of tasks that a linked list would be your best option to use to accomplish it as efficiently as possible?
    dynamic memory allocation/deallocation and tracking. Any time you need a string of data, but need that string to be dynamic in not only size but dimension, the linked list is your choice. Imagine if you will the following possibility:

    You have some kind of sorting algorithm that has 5 possible outcomes, so you create an array of 5 spaces, but you don't know how many of each will go into each spot in the array. Let's make it simple and say you have 100 objects. Now, do you just create an array of [5][100] objects? no, that's a colossal waste of memory. Do you create an array of [5][80] hoping to cut down on memory, but taking a chance that there will be at most 80 of any one kind? no.

    You use a linked list. Your array looks like this: [5]

    Each index of the array is a pointer to a list. that list grows and shrinks dynamically. That way, when you fillin in the list, instead of keeping 500 memory blocks for 100 objects, you're keeping 100 memory blocks for 100 objects and their pointers. It's alot more efficient. Also, what if your machines's low on memory and can't find 500 adjacent memory locations?

    a linked list allows more dynamic memory management. Imagine creating a dynamic net without being able to dynamically change the amount of memory you've allocated...
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  3. #18
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Quote Originally Posted by major_small
    Any time you need a string of data, but need that string to be dynamic in not only size but dimension
    A std::vector of std::strings should handle this. There are probably better uses of containers than that, that I just simply don't know. I wasn't compare the use of an array to the use of a linked list, at all.

    I'm not say Linked Lists don't work. They exist for a reason. I'm just saying they don't work as well as some of the modern conveniences that C++ offers. I'm sure there are certain uses for Linked Lists today, but I'm sure the reason they're use today as much as some say is simply because when you add to software that's been developed, you try and keep the code similar to what's already there.

    You guys are talking like I'm bashing the point of the linked list. I said they're the foundation for many modern structures. I said to the OP that he should learn them if his teacher is teaching them. I just can't think of too many practical uses for linked lists, today. And keep in mind, I'm talking about the bare linked list here. I'm not saying that any modern container that uses the logic of linked lists to operate.
    Sent from my iPadŽ

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318

    Wink Sure

    Quote Originally Posted by SlyMaelstrom
    Does it? I'm glad you figured it out because I'm sure it would have been weird for you if you didn't. I'm sure it could be done, but can you name five of tasks that a linked list would be your best option to use to accomplish it as efficiently as possible?
    I'm up to that:
    Tracking unused memory in a fixed item size pool allocator.
    A message queue.
    A list of particles in a particle generator.
    The list of active edges in an Edge-Buffer algorithm.
    Inside of a runtime engine for a language such as prolog.

    Note, these are cases where specifically a singly-linked list is most efficient, not a doubly linked list. I know my data-structures well, and where they are most appropriate. It's certainly true however, that C++ has made it easier to pick a better data structure in many circumstances.

    Try not to exaggerate by such a foolish amount next time.

  5. #20
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    one more point: why would the standards committee bother writing the stl list container if they thought linked lists were useless
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  6. #21
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Quote Originally Posted by major_small
    one more point: why would the standards committee bother writing the stl list container if they thought linked lists were useless
    Well...
    Quote Originally Posted by SlyMaelstrom
    And keep in mind, I'm talking about the bare linked list here. I'm not saying that any modern container that uses the logic of linked lists to operate.
    Lists have their purposes, and I'd say iMalc listed some good examples of them. That's why I said they should be taught in school. That's why I told the OP he should learn them. But the fact that there is an STL list container as well as so many others only reinforces my statement that the use of a user defined basic linked list is outdated.

    Now, iMalc, would you say that you would define your own linked list structure or would you use the predefined standard list container? I don't see a reason not to use it.

    It's just like character arrays. There is a std::string object that is much more effective. Why go through the hassle of doing the work yourself? You know I gotta tell you, with the way you guys have been replying, I think you're thinking your fighting a different battle than you actually are.
    Sent from my iPadŽ

  7. #22
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> And keep in mind, I'm talking about the bare linked list here. I'm not saying that any modern container that uses the logic of linked lists to operate.

    well that certainly makes more sense - I wasn't making that distinction between 'bare' and self-contained lists and merely assumed you meant lists in general (in fact, many of us who started out primarily as C programmers tend to think of 'a list is a list' since even an stl list, stripped of all of the automagical features of C++, is ultimately just a glorified bundle of pointers all the same. ) at any rate, I definitely agree that the latter is probably a better choice than the former in most cases.

    btw, I really don't see the sense in starting a flame war over this...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  8. #23
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    Quote Originally Posted by SlyMaelstrom
    It's just like character arrays. There is a std::string object that is much more effective. Why go through the hassle of doing the work yourself? You know I gotta tell you, with the way you guys have been replying, I think you're thinking your fighting a different battle than you actually are.
    probably. but I like knowing how lists work and the ability to write them leaves the door open for more possibilites.

    I can make a virtual building out of nodes with an elevator that can travel up, down, left, right and right.

    (at this point I'm just messing)
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  9. #24
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    I agree with not starting a flame war, and I am not the one to start this fight. Nor is Major. Again, major, I agree that you should understand linked lists. It's a nessassary part of programming. Even if you don't implement one yourself, if you plan on getting a job in programming, you'll have to deal with them eventually. Probably on the first day. As far as understanding goes, I think people should understand every aspect of the language they are learning. Good and bad. I think people should know what goto does and how it's used. They have to know it because it exists in the world that they are studying.
    Sent from my iPadŽ

  10. #25
    Registered User
    Join Date
    May 2005
    Posts
    12
    It seems this topic has became a war field. Why did you guys keep on argue about linked list anyway ?? i don't get it at all. Anyway thank you for all the reply. i really appreciate it.

  11. #26
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    Quote Originally Posted by isarapearl
    It seems this topic has became a war field. Why did you guys keep on argue about linked list anyway ?? i don't get it at all. Anyway thank you for all the reply. i really appreciate it.
    this isn't a flame war, it's a debate (if you could even call it that)

    Now, if I said sly was useless and didn't know what he was talking about, that would be a flame

    j/k
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  12. #27
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    the basic linked list has a very important use still (even if you would choose to never use it directly for performance or whatever reasons): to serve as a backing structure for the libraries that implement all kinds of wrappers around them.
    If noone were to know how to implement one anymore (as is ever more often the case with people "learning" "programming" these days, soon there will be noone left who can create and maintain those libraries and then what are we to do?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM