Thread: linked list - when to use?

  1. #1
    blah
    Guest

    linked list - when to use?

    hi,

    can anyone tell me when i "should" be using linked lists? i know this is a very broad question, but i'm just trying to figure out when they would work better than just using an array.

    thanks!

  2. #2
    Registered User biosx's Avatar
    Join Date
    Aug 2001
    Posts
    230
    Essentially, arrays and linked-lists can be used interchangeably. It really depends on the situation though. You have to think of the pro's and con's of each:

    Arrays
    Pros
    • Easy pointer manipulation (i.e. You can just used indexes)
    • Easier to read and understand by the programmer
    • A fixed size (this can be a good thing if you don't want something getting too big)


    Cons
    • A fixed size (this can be a bad thing considering that it limits your space)
    • You have to think of a size for the array that will accomodate any situation while not being too astronomical.


    Linked-Lists
    Pros
    • Not fixed size. Can accomodate any amount of data (given the hardware)
    • You can create nested lists within the list (very useful for trees)


    Cons
    • Not fixed size. Things can go out of hand sometimes.
    • Tougher pointer manipulation. (You have to keep track of where everything is pointing).
    • To access any node, you must travel through all of the previous nodes


    I think some great uses for Arrays would be stacks, FIFO's, and other simple data constructs.

    Some great uses for Linked-Lists would be Binary trees, 2-3 Trees, and basically things you aren't sure how large they are to be.

    I hope that helped clear things up.

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Some more pros/cons:

    arrays::

    pro:

    - compiler generates very fast iteration code since the cells are guaranteed to be side-by-side in memory.

    con:

    - to remove an item you must effectively shift an entire chunk of cells over, which can be quite inefficient.

    lists::

    pro:

    - to remove an item, simply "detach" it from the list and place it somewhere else/destroy it quite easily and efficiently.

    con:

    - when sorting a list, it is difficult to implement the more efficient techniques, such as quicksort. This is mainly because these algorithms rely on indexes to navigate.
    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;
    }

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    You should be using linked lists when you don't need random access or sortedness, searching is not done often, but you will be doing a lot of insertions and deletions, especially if those insertions/deletions are in the middle of the sequence.

    Basically, insertions and deletions are really fast in a linked list, but it suffers from not being able to access arbitrary elements quickly.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    blah
    Guest
    that's exactly what i thought. thanks very much to all of you!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM