Linked Lists!

[carrja99]

** Keep in mind that this assumes you have a basic understanding of pointers, however no previous knowledge of pointers is required, it is suggested you try to read up on them a bit **

Ah yes, those darn linked lists. Linked lists are quite simple data structures, which work kind of like arrays but with one major difference, they can grow and shrink as needed, which is good because it makes an efficient use of memory. A linked list consists of a node, which contains a key with a value and a link to the next node. Here is how you define a node datatype:

struct node
    { 
     int key;
     node* next;
     };

Now, let's construct a nice simple linked list. Now, in common application, some find it easy to create "dummy nodes" for the beginning of the list and the end of the list. These nodes have a null value, the root node pointing to the first item, the last node pointing to itself. Here we go...

typedef node* node_ptr; // makes it easy for parameter passing

int main(void)
     {
      node_ptr root = NULL, z = NULL, t = NULL, tmp = NULL;

As you noticed, I initialized each node to null. You don't need to do this, I just do this to avoid some problems that could happen. Now, we have defined 3 pointers, root, which will point to the beginning, z, which will signify the last node, and t, which is the pointer we will use to add new nodes to the list and cycle through the list. Now, let's create nodes for the pointers to point to(rather than pointing into the depths of NULL):

root = new node;
z = new node;

/** Now let's have them point to something **/

root->next = z;
z->next = root;

Now we have two empty nodes, one pointing to z, and z pointing to itself. You don't need to use these, and some of us rarely do, but some consider it good practice.

Alright, now lets begin adding a few things to the list. First let's add the number 12 to the list:

t = new node;
t->key = 12;

/** now to insert it into the list **/

root->next = t;
t->next = z;

There, now we have a single item in the list. Now, let's say you want to add more to the end of the list, leave t pointing at the last position, and all you need to do is add to it:

tmp = new node; 
tmp->key = 5; 
tmp->next = z;

t->next = tmp; //points t's link to the new node
t = t->next; //moves the pointer to the next node.

that's simple enough. Now let's print the nodes out for our linked list:

t = root->next;

cout << "The first item in the list is " << t->key << endl;

t = t->next;

cout << "The 2nd item in the list is " << t->key <<endl;

Pretty easy huh? Now let's delete an item. let's say I want to delete the 1st item.

tmp = root->next; // selects the first node
root->next = tmp->next; //points root to the node after tmp 
delete tmp; //removes the node from memory

t = root->next; //traverse to the 1st node
cout << "The value of the first node is " << t->key << endl;

Now, you may say "why not just point the link to the node after it? It can't be accessed, so by all means, isn't it gone?" Not neccisarily. Sure, you may not be able to access it directly from the list, but it still exists in memory. Therefore, it's a good idea to delete it before moving on. I think java has "automatic garbage removal" for nodes that are removed, though I am unsure.

Well, that concludes this tutorial. Keep in mind that the above code snippets are the most simple way to make it easy to understand. A more efficient way would be to create functions that add and remove nodes, so the whole process could take only about 5 or 6 lines of code to create a huge list of nodes and remove any node at any point. Play around with nodes and and loops, and keep in mind that things you can do with arrays can sort of be done with linked lists, and sorts for arrays can be converted to linked lists easily. Good luck!