I plan to use a QuadTree for my terrain project i'm working on, and felt knowledge of this linked list stuff would be needed. I have a few ideas how to translate this into a QuadTree but if anyone could provide an hints that would be cool.

Not to deviate too much from the main topic, but the current structure that I use for creating a mesh is to have a vector for all the points in the terrain and then have another vector to store all the triangles, which store the indexs of the points. I can post it if that's not to clear.

anyway, here is my linked list code.

#include <iostream> #include <string> #include <vector> class Point3d { private: double x,y,z; // or double coord[3]; public: Point3d(double nx, double ny, double nz) : x(nz), y(ny), z(nz) { }; ~Point3d() {}; void setx(double nx) { x = nx; } void sety(double ny) { y = ny; } void setz(double nz) { z = nz; } double getx() { return x; } double gety() { return y; } double getz() { return z; } }; class Node { private: unsigned int pointindices[4]; // indices, but how to prevent duplication of point3d data? Node *child; public: Node() {}; ~Node() {}; void setindex(unsigned int arrayposition, unsigned int index) { //..... pointindices[arrayposition] = index; } void setchild(Node *nchild) { child = nchild; } unsigned int getindex(unsigned int arrayposition) { //..... return pointindices[arrayposition]; } Node *getChild() { return child; } }; class QuadTree { // basically a list for now. private: Node *head; // correct for list but what about quadtree? std::vector<Point3d> point3d; // a place to store points. /* Concerns of data duplication whilst subdividing to be added in Class QuadTree/private std::vector<BoundingBox> boundingbox; to be added in Class QuadTree/public // nw,ne,se,sw are index's for the point3d vector. void addboundingbox(int nw, int ne, int se, int sw) { boundingbox.push_back(BoundingBox(nw, ne, se, sw)); } to be added in Class Node replace pointindices[4] with unsigned int boundingboxindex; does this prevent point3d duplicates */ public: QuadTree() { head = NULL; }; ~QuadTree() {}; void Print(); void AppendBack (unsigned int arrayposition, unsigned int index); void AppendFront (unsigned int arrayposition, unsigned int index); void Delete(); }; void QuadTree::Print() { Node *tmp = head; // head was NULL so the list is empty if(tmp==NULL) { std::cout << "This list is empty" << std::endl; return; } // there is only one node present in the list if(tmp->getChild() ==NULL) { std::cout << "index: " << tmp->getindex(0) << std::endl; } else { while(tmp->getChild() !=NULL) { std::cout << "index: " << tmp->getindex(0) << std::endl; tmp = tmp->getChild(); } // child of the last node. if(tmp->getChild() ==NULL) { std::cout << "index: " << tmp->getindex(0) << std::endl; } } } void QuadTree::AppendBack(unsigned int arrayposition, unsigned int index) { // Create new node Node *newNode = new Node(); // constructor?? Node(.....); // To be moved to ^^/> constructor. newNode->setindex(arrayposition, index); newNode->setchild(NULL); // tmp Node *tmp = head; // head is NULL on 1st run; // Nodes already exist // if ignored on 1st run, move to else. if(tmp !=NULL) { // what is the point of this commented section // will it ever be true? /* while(tmp->getChild() !=NULL) { tmp = tmp->getChild(); } */ // Point last node to new node tmp->setchild(newNode); } else { head = newNode; } } void QuadTree::AppendFront(unsigned int arrayposition, unsigned int index) { // Create new node Node *newNode = new Node(); newNode->setindex(arrayposition, index); newNode->setchild(head); head = newNode; } int main() { QuadTree quadtree; quadtree.AppendBack(0,1); quadtree.AppendBack(0,2); quadtree.AppendFront(0,17); quadtree.Print(); std::string a; std::cin >> a; return (1); }