Jump to content
  • Advertisement

Archived

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

Yanroy

Linked List that looks like an Array

This topic is 6929 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

I am working on a class that works like an array buy is really a linked list. I have attempted to overload the [] operators. Somehow that doesn''t work very well I have ended up with this ugly thing:
DynamicArray MyDArray;
MyDArray.SetIndex(0, 23);
 
Little better than an ordinary linked list, and twice as slow. Any ideas on at least getting it to this point?
MyDArray.Index(0) = 23;
 
My ultimate goal, which I now belive to be impossible, is to use it like a normal array. I would even settle for the following:
MyDArray(0) = 23;
 
For some reason I do not have a lot of luck dealing with operator overloading (even when I compile the example on the CD that came with my intro to C++ book it doesn''t work). --------------------

You are not a real programmer until you end all your sentences with semicolons;

Yanroy@usa.com

Visit the ROAD Programming Website for more programming help.

Share this post


Link to post
Share on other sites
Advertisement
Some sample code. It compiled under MSVC 6.

class ArrayLikeList {
protected:
class Node {
public:
int data;
Node * next;
Node(int somedata) { data = somedata; next = NULL; }
};
Node * head;
Node * tail;
public:
ArrayLikeList() { head = NULL; }
int& operator[](int n);
void InsertEnd(int i) {
if (head == NULL) {
head = new Node(i);
tail = head;
} else {
Node * temp = new Node(i);
tail->next = temp;
tail = temp;
}
}
};

int & ArrayLikeList::operator[](int n) {
Node * ptr = head;
for (int i = 0; i < n; i++) {
if (ptr != NULL) ptr = ptr->next;
}
if (ptr != NULL) return ptr->data;
else return tail->data;
}

int main() {
ArrayLikeList a;
a.InsertEnd(4);
a.InsertEnd(5);
a.InsertEnd(6);

printf("%d\n", a[0]);
printf("%d\n", a[1]);
printf("%d\n", a[2]);
return 0;
}

Share this post


Link to post
Share on other sites
quote:
Original post by JonatanHedborg

Ok, what IS a linked list?

i know i should know but...

========================
Game project(s):
www.fiend.cjb.net



struct linkedlist
{
MYTYPE myData;
struct linkedlist *next;
};


In a linked list each element can be everywhere in memory, but each element excepts the last one has a pointer to the next one.

Yanroy, I think it's no good idea to handle a linked list like you do. Imagine you have to modify each element of the list. You probably would do it like this:

for(int i=0;i{
DotheOperation(MyDArray.Index(i));
}

The adress of the list element must be found again each time which costs time. It would be better to have a walk-through list function like DynamicArray::WalkThrough(void (*ptr_to_function)(MYTYPE *data)).

Visit our homepage: www.rarebyte.de.st

GA

Edited by - ga on 5/5/00 10:46:36 AM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This is from Bjarne Stroustrup''s "The C++ Programming Language", 3 ed., chapter 11.8 Operator Overloading: Subscripting

This is an example of a class that uses an overloaded [] operator. Its not a linked list, but the ideas can be applied to a linked list class.


class Assoc {
struct Pair {
string name;
double val;
Pair(string n = "", double v = 0) : name(n), val(v) {}
};
vector vec;

Assoc(const Assoc&); // private to prevent copying
Assoc& operator=(const Assoc&);
public:
Assoc() {}
double& operator[](const string&);
void print_all() const;
};

double& Assoc::operator[](const string& s)
{
for(vector::const_iterator p = vec.begin(); p!=vec.end(); ++p)
if(s==p->name) return p->val;

vec.push_back(Pair(s,0));

return vec.back().val;
}

void Assoc::print_all() const
{
for(vector::const_iterator p=vec.begin(); p!=vec.end(); ++p)
cout << p->name << ": " << p->val << ''\n'';
}

void main()
{
string buf;
Assoc vec;
while(cin>>buf) vec[buf]++;
vec.print_all();
}



Share this post


Link to post
Share on other sites
Guest Anonymous Poster
oops... everytime in the above code you see "vector" it should be a vector template with the Pair struct as the first parameter.

Share this post


Link to post
Share on other sites
Re: SiCrane

Awesome job! Did you have that laying around or did you just type that in?

Mind if I steal it?

Share this post


Link to post
Share on other sites
I actually recently implemented linked lists in an array (two actually) for a data structures class. The way I did it was to have two arrays (or a two-column multidimensional array) and one holds the data and the other holds the index number of the next "node" in the list.

This is a really simple way to do it, but it should work fairly quickly.

Share this post


Link to post
Share on other sites
Ok, so is this correct?

struct test
{
int number; //Test
test *next;
};

and then:

test data;

data.next=malloc(whatever);
data.next[n].number;

how would you btw. add "links" later? can u just malloc more memory or how do u do it?

data.next=malloc(sizeof(test));
data.next[0].number=1;
data.next=malloc(sizeof(test)); // do they "add up"
data.next[1].numer=2;


would the above stuff work? sorry if it look stupid btw...







========================
Game project(s):
www.fiend.cjb.net

Share this post


Link to post
Share on other sites
If you want to allocate memory for something at run time and access the elements in an array like fashion then you can also do this.


int *array, numElements;

numElements = 10;

array = (int *)malloc(sizeof(int)*numElements);

// to access an element just do this
array[3] = 20;


To utilise a multidimensional array style do this.


int **array;
int numRows = 10;
int numColumns = 10;

array = (int **)malloc(sizeof(int *)*numRows);

for(int i = 0; i < numRows; i++)
array[ i ] = (int *)malloc(sizeof(int)*numColumns);

array[3][6] = 34;


Edited by - Chris F on 5/5/00 2:51:32 PM

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!