C/C++ How to Improve the Design of a Linked List Class in C++?

[Avichal]

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:-

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)?

 

[Borek]

Best design I can think of:

#include <list>

 

[jtbell]

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:

1) In constructor I have to give the first key. I can't have a class with no key.

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

2) When I need to insert a key before the first one, then it involves deleting the "this" pointer but that's not possible.

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.

 

[jtbell]

class Linked_List
{
private:
    int key;
    Linked_List* next;
public:
    Linked_List(int key)
    {
        this->key = key;
        this->next = NULL;
    }
...
 }

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.

class Linked_List
{
private:
    int key;
    Linked_List* next;
public:
    Linked_List(int newKey)
    {
        key = newKey;
        next = NULL;
    }
...
 }

A key (pun intended ) 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.