Linked Lists (C/C++). What are the advantages/disadvantages of creating both a list struct and a node struct?

user_9351296 0
Viewed 177

I've seen various implementations online were some only create a node struct for their linked lists, while others create both a list struct and a node struct and thus I was wondering what is best practice.

Example of list and node_struct implemenation:

typedef struct listnode listnode_t;
struct listnode {
    listnode_t *next;
    listnode_t *prev;
    void *elem;
};

struct list {
    listnode_t *head;
    listnode_t *tail;
    int size;
};

Example of node struct only implementation:

typedef struct node node_t;
struct node { 
    int data; 
    node_t *next; 
};
node_t *head;
node_t *tail;
linked-list list c c++
3 Answers

I was wondering what is best practice.

The usual idiom applied with c++ is to create a private node struct type inside of a list class:

class list {
    struct listnode {
        listnode *next;
        listnode *prev;
        void *elem;
    };
    listnode *head;
    listnode *tail;
    int size;

public:
    // Some public operations here. 
    // listnode instances must be referred by clients using the auto keyword
    list::listnode* insert_after(list::listnode* prevnode, void* elem) {
        list:listnode newNode = new list:listnode();
        newNode->elem = elem;
        newNode->prev = prevnode;
        newNode->next = prevnode->next;
        newNode->next->prev = newNode;
        prevnode->next = newNode;
        return newNode;
    }
};

And the real best practice in c++ is simply to use std::list<T> from the standard library.

user_14133950

We are comparing apples and oranges here. The first example you show is a double-link list. The second example is a node representation of a linked list.

But, if we ignore this dissonance, it is better to separate the concerns. For the one hand, you try to make sure that nodes are correctly represented. On the other hand, you try to use those nodes as lists.

If you do not implement a struct for list and resolve your issues at a certain problem-space, then the generality of how a list should work will be mixed up with the particularity of that problem, so you will not be able to reuse your code when you will need a list for other problems and you will duplicate your list implementation over and over again.

Also, you will not be able to hide head and the concern for not losing head will escalate to the code which uses your node.

This will result in mixed-up code, difficult to maintain. You should aim to have a struct for node and another for list.

user_4365600

Some input on that:

  1. If you have a tail, you can insert at the end in Θ(1). Might be useful, depending on what you want to do.

  2. If you have a tail, you can continue write an iterator, allowing you to use range based loops. (Iterators require a method end()).

  3. If a list is a different type than an element, you have a built in safety. For example, let's say you write a sorting algorithm. If you only have nodes, the signature is like void sort(node* list). This allows the user to insert a node element which is not the head of a list but an element from the middle. A separate type would guarantee that it is always a whole list.

  4. You could further make this safer. Right now, one could create a loop with the next pointers, as everything lies barren. Usually you'd want to guarantee that a list is in fact a list. For that, you would encapsulate things, and a part of that would be to have separate types for elements and lists. The advantage of this is that you can say "if you work with this class, it will always be a proper list". You can't ruin it at another place, which would create a bug that might be hard to fix.

  5. In your example, the first structure also is a double linked list. A double linked list has some obvious additional properties, like it requiring more memory but allowing reverse iteration and inserting elements in front of another one.

user_51143420
Related