Tutorial [C++] Doubly-Linked Lists - Data Structures

Tutorial [C++] Doubly-Linked Lists - Data Structures - Printable Version

+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: C, C++, & Obj-C (https://sinister.li/Forum-C-C-Obj-C)
+--- Thread: Tutorial [C++] Doubly-Linked Lists - Data Structures (/Thread-Tutorial-C-Doubly-Linked-Lists-Data-Structures)

[C++] Doubly-Linked Lists - Data Structures - dotcppfile - 09-04-2015

Hello people,

Lets me just make things clear here; I'm making this tutorial because I'll post it as an entry on this thread: https://sinister.li/Thread-Syntax-Competition-Best-Coding-Thread
Now, I obviously don't give a shit about this "NSP" or whatever you want to call it because I simply do not know the hell that is lol and I do not want join Syntax() basically because it's an official group where you're forced to be active all the time and shit like that so I'll probably last for a day or two lol, the reason I'm doing this is because I'm a nice guy, I know this is emotional but please do not cry lol, that competition got no entries so far and this section is kind of homosexual since the biggest tutorial is probably explaining some dumb stuff in a few lines... Now that we got this shit out of the way we can move on to the actual tutorial.

What is a Linked Data Structure ?
If we want to explain this in a noob way then it's simply an array of structures, the items within this array are called Nodes and are connected with pointers and the size doesn't have to be constant(I am not mentioning "dynamic allocations" in this case because I don't want people, that are new to this, to mix shit up).

Advantages/Disadvantages of Arrays/Vectors:

Disadvantages of an Array:
So, we all know how arrays are defined:

Code:
char char_array[] = "some text";
int int_array[] = {1,2,3};

Now, you can go ahead and talk about dynamic allocations or empty arrays or whatever but it's all the same in this tutorial.
What matters here is how these are actually defined:

The allocated memory of the array is all in 1 place, so if you define an int array with a size of 4 items then you basically allocated 16 bytes in memory; these bytes are all placed in memory one after the other.
The size of the item that you can store is basically fixed, so if you define a 4 bytes char array, for example, the size of the elements are all the same; they're each 1 byte and you cannot change that.
Whether it's a static or a dynamic allocation, the size of that array needs to be defined. Whether the size is constant or defined on run time, once the array is allocated then you simply have to use it the way it is, now ofcorse you can use realloc(which isn't so efficient) or create a second one and copy to it the bytes of the first one then delete/free the first one and keep using the second one (which is something, I consider, dumb since it requires a lot of operations).
Switching/Deleting elements in an array or doing anything similar is complicated and requires a lot of CPU Operations and Memory usage.
etc

Advantages of an Array:

One thing is sure and clear here, a lot of predefined functions that you can apply on arrays which makes everything a lot easier, whether it's memcpy, sprintf or any other predefined function; the point is that you don't have to create them yourself.
Reading data is simple and fast since the only thing required, for example, is to change the index by jumping a constant amount of bytes and that's pretty much it.
Random Access; you can chose to read/write any item at any time as long as you give an index, which is a really good thing.
Arrays receives all benefits of Data Cache which makes things even faster while other types of lists fail at doing so.
etc

Disadvantages of a Vector:
Item 1, 2 and 4 from the "Disadvantages of an Array" part.
And more...

Advantages of a Vector:

Dynamically allocated, and you can easily add as many items as you want and any time you want.

All the items from the "Advantages of an Array" part.
Even more, that's all I can think of right now...

Disadvantages of a Doubly Linked List:

Data needs to be read in a sequential way, you can't just go ahead and point with an index, for example, towards an item; if you're looking for an item then you basically need to go and read every item in the list using comparison operations to find what you're looking for.
No predefined functions, you have to code everything yourself, literally everything.
No benefits at all from Data Cache.
Even though adding/removing an item in a Linked Data Structure isn't complicated or hard and is more efficient than doing so in an Array, they require extra CPU operations; you'll understand this better by checking the "Code" part.
etc

Advantages of a Doubly Linked List:
The complete opposite of all the items in the "Disadvantages of an Array" part.

Code:
Lets create our item first, which is a structure:

Code:
struct NODE {
    int id;
    char username;
    NODE *next = NULL;
    NODE *prev = NULL;
}

id and username are normal variables within the structure.
next is used to point to the NODE that comes after the current one.
prev is used to point to the NODE that was before the current one.
As simple as that.
So we basically got a node that holds any type of variables but also holds two extra pointers that are needed to point to what's after and what's before and that is basically everything you need to know about Doubly-Linked List, whatever comes next is something you can easily write yourself if you're well familiar with pointers in C++ but I'll be sharing some code and some functions to make this more understandable for whoever didn't get it yet.

So, now that we have our Structure ready, lets create our first node shall we? But first, lets create two pointers, the first one will always be pointing towards our first node and the second one will always be pointing towards the last node. We will need both of these the whole time since these define the limits of our list.

Code:
NODE *front = NULL;
NODE *rear = NULL;

Now lets create two simple functions, one is for appending items to the end of the list and the other one is for removing a specific item from the list.

Code:
void add_item(int id, int username) {
    NODE *tmp = new NODE;
    tmp->id=id;
    tmp->username=username;
    tmp->next = NULL;
    if (front == NULL) {
        tmp->prev = NULL;
        front = rear = tmp;
    } else {
        tmp->prev = rear;
        rear->next = tmp;
         rear = tmp;
    }
}

This is simple, we firstly create a pointer called tmp and we point it towards a newly allocated NODE. Now that we have our NODE we simply append the values to it.
The reason we're point "next" to NULL is because, again, this function is used for appending items to the end of the list so nothing comes after this specific item.
Now before we append the item to the list we need to check and see whether this is our first item or not, we simply have to check if "front" is NULL and if it is then this means that this is indeed our first item, now all we need to do is setting the "prev" pointer to NULL since this is our first item and there's nothing before it and we have to make sure that the "front" and "rear" pointers are now equals to "tmp", again, since this is our first NODE in this list.
Now if "front" wasn't set to NULL, then this means that the list is already holding items and again, since we're adding an item at the end of the list, we need to make sure that the "prev" pointer in our NODE points towards the same address that "rear" is pointing to since "rear" points towards the last item in the list. And now since our "tmp" is the last NODE then we need to make sure that the "next" pointer in "rear" points to it.
Finally, and again lol, since our new node is the last item in the list we simply need to make sure that "rear" is now pointing towards that item since "rear" is supposed to do so.

Code:
void delete_item(int id) {
    NODE *curr = front;
    while (curr != NULL) {
        if (curr->id == id) {
            if (curr == front) {
                front = curr->next;
                delete curr;
                return;
        } else if (curr == rear) {
            rear = curr->prev;
            delete curr;
            return;
        } else {
            curr->prev->next = curr->next;
            delete curr;
            return;
        }
    }

    curr = curr->next;
    }
}

This function is used to delete a specific item in the list. In this example, that specific item is identified based on its id.
If we want to delete a specific item in a Linked List Data structure then we simply need to read the needed values (id in this case) in every node until we find what we're looking for.
So this new pointer that we created should be firstly pointing towards our first NODE.
Now we can use a simple while loop that will check whether the value of curr is set to NULL (which means that we finished reading everything in the list).
After we find the "id" we're looking for we can then go ahead and remove the current node.
Now there's a lot of things to keep in mind before we do so, such as checking whether the current node is the first item in our list or the last one and then we can go for it based on what we know.
I won't be explaining more since I'm tired and I believe that I already explained too much; the code is simple and easy and if you have any questions then post them in a reply.

THE END
Now before I go get something to eat since I haven't eaten shit for 18 hours because I forgot to lol, I think that you must know that these simple functions that I wrote using notepad need a lot of improvement and you gonna have to figure that shit out yourself.
There's a lot you can do, I personally like Linked List Data Structures and that is because I decide what happens and what doesn't, I know exactly what's going on since I wrote it all, but again, everything has its advantages and disadvantages and it's up to you to decide what would fit best in your application.
Before I leave you here, examples, tuts and more information about Linked List Data Structures are everywhere so do not hesitate to use google and get more into it.

Thanks for reading,
dotcppfile.

RE: [C++] Doubly-Linked Lists - Data Structures - Inori - 09-04-2015

Couldn't help but notice that you posted this in "coding" when there's a C/C++/Obj-C sub-forum available. Might want to delete thread and repost there.

RE: [C++] Doubly-Linked Lists - Data Structures - dotcppfile - 09-04-2015

(09-04-2015, 03:52 AM)Chitoge Wrote: Couldn't help but notice that you posted this in "coding" when there's a C/C++/Obj-C sub-forum available. Might want to delete thread and repost there.

True but too bad I'm on my phone so I cant do that right now. Lets hope a mod does it.

RE: [C++] Doubly-Linked Lists - Data Structures - 0xDEAD10CC - 09-05-2015

In C++ typically it's not a great idea to use a linked-list, in C it's an easy way to chain things together, but linked-lists in general are very bad for performance. Additionally, they also make it more prone to make tons of cache-misses, and this is even more true the larger the list is. Aside from the allocations too, you have to store pointers bidirectionally so that you can make proper manipulations to the web of data. Linked lists are probably 100 times slower in some cases than a vector because of this. Sure, with a vector you have to move a lot of elements within an allocated space but caches are very efficient at doing this. Using pointers in the way a linked list uses them is like poison to caches.

Quote:3. Whether it's a static or a dynamic allocation, the size of that array needs to be defined. Whether the size is constant or defined on run time, once the array is allocated then you simply have to use it the way it is, now ofcorse you can use realloc(which isn't so efficient) or create a second one and copy to it the bytes of the first one then delete/free the first one and keep using the second one (which is something, I consider, dumb since it requires a lot of operations).

You can only use realloc() on memory allocated on the heap with a function like malloc() though, just to clarify.

Other advantages of a vector:
- It takes care of memory for you, and as of C++11 all STL containers utilize RAII to ensure safe memory management even in the case of an exception
- C++11 - std::vector<bool> is specialized to essentially store each element as a bit in size

edit: Don't forget the semi-colon at the end of your struct

Code:
struct NODE {
    int id;
    char username;
    NODE *next = NULL;
    NODE *prev = NULL;
}; <---

Why do you keep nodes for front and back though? Just globally too? That may avoid the requirement to linear traverse the linked list for each deletion and insertion, but you have to do this anyways if you want your linked list to be sorted in some way anyways or if you're deleting specific data or searching for something.

Btw, for your deletion function:

Code:
if (curr == front)
else if (curr == rear)

These checks are not as useful because you should know if they are the front or the back of the linked list simply by the node's contained pointers, you shouldn't have to compare the pointer to the current node at all. If prev is null when you compare the id, then you know that it should be the front, and reversely, if the next pointer is null, then you should automatically be able to deduce that it's the end of the linked list.

i.e. Here's how I'd write it.

Code:
void delete_item( int id)
{
  NODE *curr = front;
  while (curr)
  {
    if (curr->id == id)
    {
      if (!curr->prev) front = curr->next;
      else if (!curr->next) rear = curr->prev;
      curr->prev->next = curr->next;
      curr->next->prev = cur->prev;
      delete curr;
      return;
    }
    curr = curr->next;
  }
}

