Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linked list class c++ design

  1. Mar 21, 2014 #1
    I decided to make a library for some common data structures and I'm facing some design problems.
    I wanted to implement linked list using classes in c++.

    Here is the sample class:-
    Code (Text):

    class Linked_List
    {
    private:
        int key;
        Linked_List* next;
    public:
        Linked_List(int key)
        {
            this->key = key;
            this->next = NULL;
        }
        void insert(int key)
        {
        ...
        }
        void delete(int key)
        {
        ...
        }
    }
     
    I want the next pointer to point to another Linked_List class. Current class should store key and pointer to next class.
    Problem with this design:
    1) In constructor I have to give the first key. I can't have a class with no key.
    2) When I need to insert a key before the first one, then it involves deleting the "this" pointer but that's not possible.

    Any better design for a linked list class? (some standard implementation)?
     
  2. jcsd
  3. Mar 21, 2014 #2

    Borek

    User Avatar

    Staff: Mentor

    Best design I can think of:
    Code (Text):
    #include <list>
     
  4. Mar 21, 2014 #3

    jtbell

    User Avatar

    Staff: Mentor

    I think most of the textbook-type designs I've seen for a linked list in C++ use two classes: one for the individual nodes (data and associated pointer(s)), and one for the list as a whole (containing a pointer to the first node, plus other useful data as desired).

    Nevertheless, thinking about your proposed scheme a bit:

    If you don't have a first key, you have an empty list. How do you propose to represent an empty list?

    Create a new list and make it point to (the beginning of) the existing one. The existing list doesn't need to change.
    Try writing a second constructor, which takes a key and a LinkedList as parameters, and constructs a new list whose first node contains the given key, and then points to the given LinkedList.
     
    Last edited: Mar 21, 2014
  5. Mar 21, 2014 #4

    jtbell

    User Avatar

    Staff: Mentor

    I think it's confusing to have the same name 'key' for both the private data and the parameter of the constructor (and your other member functions). If you use different names, then you don't need to invoke the 'this' pointer.

    Code (Text):

    class Linked_List
    {
    private:
        int key;
        Linked_List* next;
    public:
        Linked_List(int newKey)
        {
            key = newKey;
            next = NULL;
        }
    ...
     }
     
    A key (pun intended :tongue2:) aspect of writing good, maintainable code is to choose names carefully so that they clearly indicate their purpose and relationships, and don't confuse the reader.
     
    Last edited: Mar 21, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook