Back to General and Gameplay Programming

Deleting an object in linked list using template function

General and Gameplay Programming Programming

Started by _WeirdCat_ November 01, 2016 08:19 PM

4 comments, last by _WeirdCat_ 7 years, 5 months ago

_WeirdCat_

1,512

Author

November 01, 2016 08:19 PM

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

Master & Mentor
https://sites.google.com/site/customprog/

fastcall22

10,918

November 01, 2016 08:33 PM

Passing in `first_object` of type type* creates a copy of the pointer. You will need another level of indirection if you expect to modify it outside of the function:


void A(int* p) { 
    p = nullptr;
}

void B(int*& p) {
    p = nullptr;
}

void C(int** p) {
    *p = nullptr;
}

int main() {
    int* the_int = new int;
    int* p;

    p = the_int;
    A(p);
    assert( p == the_int );

    p = the_int;
    B(p);
    assert( p == nullptr );

    p = the_int;
    C(&p);
    assert( p == nullptr );
}

Also, inb4 use std::vector/std::list

Khatharr

8,814

November 01, 2016 09:52 PM

use std::vector/std::list

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

Aardvajk

13,217

November 02, 2016 05:11 PM

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.

journal | website | twitter | youtube

Alberth

10,209

November 02, 2016 06:11 PM

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 :)