I'd also put the front and rear pointers into an object of its own, that way you don't have to rely on these being global, and you can pass a pointer to the struct containing these 2 pointers to modify them within the function if your strategy is to keep a pointer to the start and end of the doubly linked list.

RE: [C++] Doubly-Linked Lists - Data Structures - dotcppfile - 09-05-2015

(09-05-2015, 01:31 AM)0xDEAD10CC Wrote: In C++ typically it's not a great idea to use a linked-list, in C it's an easy way to chain things together, but linked-lists in general are very bad for performance. Additionally, they also make it more prone to make tons of cache-misses, and this is even more true the larger the list is. Aside from the allocations too, you have to store pointers bidirectionally so that you can make proper manipulations to the web of data. Linked lists are probably 100 times slower in some cases than a vector because of this. Sure, with a vector you have to move a lot of elements within an allocated space but caches are very efficient at doing this. Using pointers in the way a linked list uses them is like poison to caches.

True but this ain't just about speed, linked lists offers a lot more and the fact that you can do whatever you want with any item you want easily is what makes it a little bit special. Now, just like I mentioned in the main thread, the programmer himself needs to know what's needed and what isn't in his application.

(09-05-2015, 01:31 AM)0xDEAD10CC Wrote: You can only use realloc() on memory allocated on the heap with a function like malloc() though, just to clarify.

Obviously mate...

(09-05-2015, 01:31 AM)0xDEAD10CC Wrote: Other advantages of a vector:
- It takes care of memory for you, and as of C++11 all STL containers utilize RAII to ensure safe memory management even in the case of an exception
- C++11 - std::vector<bool> is specialized to essentially store each element as a bit in size

Nice share right there mate.

(09-05-2015, 01:31 AM)0xDEAD10CC Wrote: edit: Don't forget the semi-colon at the end of your struct

Code:
struct NODE { int id; char username; NODE *next = NULL; NODE *prev = NULL; }; <---

lol.

(09-05-2015, 01:31 AM)0xDEAD10CC Wrote: Why do you keep nodes for front and back though? Just globally too? That may avoid the requirement to linear traverse the linked list for each deletion and insertion, but you have to do this anyways if you want your linked list to be sorted in some way anyways or if you're deleting specific data or searching for something.

Keeping nodes for front and back gives you more control over your linked list, ofcorse, in these examples, this doesn't show up much but this will change as soon as you start getting deeper into linked lists which makes their declaration and their usage always a good practice.
For the second question, no one said anything about globally mentioning them, what you see on this thread is pieces of codes to make people think, it ain't a whole program, there ain't no includes, no main, no output and no nothing, again, it's just pieces of code. Now, if I ever wanted to use these then I would probably store them both in a structure and keep it global or pass its address to other functions.

(09-05-2015, 01:31 AM)0xDEAD10CC Wrote: Btw, for your deletion function:

Code:
if (curr == front) else if (curr == rear)

These checks are not as useful because you should know if they are the front or the back of the linked list simply by the node's contained pointers, you shouldn't have to compare the pointer to the current node at all. If prev is null when you compare the id, then you know that it should be the front, and reversely, if the next pointer is null, then you should automatically be able to deduce that it's the end of the linked list.

i.e. Here's how I'd write it.

Code:
void delete_item( int id) { NODE *curr = front; while (curr) { if (curr->id == id) { if (!curr->prev) front = curr->next; else if (!curr->next) rear = curr->prev; curr->prev->next = curr->next; curr->next->prev = cur->prev; delete curr; return; } curr = curr->next; } }

True, you can always check prev and next in a node but since we already declared front and rear then why not use them? After all, we have to go for a comparison operation.

(09-05-2015, 01:31 AM)0xDEAD10CC Wrote: I'd also put the front and rear pointers into an object of its own, that way you don't have to rely on these being global, and you can pass a pointer to the struct containing these 2 pointers to modify them within the function if your strategy is to keep a pointer to the start and end of the doubly linked list.

I replied to this in the middle of this whole reply.

RE: [C++] Doubly-Linked Lists - Data Structures - 0xDEAD10CC - 09-05-2015

"For the second question, no one said anything about globally mentioning them" -- Yeah but that's implied when you use them in a function which doesn't declare them locally or pass them as parameters. That's why I mentioned them. I assumed you were providing a snippet that others could copy and paste as readily usable.

Smile

[C++] Doubly-Linked Lists - Data Structures - dotcppfile - 09-05-2015

Dont just quote half of the answer...

(09-05-2015, 01:50 PM)dotcppfile Wrote: For the second question, no one said anything about globally mentioning them, what you see on this thread is pieces of codes to make people think, it ain't a whole program, there ain't no includes, no main, no output and no nothing, again, it's just pieces of code. Now, if I ever wanted to use these then I would probably store them both in a structure and keep it global or pass its address to other functions.

RE: [C++] Doubly-Linked Lists - Data Structures - 0xDEAD10CC - 09-06-2015

I know what you said, and I had it taken into consideration when I wrote the reply regardless of whether it was quoted or not. I know it's not a whole program, there's no examples given for the usage of the functions, but what I was saying is for how those functions work, it doesn't have to be an entire program to imply that those variables are meant to be defined before the functions, and global. The discussion about this anyways has outlived it's usefulness, we can continue to talk about wording vs semantics all day but it's not going to change an opinion.

My point was that there are tons of libraries and snippets of code out there, but unless you change the code yourself it still has a certain way that you're meant to use that code, before you even write a program with it. The examples posted too were valid snippets and not pseudocode, so I took them in a slightly more literal context than just code that describes how something is supposed to work.

Good thread nonetheless. Smile

RE: [C++] Doubly-Linked Lists - Data Structures - dotcppfile - 09-06-2015

(09-06-2015, 01:04 AM)0xDEAD10CC Wrote: I know what you said, and I had it taken into consideration when I wrote the reply regardless of whether it was quoted or not. I know it's not a whole program, there's no examples given for the usage of the functions, but what I was saying is for how those functions work, it doesn't have to be an entire program to imply that those variables are meant to be defined before the functions, and global. The discussion about this anyways has outlived it's usefulness, we can continue to talk about wording vs semantics all day but it's not going to change an opinion.

Good thread nonetheless.

The thread isn't that good but it gets the job done for whoever doesn't know about Linked Lists and it did get better because of what you shared and that is nice.
As for this discussion that is going on then I will not keep up with it and that is because it'll get worse and we both know that; I respect you and I believe you do the same for me and I want to keep things this way.
Excuse me if I just went for it on this one, I may have drank a bit more than I should but I sure know that I'm not being stupid.

RE: [C++] Doubly-Linked Lists - Data Structures - 0xDEAD10CC - 09-06-2015

All good! I know many programmers have their own idea of what the specifics of a linked-list should be, which is why I wouldn't bother arguing those points. I've seen some ugly implementations where the struct also keeps a copy of the pointer to the beginning of the linked-list, which is a waste of memory IMO.