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

 

[LudusRex]

I would recommend considering the following design solutions for your linked list class in C++:

1. Consider using a dummy node at the head of the list: A dummy node is a placeholder node that does not contain any data, but serves as the head of the list. This can solve the issue of having to give a key in the constructor, as the dummy node can act as the first node in the list. This also solves the problem of inserting a node before the first one, as the dummy node can always be used as a reference point.

2. Use templates to make the class more generic: Templates allow for the creation of generic classes that can work with different data types. This can make your linked list class more versatile and useful for a variety of applications.

3. Consider implementing a double-linked list: A double-linked list has nodes that contain pointers to both the next and previous nodes. This can make insertion and deletion operations easier, as the previous node can be used to update the pointers when inserting or deleting a node.

4. Look into existing libraries and implementations: There are many existing libraries and implementations of linked lists in C++ that you can refer to for guidance and inspiration. Some popular options include the STL list container and Boost's Intrusive List.

Overall, it's important to carefully consider the design of your linked list class to ensure efficiency, versatility, and ease of use. By exploring different options and considering the specific needs and goals of your project, you can come up with a design that works best for you.