Sign in to follow this  

Deleting an object in linked list using template function

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

This topic is 408 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this