Jump to content
  • Advertisement
Sign in to follow this  
KKTHXBYE

Deleting an object in linked list using template function

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

Coz im lazy and i didn't want to write same code 8 times changing only one word i came up with this:


template <class type> void DeleteFromLinkedList(type * p, type * first_object)
{

if (p == 0) return;


if (p->prev == 0) //deleting first object
{
if (p->next != 0) p->next->prev = 0;
first_object = p->next;
delete p;
return;
}


if ( (p->prev != 0) && (p->next == 0) )      //last
p->prev->next = 0;


if ( (p->prev != 0) && (p->next != 0) )
{
p->prev->next = p->next;
p->next->prev = p->prev;
}




delete p;
}

however i have an issue with deleting first object in linked list, i try to delete it but it 'remains' moreover some of the information remains and first_object still points on memory that was 'deleted' [or at least half of the object was wipedout from the memory]

 

in example i have a personel structure

 

 

struct personel

{

char * name;

char * surname;

int nlen;

int slen;

unsigned char age;

etc

personel * next;

personel * prev;.

};

 

 

after deletion of first object of this linked list structure

i am able to lets say read surname (its exactly the same) but name and other info is gone, also it should point on the other personel.;

 

 

what the heck

Share this post


Link to post
Share on other sites
Advertisement
If you must (or really want to) implement your own linked list, at least make it non-intrusive so that the datatype itself does not need to contain the pointers.

template<typename T> class List
{
private:
    struct Node
    {
    	T value;
    	Node *next;
    };

public:
    List() { }
};
Fairly trivial then to make the delete method part of the List interface, then you can use it for any type you instantiate it for.

Share this post


Link to post
Share on other sites
For double-linked lists, moving the prev & next links outside the value makes it impossible to remove an item from a list even if you also have the List container object, since you cannot find the 'struct Node' wrapping the value.
For fun reading, see how Java LinkedList does it: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#241

Goodbye, O(1) remove operation :)

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!