Jump to content
  • Advertisement
Sign in to follow this  
barakat

Linked List Question

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

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
I agree that the second method is the better way.

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));
}
}
#endif



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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Quote:
Original post by ace_lovegrove
ofcourse its for educational reasons, i havent even begun to us STL yet,
I was asking barakat

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!