Nodes

[geniusberry]

Hello again!

So, I'm starting to learn about nodes, and I just don't get them. Specifically, what they do, why they work, and how to use them. Any help would be appreciated. Thanks in advance!

[LB]

Nodes in what context? Nodes on the internet? Nodes in linked lists? Nodes in graphs? Nodes in trees?

[geniusberry]

oh, sorry. I meant nodes as nodes in linked lists. I'm learning about singly linked lists.

[LB]

In linked lists, nodes are structures/classes that contain a single element of the list, a pointer to the next node in the list, and, for doubly-linked lists, a pointer to the previous node in the list. Nodes can be anywhere in memory out of order - the order is known by going from node to node and finding out which node is next via the pointers.

Here's a basic example highlighting the node class:

template<typename T>
struct MyLinkedListClass
{
    //...
private:
    struct Node
    {
        T data;
        Node *next;
//      Node *prev;
    };
    //...
};

[geniusberry]

Thanks for your reply! I think I understand nodes better now. But what's the advantage to this rather than using an array?

[Peter87]

An advantage is that if you want to add or remove an element from the list you just need to change a few pointers. With an array you would have to move all the elements that are stored after, to fill the gap if you are removing, or to make room for the new element if you are inserting.

A disadvantage is that you can't easily jump to a certain position. If you want element at position 100 you will have to step through all the nodes until you reach number 100. With an array it's very easy.

Each data structure has its own pros and cons. Which one to use depends on the situation.

[LB]

Linked lists are a very specialized way to store data, and have very few good use cases. Almost always, you will use an array-like structure. The only times you may want to use a linked list is if the elements are very large and/or you will be doing many insertions and/or removals in the middle of the list.

In the C++ standard library, std::vector is a contiguous list like an array, and you will use it the most, whereas std::list is a linked list structure. In a majority of cases, std::vector is immensely more efficient than std::list to a dramatic and noticeable degree.

Linked lists are considered an optimization, but as with all optimizations, they only work in certain cases. Never use an optimization unless you have profiled your code and found that it is the bottleneck - then you may test various optimizations.

[geniusberry]

Thank you all so much for your answers! I think I've really gotten the concept behind linked lists now. Now to try creating one!