Linked Lists

scuzzman · 12-28-2004, 08:21 AM

I'm currently trying to teach myself C++ and am having difficulty grasping this concept. The tutorial I'm reading is here, but I fear that, although it explains them well (I think), I can't quite grasp the concept. Could somebody please tell me what these are... or possibly just what they're used for? Or, if possible, just provide a better analogy? Because at this point, I'm just starting to confuse myself further, and I don't want to lose this, I really want to learn to use C++.

deiussum · 12-28-2004, 08:51 AM

Linked lists can be used to store a list of items where you do not know how many items you need to store in the list.

Linked lists are also good when you need to frequently add/remove stuff from the middle of the list. Think of it kind of like a chain. Each link of the chain is called a node. Each node contains the data for a single item in the list, and a pointer to the next node in the chain. For double linked lists, each node also has a pointer to the previous node in the chain, single linked lists only have a pointer to the next node in the chain.

Now, when removing an item from the list, it is like removing a link from a chain. You can separate the link from the other links in the chain, then join together the links that were connected to the removed link. Same with adding a link to the middle. You separate the chain at the links you want to add to, then relink the new link into the chain at that point.

For C++, you can use the std::list object for linked lists, but it is usually good to try and write your own linked list initially so you can get the basic concept. It is also a good practice for starting to learn how pointers work.

As an example, you might have a struct like so:

Code:

struct IntNode
{
    int data;
    IntNode* next;
};

Now, you can have a pointer to a "head" node that points to the start of the chain;

Code:

IntNode* head = NULL;

Setting it to NULL indicates that initially, your list is empty... now you can add an initial item to the list by doing something like so:

Code:

head = new IntNode();
head->data = someData;
head->next = NULL;

Note that you set head->next to NULL to indicate that it is the last node in the chain...

Now, assume you have a lot of nodes listed together. You can do something like the following to find the last node of the list and add a new node at the end:

Code:

IntNode* temp = head;

if (temp != NULL) // make sure we have at least 1 item
{
    while(temp->next != NULL)
    {
          temp = temp->next; // move to the next node
    }
     temp->next = new IntNode();
     temp->next->data = someData;
     temp->next->next = NULL;
}

Now, say you have a node in the middle you want to remove:

Code:

IntNode *temp = head;

// Find the node right before the middlenode we want to delete
while (temp->next != middlenode)
{
     temp = temp->next;
}

// Re-link it around the middlenode we want to delete
temp->next = middlenode->next;

// Can now safely delete middlenode
delete middlenode;

Most of the above is actually more like a C style linked list. Using C++ you would likely wrap it all into a class, and hide the underlying node structure. I hope it helps explain the concept a bit more, though...

Note: some of my code above doesn't go through all the checks you would probably want to do. Stuff like checking if head is null, etc...

deveraux83 · 12-28-2004, 08:59 AM

Well, these types of "things" are collectively called container classes, because they do just that, contain stuff. In the tutorial you are reading, the "stuff" they are trying to contain is integer. You can of course, contain anything you want, integers, floating points, even your own custom made classes, which is what makes them so useful.

Think of a database which stores say the income of certain number of people and you want to write the database for that. Here's an example:

Code:

struct node {
double income;
node *next;
};

Now, in your code, you don't know how many people's income you will be storing or "containing", hence, you would need a dynamic container class (a container class that grows depending on your needs). A linked list is an example of such a class.

Your database program, when written, doesn't know how many people's income it has to store, so, you can just allocate memory for it, like when you do for an array (which is also a type of container):

Code:

double income[100];

In this code, you are limited to having a maximum of 100 people's income, no more. But, with a linked list, you could go higher. Another reason, is that in the above code, if you only store say 20 people's income, the other 80 allocations are wasted in memory since it is not being used. This is another advantage of the linked list, you only allocate it memory when you need it (hence the word, dynamic).

Now, when you actually implement the linked list (I will assume henceforth that you understand pointers reasonably well), you will need a starting point for the list, so you allocate the "root" of the container:

