Inheriting Linked List

This is a discussion on Inheriting Linked List within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by robolee Hi, straight to the point: I have a good working linked list that I want a ...

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by robolee View Post
    Hi, straight to the point: I have a good working linked list that I want a bunch of structs to inherit. Using "struct blah : Object {code};" doesn't work and I know I could get the same thing by copying the code and pasting it into all my structs and renaming parts but that would be a whole lot of copypasta and a big mess... I've read a lot of stuff on inheritance and other stuff and have learnt everything I know about c++ from internet resources, and I've been working on this linked list business for ages and I finally decided to just join a random forum and ask for help (the whole thing would have been a whole damned lot quicker if I just asked in the first place but I guess I like to struggle at things on my own).

    Here's the linked list stuff, I want a way for a regular struct to inherit it:
    Code:
    typedef struct Object{//an "object" of the list
    	Object *Next;
    	Object *Previous;
    	void Add();
    	void Remove(Object *n);
    	void CleanList();
    } Object;
    
    Object *First;
    Object *Last;
    Object *ListPointer;
    
    void Object::Add(){
    	Object *Temp;
    	if (First){// If the list already has a First (the list exists)
    		Temp = new Object;		//NULL <-- |First|...|Last| --> NULL
    		Last->Next = Temp;		//NULL <-- |First|...|Last| --> |temp|
    		Temp->Previous = Last;	//NULL <-- |First|...|Last| <-> |temp|
    		Temp->Next = NULL;		//NULL <-- |First|...|Last| <-> |temp| --> NULL
    		Last = Temp;			//NULL <-- |First|...|oldL| <-> |Last| --> NULL
    		ListPointer = Last;		//NULL <-- |First|...|Last| --> NULL //and last is pointed to by the list
    		Temp = NULL;
    		delete Temp;
    	}
    	else{//there is no list yet
    		ListPointer = new Object;
    		First = ListPointer;
    		Last = ListPointer;
    		ListPointer->Next = NULL;
    		ListPointer->Previous = NULL;// NULL <-- |newPA| --> NULL
    		First = ListPointer;
    		Last = ListPointer;// NULL <-- |new/First/Last| --> NULL
    	}
    };
    void Object::Remove(Object *n){
    	if (n != First){
    		if (n->Next){
    			Object *tempb;
    			tempb = new Object;
    			tempb->Previous = n->Previous;
    			delete tempb;
    		}
    		if (Last == n){
    			Last = n->Previous;
    		}
    	}
    	if (n != Last){
    		if (n->Previous){
    			Object *tempc;
    			tempc = new Object;
    			tempc->Next = n->Next;
    			delete tempc;
    		}
    		if (First == n){
    			First = n->Next;
    		}
    	}
    	n->Next = NULL;
    	n->Previous = NULL;
    };
    void Object::CleanList(){				 // Destroys the entire list
    	Object *tempa, *r;
    	r = new Object;
    	tempa = new Object;
    	r = First;	// Start at the First Object of this list, for better speed
    	while (r){				// While r still means something
    		tempa = r->Next;			// Save our next APointer
    		r->Remove(r);				// Remove the one we're at
    		r = tempa;				// And advance.
    	}
    	delete r;
    	delete tempa;
    	delete ListPointer;
    	First = NULL;
    	Last = NULL;
    };
    Oh dear, that code has too many bugs in it to ever hope to possibly cover in one post.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #17
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Ah crap, I clicked the wrong button. I'm just going to pick one function:
    Here goes:
    Code:
    void Object::CleanList(){				 // Destroys the entire list
    	Object *tempa, *r;
    tempa shouldn't even be declared here as it is only used inside the while loop and should thus be declared there.
    Code:
    	r = new Object;
    Don't use new here, you don't allocate memory to perform a clear of the list. All this does is leak
    Code:
    	tempa = new Object;
    Again, don't use new here. All this does is leak
    Code:
    	r = First;	// Start at the First Object of this list, for better speed
    First should not be a global, it should be a member variable. This list cannot be reused, i.e. you can't have two or more lists.

    One thing done right! You've correctly avoided accessing deleted memory!
    Code:
    	while (r){				// While r still means something
    		tempa = r->Next;			// Save our next APointer
    		r->Remove(r);				// Remove the one we're at
    		r = tempa;				// And advance.
    	}
    Code:
    	delete r;
    r is NULL here. delete wont have any effect here.
    Code:
    	delete tempa;
    tempa is also NULL here
    Code:
    	delete ListPointer;
    Assuming remove already deletes the node pointed to (as it should), then this is a double-delete bug
    Code:
    	First = NULL;
    	Last = NULL;
    If these were correctly member variables of some kind of reusable list class then these lines wouldn't be necessary
    Code:
    };
    Last but not least, never claim code is bug-free.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #18
    Registered User
    Join Date
    Oct 2009
    Posts
    12
    I think you haven't understood a word I have written, I have a bunch of structs with data and linked list functions and pointers, I want to take out the repetitive linked list stuff write it out once, and have a way for the different structs to inherit the linked list functions and pointers so I have all these structs with different linked lists.

    this "Object" struct won't do anything because there is no data, I know that, however if I take my particle linked list then I can do stuff with it, the "Object" struct does nothing.

    I already have a partially working game engine, I know for a fact that my linked list implementation works because I had over 6 particles (bullets) on screen at the same time, and after many shots there were no apparent memory leaks.

    seems the above got in before I posted this, but what I mean by bug free is debugger didn't flag any bugs, I wouldn't claim to have perfectly bug-free code in any other way than that. and I don't think most people could claim it in any way other than that.
    Last edited by robolee; 10-17-2009 at 08:20 PM.

  4. #19
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So that the fact that your bullets don't disappear when you want them to isn't a "bug" then?

    Even if you don't believe us, sit down and read your own code. Better yet, "be" the computer and run through your own code. Start with say this:
    Code:
    [FRONT] <--> [n] <--> [LAST]
    and say you call your remove function with n pointing at the second bullet in your list. Now go through your remove function and see what happens.

  5. #20
    Registered User
    Join Date
    Oct 2009
    Posts
    12
    what? there were a few bullets on screen because they were all shot one after another and disappeared after they left the screen, reducing the lifetime of theparticles removes the bullets before they get chance to go off-screen, showing that the remove function either works or are you trying to say that they disappear by coincidence when remove is called due to a bug. however I think this version and the version in the game engine might be slightly different, I'm ill have a huge headache and am now going to bed.
    Last edited by robolee; 10-17-2009 at 08:49 PM.

  6. #21
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    It is possible that your original code works and you just royally worked it over when trying to turn it into this generic version. It is not unlikely that there's a coincidence going on (if the lifetime of your particles is known to, say, your drawing function then even if they're in your list they not get drawn). But you really shouldn't need us to tell you this; you should be able to look at your own code and see what it does.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 11:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21