Linked List

This is a discussion on Linked List within the C++ Programming forums, part of the General Programming Boards category; was bored at work so i decided to implement a linked list. tell me what u think....all criticism is welcomed. ...

  1. #1
    printf("Hello Cboard\n"); codeprada's Avatar
    Join Date
    Jan 2011
    Location
    In a little room at the back of your brain
    Posts
    68

    Linked List

    was bored at work so i decided to implement a linked list. tell me what u think....all criticism is welcomed. i'm here to learn it does not have every single method. (wasn't that bored). oh and i want to know if there's a way u can avoid writing template<class T> before every method besides using define. below is just the class.


    Code:
    template <class T>
    class LinkedList
    {
    private:
        struct node {
            T data;
            struct node * next,
                        * prev;
        };
        T getDataAtNode(int index);
        struct node * head,
                    * end;
    
    public:
        LinkedList();
        LinkedList(T data);
        void push(T data);
        T pop();
        T operator[](int index);
        bool isEmpty();
        void clear();
        int length();
    };
    
    template <class T>
    T LinkedList<T>::getDataAtNode(int index)
    {
        int c = 0; struct node * iter = head;
        while(iter)
        {
            if (c++ == index)
                return iter->data;
            iter = iter->next;
        }
        return NULL;
    
    }
    
    template <class T>
    LinkedList<T>::LinkedList()
    {
        head = new node();
        head->data = NULL;
        head->next = NULL;
        head->prev = NULL;
        end = head;
    }
    
    template <class T>
    LinkedList<T>::LinkedList(T data)
    {
        if (head != end)
        {
            head = new node();
            end = head;
        }
    
        head->data = data;
        head->next = NULL;
        head->prev = NULL;
    
    }
    
    template <class T>
    T LinkedList<T>::operator[](int index)
    {
        return (getDataAtNode(index));
    }
    
    template <class T>
    void LinkedList<T>::push(T data)
    {
        if(head->data == NULL)
        {
            head->data = data;
        }
        else {
            struct node * new_node = new node();
            new_node->data = data;
            new_node->next = NULL;
            new_node->prev = end;
            end->next = new_node;
            end = new_node;
        }
    }
    
    template <class T>
    T LinkedList<T>::pop()
    {
        T data = end->data;
        if(end->prev)
        {
            end = end->prev;
        }
        else
        {
            end = head;
            head->data = NULL;
        }
        end->next = NULL;
        return data;
    }
    
    template <class T>
    bool LinkedList<T>::isEmpty()
    {
        return (head->data == NULL && head == end ? true : false);
    }
    
    template <class T>
    void LinkedList<T>::clear()
    {
        end = head;
        head->data = NULL;
        head->next = NULL;
    }
    
    template <class T>
    int LinkedList<T>::length()
    {
        int c = 0; struct node * iter = head;
        while(iter)
        {
            c++;
            iter = iter->next;
        }
        return c;
    }
    We shouldn't be quick to criticize unless we can do better.
    Code:
    public function __clone() { die ( "I'm one of a kind" ); }

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,622
    * Define them in the class declaration.
    * Make a macro...
    * Don't use templates!
    Devoted my life to programming...

  3. #3
    printf("Hello Cboard\n"); codeprada's Avatar
    Join Date
    Jan 2011
    Location
    In a little room at the back of your brain
    Posts
    68
    Quote Originally Posted by Sipher View Post
    * Define them in the class declaration.
    * Make a macro...
    * Don't use templates!
    what's so bad about templates?
    We shouldn't be quick to criticize unless we can do better.
    Code:
    public function __clone() { die ( "I'm one of a kind" ); }

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,622
    Quote Originally Posted by codeprada View Post
    what's so bad about templates?
    Nothing, nothing! I was just joking!...
    Devoted my life to programming...

  5. #5
    printf("Hello Cboard\n"); codeprada's Avatar
    Join Date
    Jan 2011
    Location
    In a little room at the back of your brain
    Posts
    68
    Quote Originally Posted by Sipher View Post
    Nothing, nothing! I was just joking!...
    lol oh... i'll add something like a cursor, a next() and previous() function....maybe
    We shouldn't be quick to criticize unless we can do better.
    Code:
    public function __clone() { die ( "I'm one of a kind" ); }

  6. #6
    'Allo, 'Allo, Allo
    Join Date
    Apr 2008
    Posts
    611
    There's a whole bunch of allocating, don't see no freeing.

  7. #7
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,657
    >> oh and i want to know if there's a way u can avoid writing template<class T> before every method

    Define all of the methods inside of the class.

    Also, provide iterators, and provide assignment and copying, at least.

  8. #8
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    Avoiding writing template: write the code inline in the class.
    Suggestions:
    Use typename instead of class.
    Use std::shared_ptr and std::weak_ptr.
    Use nullptr instead of NULL.
    Drop the "struct" on the pointers.
    Problems:
    Not freeing memory!
    Class suffers from raw pointer issues (http://sourceforge.net/apps/mediawik...pointer_issues)
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Don't implement operator[] - linked list are not for random access, it's inefficient to have to traverse an average of half the list to get an element out.

    You should keep track of the size of the list as you add and remove elements so that when you call length() you can return a number straight away. Traversing the list just for this is extremely inefficient!

    Implement a copy constructor and operator= or make them private to avoid accidental shallow copying.

    Quote Originally Posted by Elysia View Post
    Suggestions:
    Use std::shared_ptr and std::weak_ptr.
    Problems:
    Class suffers from raw pointer issues
    While I generally agree with the idea of using smart pointers over raw pointers, I think a fundamental utility like this deserves to not have the overhead of smart pointers.

  10. #10
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    Overhead is negligible. Change it if and only if performance suffers.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,657
    Even if performance suffers, I would suck it up. The only differences between a regular pointer and a weak pointer are that the weak one can transfer ownership of the pointee to a reference counted pointer if you ask it to. Since weak pointers aren't doing anything regular pointers don't, the overhead is actually paid at compile time. (From all the template code.) Actually, I should say that weak pointers are probably not the source of performance problems.
    Last edited by whiteflags; 02-22-2011 at 04:16 PM.

  12. #12
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by whiteflags View Post
    Even if performance suffers, I would suck it up. The only differences between a regular pointer and a weak pointer are that the weak one can transfer ownership of the pointee to a reference counted pointer if you ask it to. Since weak pointers aren't doing anything regular pointers don't, the overhead is actually paid at compile time. (From all the template code.) Actually, I should say that weak pointers are probably not the source of performance problems.
    Hmmm, it would be an interesting experiment to, say, run a script through all of an stl implementation to replace all the raw pointers with weak pointers (probably a custom version of weak pointer to wrap pointer arithmetic and such as well) and then to a comparison with some stl intensive code.
    Last edited by Mozza314; 02-23-2011 at 01:33 AM.

  13. #13
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,657
    That is a very funny joke. There are many parts of the STL that are not bare bones though and template classes become part of other template classes, so if your point in all this is that the STL is all POD implemented, you're wrong anyway.

    At any rate, I stand by what I said.

  14. #14
    Registered User modwind's Avatar
    Join Date
    Dec 2010
    Posts
    15
    To write an STL container like std::list or even std::vector, a lot of effort is needed. Not only coding and testing but developing interfaces. IMHO your main mistake is implementing some random methods without thinking about the user and the purpose of the class.

    Compare it to STL. Where are "front" and "back" methods? Why can I push and pop only in one direction if the list is bidirectional? Are getDataAtNode and operator[] methods really necessary for a list? As you say, "It does not have every single method", but the whole principle is incorrect.

  15. #15
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by whiteflags View Post
    That is a very funny joke. There are many parts of the STL that are not bare bones though and template classes become part of other template classes, so if your point in all this is that the STL is all POD implemented, you're wrong anyway.

    At any rate, I stand by what I said.
    I don't quite follow you there. I could see problems with macros maybe but if you create a wrapper class around pointers with an identical interface why shouldn't you be able to drop it in to the stl libraries? It does seem very optimistic that it would be possible to do a simple search and replace, but I don't see why it couldn't be mostly automated and maybe patched up in a few places.

Page 1 of 2 12 LastLast
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, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21