Archived

This topic is now archived and is closed to further replies.

Bad Sector

Linked Lists

Recommended Posts

I''m having a bit of a problem with these things. I understand pointers and dynamic allocation, but not linked lists. I was looking at a bit of code where a for loop is used to fill in a list of 10. I just don''t quite see how the list gets filled without overwriting itself. I realize that this is a fairly simple idea, and once I get an understanding of exactly how a list is built I think I''ll get it. So, if someone could explain just what''s happening in the creation of a linked list, I would appreciate it. By the way, I searched the archives before posting this, but I didn''t find anything that really explained the underlying processes. Thanks, Bad Sector

Share this post


Link to post
Share on other sites
A google search will certainly yield good results...

An array stores its elements contiguously in memory, so when you are at element 12, and you want to go to element 13, it''s simple; pointer = pointer + sizeof(element)

With lists, the elements are scattered throughout memory, and each element holds the address of the next one (in a pointer). So, to go to element 13, you have to start at element 0, follow the pointer it contains to element 1. Then, follow the pointer from element 1 to element 2, etc...

Elements of a list contain both data and a pointer to the next element. That''s a crucial point. Elements in an array contain only pertinent data.

HTH,

Cédric

Share this post


Link to post
Share on other sites
http://www.inversereality.org/tutorials/c++/linkedlists.html

or one of the other thousands of pages you can find on google.

To give you a simple idea, with completely fake numbers:

Take the following linked list (this is about as simple as you can get it (not following ANSI C):


    

struct information
{
// stuff goes here

}

struct node
{
information* myinformation;
node* next;

List()
{
next=NULL;
information=NULL;
}

};

// somewhere in code

node* mylinkedlist = new node();

/**************************************************
Here, information points to the memory 0x00000000.
next points to the memory 0x00000000.
Let's say mylinkedlist points
to the memory 0x00903fd8

If you
don't initialize your pointers, they're going
to point to some memory location, which is
dependant on OS, the compiler, etc.
**************************************************/

// you want to add something

function add(node* mylinkedlist, information myinformation)
{
// mylinkedlist is the linked list
// you want to add information to it.
node* searchnode = NULL;
node* tempnode = new node();

/**************************************************
Here, information points to the memory 0x00000000.
next points to the memory 0x00000000.
Let's say tempnode points
to the memory 0x00904530
**************************************************/

tempnode->myinformation = myinformation;

/**************************************************
Here, information points to the memory 0x00903d10.
next points to the memory 0x0000000.
Let's say tempnode points
to the memory 0x00904530
**************************************************/
for(searchnode = mylinkedlist; searchnode != NULL;
searchnode = searchnode->next)
{
if(searchnode->next == NULL)
{
searchnode->next = tempnode;
break;
}
}

/**************************************************
Here, information points to the memory 0x00000000.
next points to the memory 0x00904530.
searchnode points to the memory 0x00903fd8
**************************************************/

}


Basically, a linked list as simple as you can get it, contains at least data element (although you don't need to include one, you can just have a pointer to the next element, but that makes it incredibly stupid), and a pointer to the next element.

As long as you don't overwrite the actual pointer to the head of the linked list, it won't be overwritten.

The head of the example was mylinkedlist. searchnode was also a pointer to the head, BUT, it can be changed. If you changed the information in searchnode->information, the first node in the linked list would also be changed, because the memory would be overwritten.

Now, lets handle a bit more complex of an example

searchnode = mylinkedlist;
delete searchnode;
searchnode = NULL;

since searchnode is just a pointer, it now points to the memory address of 0x00000000.

But before you set it to NULL, you deleted it. Since at that time, searchnode pointed to the same memory address as mylinkedlist, you also deleted mylinkedlist.

But when you set searchnode to NULL, mylinkedlist stayed at the same memory address. Let's say 0xcdcdcdcd.

[edited by - Nytegard on August 13, 2002 10:45:38 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Bad Sector
I''m having a bit of a problem with these things. I understand pointers and dynamic allocation, but not linked lists. I was looking at a bit of code where a for loop is used to fill in a list of 10. I just don''t quite see how the list gets filled without overwriting itself. I realize that this is a fairly simple idea, and once I get an understanding of exactly how a list is built I think I''ll get it. So, if someone could explain just what''s happening in the creation of a linked list, I would appreciate it. By the way, I searched the archives before posting this, but I didn''t find anything that really explained the underlying processes.

Thanks,
Bad Sector


The only I can recommend is search and read the "resource files explained" and the "Stack em,Rack em, and pack em" (or something to that effect) articles in articles and resources section. They might be intedended for something else but the linked list concept is included.

Share this post


Link to post
Share on other sites
Basically, each object in the list is given it''s own memory on creation (before entry to the list). This is usually done with malloc(sizeof(object)). Once this is done, the object can be added to the list.

Every linked-list object has one or two (more useful) pointers dealing with the list: "next member" and "previous member". If it has two it is called doubly-linked.

There are also (unless the list is circular) two pointers to the list, contained inside whatever holds the linked list. These pointers are "first member" and "last member", and are equal to NULL if the list is empty.

Objects can be added and removed from either end quickly. If the list is doubly-linked, objects can be removed from anywhere just as quickly.

To add an object to the end of a linked list with objects in it you must do 3 things:

Firstly, the current "last member" will become second-to-last, so it''s "next member" must be set to the new member which is about to become the last member.

Secondly (Only in the case of doubly-linked lists), the new member''s "previous member" must be set to the current "last member", or new second-to-last member.

Finally, the "last member" must be set to the address of the new object, since it is now last.

So only 3 things changed, no objects were created (except for the one which was just added), deleted or overwritten.

If the linked list was empty to start with, the new member is both the "first member" and the "last member", and it''s "previous member" and "next member" don''t exist, or are NULL.


PS: This probably belongs in the beginner section. And you should''ve searched the web. There are many useful sites about this stuff.

Share this post


Link to post
Share on other sites