Code:

node *root;
root = new node;

Now that root has been allocated some memory, it can be used. You can now set any value for root->income but you should remember to set root->next = NULL, at least initially. If you want to add another person's income, what you do is:

Code:

node *another;
another = new node;
another->income = xxx;
another->next = NULL;

root->next = another;

As it should now become apparent to you, as long as you keep the root, you can continually add another person's income to the end of the list, and it can keep growing, that is, until it hits the memory limit of your computer (which is quite difficult).

Removing a node from the whole list is quite troublesome though which I think you should really think about as it will be a good exercise for you to try.

Notice how this list is limited in the sense that you can only traverse it in one direction? This is why there is another type of container class called a doubly linked list, which can be traversed in any direction, as each node not only has a link to the next node, but also to the previous node.

The main disadvantage of the linked list is its lack of ability to be accessed at random, such as a normal array. This is why most programmers have a set of container classes they choose from, to meet their needs.

Hope this helps!

EDIT: beaten to the punch!

scuzzman · 12-28-2004, 09:32 AM

Ok - I've gotten most of it... but this one thing:
in this example:

Code:

IntNode *temp = head;

// Find the node right before the middlenode we want to delete
while (temp->next != middlenode)
{
     temp = temp->next;
}

// Re-link it around the middlenode we want to delete
temp->next = middlenode->next;

// Can now safely delete middlenode
delete middlenode;

At what point, and how, is middlenode initialized? all the nodea have the same identifier(s) don't they? How will the program know which one to delete?

deveraux83 · 12-28-2004, 09:44 AM

delete works on a portion of memory there delete will only deallocate the memory associated with middlenode since middlenode only points to that memory. This is all done internally, the details of which I have no idea about.

scuzzman · 12-28-2004, 10:27 AM

Thank you both for all your help

scuzzman · 12-28-2004, 10:39 AM

Ok - another question...
The code that the tutorial is supplying me is this:

Code:

#include <iostream>
using namespace std;

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

int main()
{
  node *root;       // This won't change, or we would lose the list in memory
  node *conductor;  // This will point to each node as it traverses the list

  root = new node;  // Sets it to actually point to something
  root->next = 0;   //  Otherwise it would not work well
  root->x = 12;
  conductor = root; // The conductor points to the first node
  if ( conductor != 0 ) {
    while ( conductor->next != 0)
      conductor = conductor->next;
  }
  conductor->next = new node;  // Creates a node at the end of the list
  conductor = conductor->next; // Points to that node
  conductor->next = 0;         // Prevents it from going any further
  conductor->x = 42;
}

Now - is it just me, or will that while loop always return FALSE - it will never get executed...

deiussum · 12-28-2004, 11:03 AM

Yeah, in my "middlenode" example, it was assumed that middlenode would be some unspecified node in the middle of the list. It also assumed that the pointer to middlenode would be == to one of the nodes in the linked list, which would be true so long as middlenode really was in the list... (Confused yet?)

For your other question about this part:

Code:

  if ( conductor != 0 ) {
    while ( conductor->next != 0)
      conductor = conductor->next;
  }

The part in the if is checking that conductor is not null. Then it checks if the node after conductor is not null, and if it isn't, it moves conductor down the list one node, continuing until it points to the last node in the list.

scuzzman · 12-30-2004, 10:52 PM

True, but it does this

Code:

root->next = 0;

and then this

Code:

conductor = root;

wouldn't that by default cause the while loop never to execute?

also - when your removing nodes from the middle of a linked list - do you just cavalierly remove them, or can you specify a node?

deiussum · 12-31-2004, 10:51 AM

Ok, I see what you are saying. In that particular case, yes, the while loop will not execute because the sample code only creates a single node up to that point. I think the sample code was showing you how you would iterate through to get to the end of any list, though...

In my example for removing a node from the middle of the list, the middlenode variable was meant to indicate some node in the middle that you specified. I guess I didn't make that as clear as I could have...