Indexing my linked list
Author
Feel such a beginner about this one.. I want to create an index for linked list items, then access the item to draw it, without searching through the list. So I guess I need member functions Create_Index and Get_Indexed_Item(i). Now comes the best part.. I don't know how to code them:)
Here is the list code I have managed to do, it's not the current version but you can see the style of the list and probably help me write those functions..
Linked list code
Unfortunately, you can't do it without some heavy modifications if you want constant time access like that. The only way I can think of to do it (dodgy) is allocate a single block of memory to store the entire list in, then (assuming S_Tile is of fixed size) you could multiply the sizeof your node by the index number you want to access into a node pointer.
If you want constant time access like that, you might want to consider std::map.
If you want constant time access like that, you might want to consider std::map.
I wrote 2 classes for lists, one for a linked list, and one for a dynamic array. It's much better to use a dynamic array for this type of problem, since you can access the items with an index without any more a performance hit than a normal array, and any hack you can come up with a linked list (like storing a dynamic array to store it's indices) will only add over-head, and have more a performance hit.
This is a dynamic array class.You set the size using array_var.SetSize() and access individual items as array_var[index].It includes limit checks.
This same thing can be applied to a two-way linked list.You will need a int to store the last accesed item and next time another var has to be got out of the list move the pointer forward or backward by the diffrence from the last item accessed.
Helps? - ask if you have any questions [smile]
/*Author:Aaron (a.k.a FireNet)Web:http://xlock.hostcubix.com*/#ifndef _ARRAY_CONTAINER_H_#define _ARRAY_CONTAINER_H_template <class Type>class ArrayContainer{ public: bool SetSize(int); //Set the size of the array inline Type & operator [] (int); //Easy access to individual items inline operator int(); ArrayContainer(); //Constructor ~ArrayContainer(); //Destructor private: int array_size; //Size of the Array Type *data; //Array pointer};template <class Type>Type & ArrayContainer<Type>::operator [] (int loc){ if(loc<array_size && loc > -1)return data[loc]; //Data Index within range,return val else return data[loc%array_size]; //Data Index out of range,return modulus of val}template <class Type>ArrayContainer<Type>::operator int(){ return array_size; //Return size of array}template <class Type>bool ArrayContainer<Type>::SetSize(int size) //Create An array of size{ //cout<<"ArrayContainer : "<<"SetSize("<<size<<")"; if(array_size)delete[] data; data = NULL; array_size = size; data = new Type[array_size]; if(data == NULL )return false; else return true;}template <class Type>ArrayContainer<Type>::~ArrayContainer(){ //cout<<"ArrayContainer : "<<"Destructor"; if(array_size)delete[] data;}template <class Type>ArrayContainer<Type>::ArrayContainer(){ //cout<<"ArrayContainer"<<"Constructor"; array_size = 0; data = NULL;}#endifThis same thing can be applied to a two-way linked list.You will need a int to store the last accesed item and next time another var has to be got out of the list move the pointer forward or backward by the diffrence from the last item accessed.
Helps? - ask if you have any questions [smile]
Why are you writing your own list for? the standard library already has very efficent list and for dynamic arrays there is vector.
Now your problem about indexing into list, to simulate something like this with the standard library list you std::advance e.g.:
#include
#include
#include
#include
#include
int main() {
typedef std::list lint;
lint li;
std::generate_n(std::back_inserter(li), 30, rand);
lint::const_iterator itr = li.begin();
std::copy(li.begin(), li.end(),
std::ostream_iterator(std::cout, ", "));
std::advance(itr, 5); //
Now your problem about indexing into list, to simulate something like this with the standard library list you std::advance e.g.:
#include
#include
#include
#include
#include
int main() {
typedef std::list lint;
lint li;
std::generate_n(std::back_inserter(li), 30, rand);
lint::const_iterator itr = li.begin();
std::copy(li.begin(), li.end(),
std::ostream_iterator(std::cout, ", "));
std::advance(itr, 5); //
Quote:Original post by Anonymous Poster
Why are you writing your own list for? the standard library already has very efficent list and for dynamic arrays there is vector.
Now your problem about indexing into list, to simulate something like this with the standard library list you std::advance e.g.:
#include
#include
#include
#include
#include
int main() {
typedef std::list lint;
lint li;
std::generate_n(std::back_inserter(li), 30, rand);
std::copy(li.begin(), li.end(),
std::ostream_iterator(std::cout, ", "));
lint::const_iterator itr = li.begin();
std::advance(itr, 5); //
Well that was me, and it didn't display correctly it was mean't to be:
#include <cmath>#include <iterator>#include <algorithm>#include <list>#include <iostream>int main() { typedef std::list<int> lint; lint li; std::generate_n(std::back_inserter(li), 30, rand); std::copy(li.begin(), li.end(), std::ostream_iterator<int>(std::cout, ", ")); lint::const_iterator itr = li.begin(); std::advance(itr, 5); //<- move to position 5 std::cout << "\n\nElement at index 5: " << *itr << std::endl;}
Author
Forgot to mention that I wanted only a "snapshot" of the list without doing any list operations while accessing the indexed version. I wrote some code which seems to work. These are the changes I made:
And also allocating indexed_tiles to amount of max_nodes.
//linked list index nodestruct S_Index{ S_Tile *index_tile_p;};class S_List{ S_Index *indexed_tiles; public: S_Tile *Get_Indexed_Item(int i) { return indexed_tiles.index_tile_p; }void Build_Index();};void S_List::Build_Index(){ S_List_Node *next=list_anchor; int i=0; while (next!=NULL) { indexed_tiles[i++].index_tile_p=next->tile_p; next=next->next_id; }}And also allocating indexed_tiles to amount of max_nodes.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
