Back to General and Gameplay Programming

Linked List that looks like an Array

General and Gameplay Programming Programming

Started by Yanroy May 05, 2000 09:50 AM

13 comments, last by Yanroy 23 years, 11 months ago

Yanroy

122

Author

May 05, 2000 09:50 AM

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.

--------------------

You are not a real programmer until you end all your sentences with semicolons; (c) 2000 ROAD Programming
You are unique. Just like everybody else.
"Mechanical engineers design weapons; civil engineers design targets."
"Sensitivity is adjustable, so you can set it to detect elephants and other small creatures." -- Product Description for a vibration sensor

Yanroy@usa.com

JonatanHedborg

122

May 05, 2000 09:57 AM

Ok, what IS a linked list?

i know i should know but...

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

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

SiCrane

11,840

May 05, 2000 10:35 AM

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

126

May 05, 2000 10:43 AM

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

Visit our homepage: www.rarebyte.de.stGA

Anonymous

May 05, 2000 11:37 AM

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();}

Anonymous

May 05, 2000 11:42 AM

oops... everytime in the above code you see "vector" it should be a vector template with the Pair struct as the first parameter.

Buster

100

May 05, 2000 11:56 AM

Re: SiCrane

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

Mind if I steal it?

Washizu

122

May 05, 2000 12:08 PM

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.

JonatanHedborg

122

May 05, 2000 12:09 PM

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

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

Chris F

122

May 05, 2000 02:49 PM

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 thisarray[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 = (int *)malloc(sizeof(int)*numColumns);<br><br>array[3][6] = 34;<br>  </pre> <br><br>Edited by - Chris F on 5/5/00 2:51:32 PM

"I have realised that maths can explain everything. How it can is unimportant, I want to know why." -Me

Linked List that looks like an Array

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Linked List that looks like an Array

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines