Thread: LinkedListery Goodness

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    545

    LinkedListery Goodness

    I've just got onto linked lists, and my book uses all these classes to make it...I take it there is pretty much a standard syntax to make these...can you post it for me please?

    What would you want to use linked lists for?

  2. #2
    Registered User Kurisu's Avatar
    Join Date
    Feb 2006
    Posts
    62
    Basic linked list.

    Code:
    struct node
    {
       int value;
       node *next;
    }
    
    int main()
    {
      node *listHead;
    
      listHead = new node;
    
      listHead->value = 5;
      listHead->next = new node;
    }
    Linked lists are dynamic so nodes can be inserted anywhere in the list much easier than inserting a value in the middle of an array. Linked lists being dynamic also allow it to grow or shrink as needed, which optimizes memory.

    Structures like trees work on this kind of coding.

    Ex:
    Code:
    struct node
    {
       int value;
       node *left;
       node *right;
    }
    Objects like Vectors are linked lists and are available in the STL if you don't care how they are coded, but rather just want to use them.
    Last edited by Kurisu; 04-25-2006 at 10:32 AM.

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    545
    Ok thanks...my book had like 5 classes...node, linked list, internal node etc

  4. #4
    Registered User Kurisu's Avatar
    Join Date
    Feb 2006
    Posts
    62
    Well often for a more comprehensive linked list atleast one class and one struct would be created so that using the linked list would be easier to use such as creation, destruction (important because linked list is dynamic i.e. free memory), adding item, deleting item, finding item, etc.

    Ex:
    Code:
    struct node
    {
       int value;
       node *next;
    }
    
    class linkedList
    {
      public:
        linkedList();
        ~linkedList();
        insertItem(int);
        deleteItem(int);
        findItem();
        
      private:
        node *head;
    }
    
    
    int main()
    {
       linkedList phoneNumbers;
    
       phoneNumbers.insertItem(3019854434);
    }

  5. #5
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Drawback with linked list is that you always have to start at the head or the tail (unless you store the middle element all the time n stuff and kept the list sorted). So the time it takes to find an element in the list depends on the elements place in the list and the size of the list. An array for instance has much faster access to an arbitrary object.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Objects like Vectors are linked lists and are available in the STL
    vectors aren't implemented with linked lists since they require contiguous storage. The list container is implemented as a linked list.

  7. #7
    Registered User
    Join Date
    Nov 2005
    Posts
    545
    How would I then output my list and how do I order the information in my list?

  8. #8
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    To output the info you just go from the head to the tail. To sort the list you do that when you insert....http://www.cprogramming.com/tutorial/lesson15.html is a tutorial on linked list.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  9. #9
    Registered User
    Join Date
    Nov 2005
    Posts
    545
    Can you give me a full code because Kurisu's doesn't actually compile when added into stuff.

  10. #10
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    if you just want to use a linked list (as oppossed to writing one yourself) just use std::list.

    if you want to learn about linked lists, write your own one, use it for a few days and then compare it to std::list. At that point, you should throw away your implementation and never use it again.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> vectors aren't implemented with linked lists since they require contiguous storage. The list container is implemented as a linked list.

    they can be, but aren't usually coded that way (when you think of a vector in terms of concept of access, it doesn't really matter how you implement it ~ just that it conforms to the expected interface). it wouldn't be as efficient at indexing, but it would outperform the usual implementation in other respects.
    Last edited by Sebastiani; 04-25-2006 at 06:11 PM. Reason: grammar
    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;
    }

  12. #12
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by Sebastiani
    >> vectors aren't implemented with linked lists since they require contiguous storage. The list container is implemented as a linked list.

    they can be, but aren't usually coded that way (when you think of a vector in terms of concept of access, it doesn't really matter how you implement it ~ just that it conforms to the expected interface).
    are you sure about that? I'm fairly certain the Standard requires a vector to have contiguous storage. I don't have the standard in front of me so I can't check, but I'm almost certain that this should be standard-conforming
    Code:
    /* old c interface */
    void printIntArray(int* pArray, int size)
    {
        int i = 0;
        for (; i < size; ++i)
        {
            printf("%d", pArray[i]);
        }
    }
    
    std::vector<int> foo;
    foo.push_back(1);
    foo.push_back(2);
    foo.push_back(3);
    foo.push_back(4);
    
    printIntArray(&foo.front(), foo.size());
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >my book had like 5 classes...node, linked list, internal node etc
    That sounds like Jesse Liberty being overly complicated with simple concepts again. If not for books like his, people might actually realize that this stuff is pretty easy. When teaching data structures, I prefer to eschew the OO crap because it only serves to hide the concepts under layers and layers of abstraction framework. As you've seen, some authors don't agree.

    >I take it there is pretty much a standard syntax to make these
    Not really. There are conventions when it comes to the algorithms used, but the interface and implementation are largely up to the author, and dependent on how the list is going to be used.

    >I'm fairly certain the Standard requires a vector to have contiguous storage.
    Correct.
    My best code is written with the delete key.

  14. #14
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    I would definitely recommend Prelude's tutorials, actually (the sorting and hashtable articles are great). a good reference at any level.

    >> There are conventions when it comes to the algorithms used, but the interface and implementation are largely up to the author, and dependent on how the list is going to be used.
    >> When teaching data structures, I prefer to eschew the OO crap because it only serves to hide the concepts under layers and layers of abstraction framework.

    and you see new programmers go wrong there by jumping into such compl(ex|icated) projects before even knowing what a byte actually is, or how to dereference a pointer, or whatever.

    >> I'm fairly certain the Standard requires a vector to have contiguous storage.

    Code:
    void printIntArray(int* pArray, int size)
    I see your point, and I understand why the standard went that way on it - but I'm just not convinced that that's production code (why not a templated iterator?) - it's almost like a textbook example...
    Last edited by Sebastiani; 04-25-2006 at 11:00 PM. Reason: code tags, formatting
    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;
    }

  15. #15
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by Sebastiani

    >> I'm fairly certain the Standard requires a vector to have contiguous storage.

    Code:
    void printIntArray(int* pArray, int size)
    I see your point, and I understand why the standard went that way on it - but I'm just not convinced that that's production code (why not a templated iterator?) - it's almost like a textbook example...
    why not a templated iterator? because it's a C interface for some huge library you need (Win32 for example).
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Party goodness
    By master5001 in forum Party Board
    Replies: 0
    Last Post: 09-26-2008, 01:37 PM