LinuxQuestions.org
LinuxAnswers - the LQ Linux tutorial section.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 12-28-2004, 08:21 AM   #1
scuzzman
Senior Member
 
Registered: May 2004
Location: Hilliard, Ohio, USA
Distribution: Slackware, Kubuntu
Posts: 1,851

Rep: Reputation: 47
Linked Lists - What and Why?


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++.
 
Old 12-28-2004, 08:51 AM   #2
deiussum
Member
 
Registered: Aug 2003
Location: Santa Clara, CA
Distribution: Slackware
Posts: 895

Rep: Reputation: 31
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...

Last edited by deiussum; 12-28-2004 at 08:56 AM.
 
Old 12-28-2004, 08:59 AM   #3
deveraux83
Member
 
Registered: Jul 2003
Location: Malaysia
Distribution: Red Hat, Slackware 9.1
Posts: 76

Rep: Reputation: 15
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!
 
Old 12-28-2004, 09:32 AM   #4
scuzzman
Senior Member
 
Registered: May 2004
Location: Hilliard, Ohio, USA
Distribution: Slackware, Kubuntu
Posts: 1,851

Original Poster
Rep: Reputation: 47
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?
 
Old 12-28-2004, 09:44 AM   #5
deveraux83
Member
 
Registered: Jul 2003
Location: Malaysia
Distribution: Red Hat, Slackware 9.1
Posts: 76

Rep: Reputation: 15
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.
 
Old 12-28-2004, 10:27 AM   #6
scuzzman
Senior Member
 
Registered: May 2004
Location: Hilliard, Ohio, USA
Distribution: Slackware, Kubuntu
Posts: 1,851

Original Poster
Rep: Reputation: 47
Thank you both for all your help
 
Old 12-28-2004, 10:39 AM   #7
scuzzman
Senior Member
 
Registered: May 2004
Location: Hilliard, Ohio, USA
Distribution: Slackware, Kubuntu
Posts: 1,851

Original Poster
Rep: Reputation: 47
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...
 
Old 12-28-2004, 11:03 AM   #8
deiussum
Member
 
Registered: Aug 2003
Location: Santa Clara, CA
Distribution: Slackware
Posts: 895

Rep: Reputation: 31
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.
 
Old 12-30-2004, 10:52 PM   #9
scuzzman
Senior Member
 
Registered: May 2004
Location: Hilliard, Ohio, USA
Distribution: Slackware, Kubuntu
Posts: 1,851

Original Poster
Rep: Reputation: 47
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?
 
Old 12-31-2004, 10:51 AM   #10
deiussum
Member
 
Registered: Aug 2003
Location: Santa Clara, CA
Distribution: Slackware
Posts: 895

Rep: Reputation: 31
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...
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Linked Lists and Queues Kroenecker Programming 2 04-09-2005 01:59 AM
Linked Lists leonidg Programming 7 03-10-2005 02:07 AM
queue and linked lists Palamides Programming 2 03-09-2005 08:08 PM
c++ doubly linked lists durden2.0 Programming 4 02-25-2004 05:56 PM
c++ linked lists jclark00001 Programming 10 02-23-2003 02:40 PM


All times are GMT -5. The time now is 12:16 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration