[C++] Array of Linked lists Help

[saiz66]

Hi. I need to create an array where each index holds a bunch of linked lists. I have attached a picture to show what I mean. Should I create this as a class?

[bithub]

std::list<int> listArray[10];

That create an array with 10 indexes. Each array contains a linked-list of integers. No need for a class :)

[saiz66]

wow. thanks a lot. I have a really dumb question. How do I use the list? Could somebody just give me some examples on how to insert items into the indexes? Thanks in advance!

Edited August 4, 2004 by saiz66

[Etc.]

Create an array of pointers, then make each index of the array point to the head of each linked list.

[bithub]

For my example, just do this:

listArray[0].push_back(6);

[bithub]

Guess I should add that to use the stl list, you need to include the proper header:

#include <list>

[saiz66]

thanks a lot to both of u...

[Genesi]

Saw this by seaching google check it out:

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

[saiz66]

thanks Genesi! I saved that, it looks to be very helpful.

I used this declaration: std::list<int> listArray[10];

Now how do I send this to a function as a reference? b/c I want the original to change from the new function. Thanks!

[Genesi]

HeHe somebody esle will have to help you with that. I'm still trying to master the basics. Tried jumping to heavy into the language before and all it did was make things more confusing But I still know how to find answer er umm help when I need them.

[bwx]

  saiz66 said:

thanks Genesi!  I saved that, it looks to be very helpful. 

I used this declaration:  std::list<int> listArray[10]; 

Now how do I send this to a function as a reference? b/c I want the original to change from the new function.  Thanks!

void f (std::list<int>* myList)
{
 ? ?myList[0].push_back( /* something */ );
}

Hope that helps.

[saiz66]

thanks bwx, but why do you use *? I am kind of confused, I thought you used & for reference.

[Genesi]

If I'm correct its because its an argument so you want the value not the actual address you need to use the defrencing operator.

[bwx]

  saiz66 said:

thanks bwx, but why do you use *? I am kind of confused, I thought you used & for reference.

I used a pointer because you can't really pass an array as a reference (since an array is implicitly a pointer). The other way you could do it is by using vector objects, but you said you haven't learned that yet so I'll leave that alone.

Hope that helps.

[saiz66]

thanks bwx for the reply, are arrays the only thing u cant use as a reference or are there any others?

Also how can I print all the elments from the list?

Edited August 9, 2004 by saiz66

[bithub]

  Quote

you can't really pass an array as a reference

actually...

void function(int (&arr)[5])

Granted, there really isnt any reason to pass an array by reference since it will act the same as passing it by value.

[bwx]

  saiz66 said:

thanks bwx for the reply, are arrays the only thing u cant use as a reference or are there any others?

It's not so much that you can't pass arrays by reference, it's just that you can't pass them without pointers. Not unless you want to do some ugly hacking.

  saiz66 said:

Also how can I print all the elments from the list?

To get the value's stored in an std::list, you have to use iterators.

Here's an example:

#include <iostream>
#include <list>

int main (int argc, char **argv)
{
    std::list<int> intList;
    // insert some random numbers into the list
    intList.push_back(1);
    intList.push_back(5);
    intList.push_back(2);
    intList.push_back(4);

    // declare an iterator to iterate through the list and set it to the first element
    std::list<int>::iterator it = intList.begin();

    while (it != intList.end())
    {
        // Currently, 'it' acts as the index. When you dereference 'it', you get the value
        // contained at that index
        std::cout << *it << std::endl;

        // Increment the iterator to the next element
        ++it;
    }
    return 0;
}

I commented it the best I could. However, iterators may be a confusing topic so let me know if you don't understand anything.

  bithub said:

actually...

void function(int (&arr)[5])

Granted, there really isnt any reason to pass an array by reference since it will act the same as passing it by value.

Well the array notation in the argument implicitly implies a pointer. All you're doing is passing the actual pointer as a reference. There are reasons to pass an array as a reference but they are very rare. The only reason I can think of is to modify the address pointed to by the pointer you're passing in to the function. For example if you're writing a function to free a block of memory, then zero out the pointer that was just deleted, you could pass the pointer as a reference and set it to zero from within the function and it will retain it's value when the function returns.

I hope that helps.

[saiz66]

thnx so much for all the help... i am not sure why there is a need for an iterator.

[bwx]

  saiz66 said:

thnx so much for all the help... i am not sure why there is a need for an iterator.

To know why, you have to have some understanding on how linked lists are actually implemented. A linked list is usually a link of structures (can be classes as well) which contain a data variable and a pointer which points to the next element in the linked list. There are also bi-directional linked lists in which each link in the linked list also contains a pointer to the previous link therefore allowing you to go backwards aswell. Now that we're clear on what a linked list is, it is pretty obvious why it requires an iterator. When you first declare an iterator and assign it to the first element in the linked list, that first element has the pointer to the next element. When you increment it, the std::list class internally gets the address of the next link in the linked list through the first element's structure. It keeps doing the same thing with each link in the list until you reach the end. If std::list implemented a method to extract values from the linked list, it would have to iterate the whole list up to the index you specified everytime you requested a value, which is needless to say, rather inefficient.

I know all this is confusing, but it gets better as you go. The key to succeeding in programming is practice. ;)

I hope that helps.

[saiz66]

yup.. it makes more sense now... I am used to the linked list that we build ourselves. The one where you have a temporary pointer and stuff to traverse through the list. I didn't feel like building my own and thought to use the List from the library. thanks again, much appreciated!!!

[saiz66]

Also, how would I make it so that when I am passing the array of linked list it won't be changed inside the fucntion? Adding a const infront?

[Genesi]

  saiz66 said:

Also, how would I make it so that when I am passing the array of linked list it won't be changed inside the fucntion? Adding a const infront?

Correct. Placing const will tell the complier that the values are not to be changed. If any attempt by your compiler trys to change them then you will get a error message.

[saiz66]

Thanks Genesi! I have a problem. I am trying to pass an array of linked list and I have it set as const such as

const list<int>* outstandingRequest

so that it won't change the array of linked lists. But I get an error in this part of the code:

list<int>::iterator it = outstandingRequests[i].begin();

Is that because, it is changing the code?

The error is:

  Quote

error C2440: 'initializing' : cannot convert from 'class std::list<int,class std::allocator<int> >::const_iterator' to 'class st

[Genesi]

Heh, I just know about consts and what they do. Not going to touch the STL until I know I'm ready. Oogle will have to help you with that.

[bwx]

  saiz66 said:

Thanks Genesi!? I have a problem.? I am trying to pass an array of linked list and I have it set as const such as

const list<int>* outstandingRequest

so that it won't change the array of linked lists.? But I get an error in this part of the code:

list<int>::iterator it = outstandingRequests[i].begin();

Is that because, it is changing the code?

The error is:

Since you're passing it as 'const', the array of lists is unchangeable while the iterator you're requesting is not.

Change

list<int>::iterator it = outstandingRequests[i].begin();

into

list<int>::const_iterator it = outstandingRequests[i].begin();

and it'll work fine.

Hope that helps.

[Genesi]

  bwx said:

Since you're passing it as 'const', the array of lists is unchangeable while the iterator you're requesting is not.

Change

list<int>::iterator it = outstandingRequests[i].begin();

into

list<int>::const_iterator it = outstandingRequests[i].begin();

and it'll work fine.

Hope that helps.

Thats what I meant to say. :p