[TuT] Linked Lists

Basically, you will have a struct which inside will have a pointer, which will point to a new struct of the same type, and on and on.
Example of the struct code:

[php]
struct tagUser {
char name[10];
int age;
char adress[20];
struct tagUser* pNext; //points to a new struct
};
[/php]

Image says it all: (I will talk about pHead on next the part)

Example on Code:

[php]
struct tagUser* pHead = NULL; // you can't loss the location of the head, otherwise you will end up losing your list in memory
struct tagUser* pNew; //used to add a new Item to the list
struct tagUser* pAux; //used to let us search the list without losing her
[/php]

Lists works like This:



To acess "X" you would just need to:
[php] pHead->var [/php]
To acess "P" you would just need to:
[php] pHead->pNext->var [/php]
(pNext of pHead is the next node, so like drawed, is the one with "P")

To acess "T" you would just need to:
[php] pHead->pNext->pNext->var [/php]
(pNext->pNext of pHead is the next node or pHead->pNext, so like drawed, is the one with "T")

Etc... (I don't advice btw to acess them like this xD but it's just to make you understand how it works)

Of course, this will only look like a list if we can at least insert stuff no?
There is 3 ways for you to insert:

• In the head of the list;
• In the middle of the list;
• In the tail of the list;

Well, the simpler is to insert on head, but the more logical to me, is to insert in the tail (end) of the list, and of course, the middle is always useful somehow. Anyway i will write all of them.

By Tail:
Like it was said before you will need to know a way of not losing all your list while trying to edit her.

First of all, lets give you an example in images how this should work:


(This is a normal list)

To


