Linked List Question
Author
When creating a linked lists of students ( and i am going to implement the list from ground up ... )
what is better ? :
1- put the students data directly into each node
class node{
node* next;
int id;
string name;
///stuff////
};
2- include the student data as the data member of the node
class node{
node* next;
student data;//student is a struct containing student's data
};
It doesn't really matter either way - it comes down to personal preference.
I prefer to have the second way. Put everything required in a struct and then have an instance of the struct inside the class. It's just a lot easier when thinking about it for me.
I prefer to have the second way. Put everything required in a struct and then have an instance of the struct inside the class. It's just a lot easier when thinking about it for me.
I agree that the second method is the better way.
Also this code may help:
It's a templated linked class im in the process of finalising. Then it will be reviewed, finalised etc.
May help u with the understandings of the list.
ace
Also this code may help:
#ifndef _DOUBLE_LINKED_LIST_H_#define _DOUBLE_LINKED_LIST_H_#include <stdio.h>#include <stdlib.h>#include <memory.h>#include <assert.h>namespace COM_DAVESDUMP{ template <class T> class dl_list { public: dl_list(); virtual ~dl_list(); dl_list (const dl_list& o) { delete o; } void operator = (const dl_list& o) { delete o; } T* List_AddToStart(const T& p); T* List_AddToEnd(const T& p); T* List_AddBeforeThis(const T& p); T* List_AddAfterThis(const T& p); T* List_GotoStart(); T* List_GotoEnd(); T* List_TrackForward(); T* List_TrackBackward(); T* List_CreateEmpty(const unsigned long numNodes); void List_SwapThisNext(); void List_SwapThisPrev(); T* Get_Payload() { return node->payload;}; int Get_NumNodes() { return nodeCount; }; private: struct BODY { T* payload; BODY* prev; BODY* next; } start, *node, *end; unsigned long nodeCount; bool listInitiated; void List_Start(); void List_Destroy(); void SwapNodes(T& itemA, T& itemB); }; ////////////////////////////////////////////////////////////////////////////////////////////// // Name: list // Params: N/A // // Desc: Constructor, takes care of initialising the 'start' of the list. ////////////////////////////////////////////////////////////////////////////////////////////// template <class T> dl_list<T>::dl_list() : listInitiated(false) { listInitiated = false; nodeCount = 0; List_Start(); } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: ~list // Params: N/A // // Desc: Destructor, deletes the entire list when the object goes out of scope or is // deleted. ////////////////////////////////////////////////////////////////////////////////////////////// template <class T> dl_list<T>::~dl_list() { List_Destroy(); } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: StartList // Params: N/A // // Desc: Initiates the list. ////////////////////////////////////////////////////////////////////////////////////////////// template <class T> void dl_list<T>::List_Start() { start.next = NULL; start.prev = NULL; node = &start; end = &start; } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_AddToStart // Params: N/A // // Desc: Adds a node to the start of the list. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> T* dl_list<T>::List_AddToStart(const T& p) { BODY* firstNode; firstNode = start.next; start.next = new BODY; memcpy(&start.next->payload, &p, sizeof(start.next->payload)); start.next->next = firstNode; start.next->prev = NULL; start.next->next->prev = start.next; nodeCount++; return (node->payload); } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_AddToEnd // Params: N/A // // Desc: Adds a node to the end of the list. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> T* dl_list<T>::List_AddToEnd(const T& p) { end->next = new BODY; end->next->prev = end; end = end->next; end->payload = new T; memcpy(&end->payload, &p, sizeof(end->payload)); end->next = NULL; nodeCount++; return (node->payload); } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_Destroy // Params: N/A // // Desc: Completely deletes a linked list from memory. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> void dl_list<T>::List_Destroy() { //point to start node = &start; node = node->next; while(node != NULL) { // change start.next to point to next but one start.next = node->next; // delete this node delete (&node->payload); // move to the next but one node = start.next; } nodeCount = 0; } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_GotoStart // Params: N/A // // Desc: Sets the current node to the first node in the list. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> T* dl_list<T>::List_GotoStart() { node = start.next; return ((node != NULL)?(node->payload):(NULL)); } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_GotoEnd // Params: N/A // // Desc: Sets the current node to the last node in the list. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> T* dl_list<T>::List_GotoEnd() { node = end; return ((node != NULL)?(node->payload):(NULL)); } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_TrackForward // Params: N/A // // Desc: Move to the next node. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> T* dl_list<T>::List_TrackForward() { if(node->next != NULL) { node = node->next; return ((node != NULL)?(node->payload):(NULL)); } return NULL; } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_TrackBackward // Params: N/A // // Desc: Move to the previous node. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> T* dl_list<T>::List_TrackBackward() { if(node->prev != NULL) { node = node->prev; return ((node != NULL)?(node->payload):(NULL)); } return NULL; } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_TrackBackward // Params: N/A // // Desc: Move to the previous node. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> T* list<T>::List_AddBeforeThis(const T& p) { if (node->prev != NULL) { BODY* toBeNext, *toBePrev; toBeNext = node; toBePrev = node->prev; //----- node->prev->next = new BODY; node = node->prev->next; node->prev = toBePrev; node->next = toBeNext; node->next->prev = node; memcpy(&node->payload, &p, sizeof(node->payload)); nodeCount++; return ((node != NULL)?(node->payload):(NULL)); } else { List_AddToStart(p); } return NULL; } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_TrackBackward // Params: N/A // // Desc: Move to the previous node. ////////////////////////////////////////////////////////////////////////////////////////////// template<class T> T* dl_list<T>::List_AddAfterThis(const T& p) { if (node->next != NULL) { BODY* toBeNext, *toBePrev; toBeNext = node->next; toBePrev = node; //----- node->next = new BODY; node = node->next; node->prev = toBePrev; node->next = toBeNext; node->next->prev = node; memcpy(&node->payload, &p, sizeof(node->payload)); nodeCount++; return ((node != NULL)?(node->payload):(NULL)); } else { List_AddToEnd(p); } return NULL; } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_SwapThisNext // Params: N/A // // Desc: Swap over this node and the next node. ////////////////////////////////////////////////////////////////////////////////////////////// template <class T> void dl_list<T>::List_SwapThisNext() { if ( ( node->payload != NULL ) && ( node->next != NULL) ) { SwapNodes((T&)node->payload, (T&)node->next->payload); } } ////////////////////////////////////////////////////////////////////////////////////////////// // Name: List_SwapThisPrev( // Params: N/A // // Desc: Swap over this node and the previous node. ////////////////////////////////////////////////////////////////////////////////////////////// template <class T> void dl_list<T>::List_SwapThisPrev() { if ( ( node->payload != NULL ) && ( node->prev != NULL) ) { SwapNodes((T&)node->payload, (T&)node->prev->payload); } } template <class T> void list<T>::SwapNodes(T& itemA, T& itemB) { T temp; temp = itemB; (itemB) = (itemA); (itemA) = (temp); } template <class T> T* dl_list<T>::List_CreateEmpty(const unsigned long numNodes) { unsigned long currIndex; List_Destroy(); List_GotoStart(); for (currIndex = 0; currIndex < numNodes; currIndex++) { { // same has add node to end of list code but with no memcpy end->next = new BODY; end->next->prev = end; end = end->next; end->payload = new T; end->next = NULL; } nodeCount++; } return ((node != NULL)?(node->payload):(NULL)); }}#endifIt's a templated linked class im in the process of finalising. Then it will be reviewed, finalised etc.
May help u with the understandings of the list.
ace
Quote:Original post by ace_lovegrove
It's a templated linked class im in the process of finalising. Then it will be reviewed, finalised etc.
I can see alots flaws in your list for instance:
1. syntactically correct but schematically wrong assigmenet operator.
2. copy constructor & assignement operator don't anything but try to use operator delete (and used incorrectly).
3. virtual destructor, why? is it meant to be an intrusive list?
4. hard-coded memory model/scheme, what if i want to use a pooled allocator? i'd be forced to do something like redefine global operators new/delete.
5. No speratation of allocation/deallocation & construction/destruction.
6. no iterator types, clients have to deal with nodes or you write a million methods to do specific tasks yucky.
7. Potentially not exception safe code.
I'm just pointing some of these out to you as advice [smile] because the standard c++ library provides a parameterized list type, unless your writing lists to learn data structures & algorithms i recommend you use that instead.
This makes me question even more some of the people the randomly blurt out that STL is an overhead & then i see code like this.
[Edited by - snk_kid on November 26, 2004 9:23:40 AM]
Is this for educational reasons?
If not use the standard std::list, or the non-standard slist if you only need forward traversal and you're really excruciatingly worried about memory overhead.
If not use the standard std::list, or the non-standard slist if you only need forward traversal and you're really excruciatingly worried about memory overhead.
ofcourse its for educational reasons, i havent even begun to us STL yet,
Im not stupid enough to think mine is better.
And it actually does what i want it to, which for now is enough.
ace
Im not stupid enough to think mine is better.
And it actually does what i want it to, which for now is enough.
ace
Quote:Original post by ace_lovegroveI was asking barakat
ofcourse its for educational reasons, i havent even begun to us STL yet,
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
