looking for linked list help/advice
January 14, 2003 10:37 AM
hi,
im new to linked lists, and the book i have been using to learn c++ only has a simple linked list example, which doesnt support deletion of individual objects, only deleting of the entire list at once.
//-----simplified to reduce post length
class ball
{
public:
int get_xPos()const {return xPos;}
//etc
private:
int xPos;
//etc
};
//-----hopefully this should help explain what i need to do
i need the ability to add new objects to the list (position in list unimportant), and be able to traverse the list to call member functions of each object in turn, and delete the objects based upon the return of the functions, if xPos < 0 then delete the object etc.
i tried to look up stl lists but didnt have to much success due to the fact that all the tutorials i found used lists of integers and not lists of objects / lists of pointers to objects (is this even possible ?)
if anyone can point me to some good examples/tutorials of linked list with similar functionality to that i require or offer any other assistance i would be very greatfull.
thanx for taking the time to read.
[edited by - bobob on January 14, 2003 11:52:28 AM]
1,284
January 14, 2003 12:25 PM
The book I''m currently reading, Data Structures for Game Programmers, covers both single and double linked lists in detail.
pan narrans
Study + Hard Work + Loud Profanity = Good Code
pan narrans
Study + Hard Work + Loud Profanity = Good Code
Minister of Propaganda : leighstringer.com : Nobody likes the man who brings bad news - Sophocles (496 BC - 406 BC), Antigone
January 14, 2003 12:34 PM
hi there, i worked on a really nice templated doubly linked list that offers all the features you''re looking for, plus it can be populated with any data type (object or otherwise)... feel free to take it and call it your own.
i hope that turns out legible...
so in use, you''d simply instantiate a list via
CLinkedList<class ball> BallList;
and boom... you have a linked list of type ball. (actually, i''m not sure if that''s the CORRECT syntax, it''s been awhile since i''ve used templates, but it''s similar).
Hope this helps you out.
// FILENAME : CLinkedList.h// AUTHOR : Dennis Hubley// CREATED : July 25, 2002// UPDATED : July 25, 2002// DESCRIPTION : This is the CLinkedList class declaration. CLinkedList// contains the class CNode which contains the type injected// data.#ifndef CLINKEDLIST_H#define CLINKEDLIST_H// CLASS DECLARATIONtemplate<class T>class CLinkedList{ protected: class CNode // CNode stores the actual { // data which is type injected friend CLinkedList; // when the user instantiates // CLinkedList. private: CNode *next; // Link to next node in list CNode *prev; // Link to previous node in list public: T data; // The data of type < T > }; private: CNode *head; // Linked list head CNode *tail; // Linked list tail public: CLinkedList(); // Constructor ~CLinkedList(); // Deconstructor void InsertBeforeHead(T new_data); // Inserts record before head void InsertAfterHead(T new_data); // Inserts record after head void InsertBeforeTail(T new_data); // Inserts record before tail void InsertAfterTail(T new_data); // Inserts record before tail void Clear(); // Removes all data from list T GetHead() { return head->data; } // Data at head of list T GetTail() { return tail->data; } // Data at tail of list CNode *current; // Current place in the list};#endif// END OF FILE - CLinkedList.h// FILENAME : CLinkedList.cpp// AUTHOR : Dennis Hubley// CREATED : July 25, 2002// UPDATED : July 25, 2002// DESCRIPTION : This is the CLinkedList class definition. CLinkedList// contains the class CNode which contains the type injected// data.// INCLUDES#include "CLinkedList.h"// CLASS DEFINITIONtemplate<class T>CLinkedList<T>::CLinkedList():head(NULL),tail(NULL),current(NULL){}template<class T>void CLinkedList<T>::InsertBeforeHead(T new_data) // Insert new node before head{ if(head == NULL) // If list is empty { head = new CNode; // Allocate memory for the head head->data = new_data; // Store the data in the head head->next = NULL; // Set the next link to NULL head->prev = NULL; // Set the previous link to NULL tail = new CNode; // Allocate memory for the tail tail->data = new_data; // Store the data in the tail tail->next = NULL; // Set the next link to NULL tail->prev = NULL; // Set the previous link to NULL return; } else if(head->next == NULL) // If the list "only contains one node" { head->next = tail; // The head node points at the tail node tail->prev = head; // The tail node points at the head node head->data = new_data; // Store the data in the head return; } // The list is two nodes in size so we create an empty node CNode *node = new CNode; // Insert the node before head node->data = new_data; node->next = head; node->prev = NULL; head->prev = node; head = node; return;}template<class T>void CLinkedList<T>::InsertAfterHead(T new_data) // Insert new node after head{ if(head == NULL) // If list is empty { head = new CNode; // Allocate memory for the head head->data = new_data; // Store the data in the head head->next = NULL; // Set the next link to NULL head->prev = NULL; // Set the previous link to NULL tail = new CNode; // Allocate memory for the tail tail->data = new_data; // Store the data in the tail tail->next = NULL; // Set the next link to NULL tail->prev = NULL; // Set the previous link to NULL return; } else if(head->next == NULL) // If the list "only contains one node" { head->next = tail; // The head node points at the tail node tail->prev = head; // The tail node points at the head node tail->data = new_data; // Store the data in the tail return; } // The list is two nodes in size so we create an empty node CNode *node = new CNode; // Insert the node between head and head->next node->data = new_data; node->next = head->next; node->prev = head; head->next->prev = node; head->next = node; return;}template<class T>void CLinkedList<T>::InsertBeforeTail(T new_data) // Insert new node before tail{ if(head == NULL) // If list is empty { head = new CNode; // Allocate memory for the head head->data = new_data; // Store the data in the head head->next = NULL; // Set the next link to NULL head->prev = NULL; // Set the previous link to NULL tail = new CNode; // Allocate memory for the tail tail->data = new_data; // Store the data in the tail tail->next = NULL; // Set the next link to NULL tail->prev = NULL; // Set the previous link to NULL return; } else if(head->next == NULL) // If the list "only contains one node" { head->next = tail; // The head node points at the tail node tail->prev = head; // The tail node points at the head node head->data = new_data; // Store the data in the head return; } // The list is two nodes in size so we create an empty node CNode *node = new CNode; // Insert the node before tail node->data = new_data; // Store data in node tail->prev->next = node; // Set tail prev->next to node node->prev = tail->prev; // Set node->prev to tail prev node->next = tail; // Set node->next to tail tail->prev = node; // Set tail prev to node return; // Node is now before tail}template<class T>void CLinkedList<T>::InsertAfterTail(T new_data) // Insert new node after tail{ if(head == NULL) // If list is empty { head = new CNode; // Allocate memory for the head head->data = new_data; // Store the data in the head head->next = NULL; // Set the next link to NULL head->prev = NULL; // Set the previous link to NULL tail = new CNode; // Allocate memory for the tail tail->data = new_data; // Store the data in the tail tail->next = NULL; // Set the next link to NULL tail->prev = NULL; // Set the previous link to NULL return; } else if(head->next == NULL) // If the list "only contains one node" { head->next = tail; // The head node points at the tail node tail->prev = head; // The tail node points at the head node tail->data = new_data; // Store the data in the tail return; } // The list is two nodes in size so we create an empty node CNode *node = new CNode; // Insert the node after tail node->data = new_data; // Store the data in the node node->next = NULL; // Node is now tail so next is NULL node->prev = tail; // Node prev links with tail tail->next = node; // Tail next links with node tail = node; // Move tail to node return; // Node is now after tail}template<class T>void CLinkedList<T>::Clear(){ current = head; // Set current to the front of the list while(current != NULL) { CNode *temp = current; // Create a temp node current = current->next;// Move to the next node on the list delete temp; // Free the memory } head = tail = NULL; // Set everything to NULL}// The Deconstructor -- Free all memory associated with the listtemplate<class T>CLinkedList<T>::~CLinkedList() { Clear(); }// END OF FILE - CLinkedList.cpp i hope that turns out legible...
so in use, you''d simply instantiate a list via
CLinkedList<class ball> BallList;
and boom... you have a linked list of type ball. (actually, i''m not sure if that''s the CORRECT syntax, it''s been awhile since i''ve used templates, but it''s similar).
Hope this helps you out.
122
January 14, 2003 06:58 PM
I''ll give you some tips that that I''ve picked up over the years on linked lists.
First, if you don''t already, try drawing a sample list on paper
with just a few nodes represented by boxes and arrows for connections. That helped me a lot when I started learning them and even now I do that when I need to figure out how to, for instance, insert between two nodes, or whatever. Just keep track of how you change the arrows, and especially in what order, to know how to change the pointers.
Second, if order is not important, then its much easier. Easiest is probably to always insert at the end (you can have a pointer to the last node to help, just be sure to update it to then point to this new node). Otherwise at the beginning is not much more difficult. But always remember that the order of moving pointers is very important, or you can end up with lots of memory leaks.
Lastly, a technique I picked up allows you to forego pointers and dynamic memory altogether. You create a standard, non-dynamic array that''s as big as you think you might ever need and an integer that keeps track of how many elements are currently valid, initialized to zero. Let''s call that integer "count".
To insert, simply copy the appropriate values into the element at position "count", THEN increment "count".
To use the array, start at zero and go through "count" number of elements.
Here''s the cool part:
To delete element n, first decrement count, THEN simply copy the data from element count into element n. Thus the last valid element is brought up to overwrite the deleted element and with the count decremented, you never reach the point in the array with the duplicate element until you are writing over it with a new node. Try it on paper if it doesn''t make sense.
Only down sides are that it does not maintain the order of elements, and that there is copying involved. But that last part doesn''t matter if your data structure is simple enough.
First, if you don''t already, try drawing a sample list on paper
with just a few nodes represented by boxes and arrows for connections. That helped me a lot when I started learning them and even now I do that when I need to figure out how to, for instance, insert between two nodes, or whatever. Just keep track of how you change the arrows, and especially in what order, to know how to change the pointers.
Second, if order is not important, then its much easier. Easiest is probably to always insert at the end (you can have a pointer to the last node to help, just be sure to update it to then point to this new node). Otherwise at the beginning is not much more difficult. But always remember that the order of moving pointers is very important, or you can end up with lots of memory leaks.
Lastly, a technique I picked up allows you to forego pointers and dynamic memory altogether. You create a standard, non-dynamic array that''s as big as you think you might ever need and an integer that keeps track of how many elements are currently valid, initialized to zero. Let''s call that integer "count".
To insert, simply copy the appropriate values into the element at position "count", THEN increment "count".
To use the array, start at zero and go through "count" number of elements.
Here''s the cool part:
To delete element n, first decrement count, THEN simply copy the data from element count into element n. Thus the last valid element is brought up to overwrite the deleted element and with the count decremented, you never reach the point in the array with the duplicate element until you are writing over it with a new node. Try it on paper if it doesn''t make sense.
Only down sides are that it does not maintain the order of elements, and that there is copying involved. But that last part doesn''t matter if your data structure is simple enough.
January 15, 2003 05:32 AM
that last suggestion solves my problem nicely, for now.
once i have finished my first simple game i will pick up that data structures books someone mentioned, and learn about linked lists, at the moment i just want to get my first game up and running, kind of sick of win32 console apps.
thankyou all for youre assistance.
once i have finished my first simple game i will pick up that data structures books someone mentioned, and learn about linked lists, at the moment i just want to get my first game up and running, kind of sick of win32 console apps.
thankyou all for youre assistance.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