(As you can see for you not to loss stuff, you need to point your last node to the new one, and the new one to NULL (Which was where the other was pointing)

Example code:

[php]
pNew = (tagUser*)malloc(sizeof(struct tagUser)); //allocates the memory for pNew
pNew->pNext = NULL;

cout << "Your age:"; //duh..
cin >> pNew->age; //well, it saves the value in the pointer that is not yet related with your list. so lets make that happen


//inserting in tail
if(pHead == NULL) //if pHead is null, means that there is no items in the list
pHead = pNew; //if there is no items, just add the item to head. Now pHead will equal pNew (the new item)
else
{
pAux = pHead; //if not Null, we will use pAux so we won't use the head of the list
while(pAux->pNext != NULL) //this will search through the list to find the last item (this is why u had to "null" pNext on pNew in earlier code)
pAux = pAux->pNext;
pAux->pNext = pNew; //when on last one, just add it to the list
}

[/php]

And there you go, if you do Debug, you will realize that pHead will now have the item inserted on his pNext.

Saying:
pAux->pNext = pNext is the same as saying
pHead->xxx->pNext (xxx stands for nodes in the middle that might or not have it)
Well, it's not the same... but if you are reading this, you should already know Pointers, and if so, you will understand why.

By Head:

Like the name says, you will insert something in the position of pHead and then point that one to the next of the list. And that one will then be the Head of the list.

[php]
pNew = (tagUser*)malloc(sizeof(struct tagUser)); //allocates the memory for pNew
pNew->pNext = NULL;

cout << "Your age:"; //duh..
cin >> pNew->age; //well, it saves the value in the pointer that is not yet related with your list. so lets make that happen

if(pHead == NULL) //if pHead is null, means that there is no items in the list
pHead = pNew; //if there is no items, just add the item to head. Now pHead will equal pNew (the new item)
else
{
pNew->pNext = pHead; // Simpler then this is impossible, i will say that pHead is now the next of pNew (means that the whole list will go there)
pHead = pNew; //Simple, you still want to have pHead as your list Header, so... ^^
}
[/php]


In Middle:

Almost the same as both of them, but you need to search where to insert.

[php]
int age = 20
pAux = pHead;
while(pAux->pNext->age != 20) //this will search through the list to find the node that you are looking for to be the next of the new one. (In this case you are looking for the one that has the age of 20.
pAux = pAux->pNext;
pNew->pNext = pAux->pNext; / need to make sure you don't loss the rest on the list, so ^^ just like inserting in Head
pAux->pNext = pNew;
[/php]

Printing the whole list:

This is easy stuff if you already did all this, and quite obvious

[php]
pAux = pHead; //always remember to have an Aux for head.. otherwise you will be losing your list everytime u do pAux = pAux->pNext; (if they were pHead)
do
{
cout << pAux->price << endl;
pAux = pAux->pNext;
}
while (pAux != NULL);
cout << "" << endl;
[/php]

Delete nodes from list:

[php]
pAux = pHead;

//run the whole list
while(pAux != NULL)
{
if(pAux->age == 20) //if he finds it
{
if(pAux == pHead) //means he found it right the the first place
pHead = pAux->pNext;
else
{
//search the last one so he can point it
pAux2 = pHead;
while(pAux2->pNext != pAux) //tries to find the pAux (we want to stay in the one before pAux
pAux2 = pAux2->pNext;
if(pAux->pNext == NULL) //if the node is the last node (no need to point to the next one after delete)
pAux2->pNext = NULL;
else //needs to point to next one
pAux2->pNext = pAux->pNext; //if you are searching for node 3.. pAux is 3 and pAux2 is 2.. so you want 2 to point to 4, and delete the 3
}
free(pAux); //free's memory (important)
pAux = pHead;
}
else
pAux = pAux->pNext; //not 2.. next node
}
[/php]


::Conclusion::

Why did i make this tutorial?

Well, I'm not saying that it is perfect, but this was what I did A LOT like an year ago, when i was learning C (Not C++). This was the main think to make me understand pointers, seriously..
I decided to make it so i could "Remember" what i have learned because it's important imo.
Credits to:
Wikipedia for the first quote.
Me (Tutorial, code.. etc)
The person that taught me this an year and half ago.

::Code I used for all this::

It's not the same struct, i did this one before the tutorial to remember everything

[php]#include <iostream>

using namespace std;

struct tagGame {
char name[10];
int price;
char company[20];
struct tagGame* pNext; //points to a new struct
};

int main(void)
{

struct tagGame* pHead = NULL; // you can't loss the location of the head, otherwise you will end up losing your list in memory
struct tagGame* pNew; //used to add a new Item to the list
struct tagGame* pAux; //used to let us search the list without lossing her
struct tagGame* pAux2;

//Example:
//Lets say you get your pHead to point to the next list Item, you will then never know where is the first item... (unless you use more vars)

do
{
pNew = (tagGame*)malloc(sizeof(struct tagGame)); //allocates the memory for pNew
pNew->pNext = NULL;

cout << "Car Price:";
cin >> pNew->price;

if(pNew->price == 0)
break;

//inserting in tail
if(pHead == NULL) //if pHead is null, means that there is no items in the list
pHead = pNew; //if there is no items, just add the item to head. Now pHead will equal pNew (the new item)
else
{
pAux = pHead; //if not Null, we will use pAux so we won't use the head of the list
while(pAux->pNext != NULL) //this will search through the list to find the last item (this is why u had to "null" pNext on pNew in earlier code)
pAux = pAux->pNext;
pAux->pNext = pNew; //when on last one, just add it to the list
}
}
while(1);


//searching
pAux = pHead;

do
{
cout << pAux->price << endl;
pAux = pAux->pNext;
}
while (pAux != NULL);

cout << "" << endl;

//insert in middle


/*pAux = pHead;
while(pAux->pNext->price != 20) //this will search through the list to find the node that you are looking for to be the next of the new one.
pAux = pAux->pNext;
pNew->pNext = pAux->pNext; / need to make sure you don't loss the rest on the list, so ^^ just like inserting in Head
pAux->pNext = pNew;

//insert in head

pNew->price = 1337;
pNew->pNext = pHead;
pHead = pNew; //Simple, you still want to have pHead as your list Header, so... ^^


//searching
pAux = pHead;

do
{
cout << pAux->price << endl;
pAux = pAux->pNext;
}
while (pAux != NULL);

cout << "" << endl;*/

/*pAux = pHead;

while(pAux->pNext->price != 2)
pAux = pAux->pNext;
pAux->pNext = pAux->pNext->pNext; //Example.. you wan to delete node 3.. so you say that the next of 2.. will be 4..
*/

pAux = pHead;

//run the whole list
while(pAux != NULL)
{
if(pAux->price == 2) //if he finds it
{
if(pAux == pHead) //means he found it right the the first place
pHead = pAux->pNext;
else
{
//search the last one so he can point it
pAux2 = pHead;
while(pAux2->pNext != pAux) //tries to find the pAux (we want to stay in the one before pAux
pAux2 = pAux2->pNext;
if(pAux->pNext == NULL) //if the node is the last node (no need to point to the next one after delete)
pAux2->pNext = NULL;
else //needs to point to next one
pAux2->pNext = pAux->pNext; //if you are searching for node 3.. pAux is 3 and pAux2 is 2.. so you want 2 to point to 4, and delete the 3
}
free(pAux); //free's memory (important)
pAux = pHead;
}
else
pAux = pAux->pNext; //not 2.. next node
}



//searching
pAux = pHead;

do
{
cout << pAux->price << endl;
pAux = pAux->pNext;
}
while (pAux != NULL);

cout << "" << endl;

system("pause");
return 0;
}[/php]