Sign in to follow this  

Indexing my linked list

This topic is 4813 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.


/*
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;
}

#endif







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]

Share this post


Link to post
Share on other sites
Guest 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);

lint::const_iterator itr = li.begin();

std::copy(li.begin(), li.end(),
std::ostream_iterator(std::cout, ", "));

std::advance(itr, 5); //

Share this post


Link to post
Share on other sites
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;

}

Share this post


Link to post
Share on other sites
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:


//linked list index node
struct 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[i].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.

Share this post


Link to post
Share on other sites

This topic is 4813 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this