Thread: Inheriting Linked List

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    12

    Inheriting Linked List

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

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Easy note: Your typedef is completely superfluous in C++, as struct is optional in types.

    On to the actual question: why not template what you've got? Your linked list is (probably) good (I didn't go through it all), except for the "not actually keeping any data" bit. So call your struct something like
    Code:
    template <typename T>
    struct Listof{
      //all your stuff
    }
    and include in your struct an actual data field.

    (I know this is a good idea because C++ already does this.)

  3. #3
    Registered User
    Join Date
    Oct 2009
    Posts
    12
    it purposely doesn't keep any data because I only want it to create a list for other structs which contain their data and I don't have any "universal" data I want to inherit. before it looked like this:
    Code:
    typedef struct Particle : Physics{
    	int TrailSize;
    	int R, G, B;
    	int type;
    
    	Particle *Next;
    	Particle *Previous;
    	void Add();
    	void Remove(Particle *n);
    	void CleanList();
    } Particle;
    //functions removed for clarity
    typedef struct Area{
    	int startX;
    	int endX;
    	int startY;
    	int endY;
    	bool type;
    	int maptoload;
    
    	Area *Next;
    	Area *Previous;
    	void Add();
    	void Remove(Area *n);
    	void CleanList();
    } Area;
    now I just want to be able to use the list functions for those structs, so I don't want the inherited list to have any other data.

    Also I don't quite understand how templates work though I did see an example it was confusing and wasn't explained, though I am looking into them now.

  4. #4
    Registered User
    Join Date
    Oct 2009
    Posts
    12
    okay I have failed at turning this into a template (mainly failing at the global pointers), could somebody just do it for me, or at least try to help me (this is not school work, I'm only 17 I shall have to wait a year before I can start learning this properly at uni, I'm just trying to make a game with a friend). I know asking for the whole thing is extreme but really I've spent months on this linked list stuff and I would be entirely grateful if someone could just give me something that works instead of spending another couple of months on it.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    If you're not doing it for an assignment, then don't do it. I will be more explicit then I was in my first post: This is already in C++. It's called "list". Off you go.

  6. #6
    Registered User
    Join Date
    Oct 2009
    Posts
    12
    I'm making a friggen game you unhelpful sod. And I'm doing this because I want to do it, I made it and thus I can both apply it better and it's more efficient as I'm not including a hundred other functions I'm not going to use. I don't care if it's wasting time or if I'm remaking something that's already built into the programming language. plus I'm doing this because I don't know how to use the template which I have already made clear and also because when I started it I didn't even know what a template was, now if you aren't going to help then off YOU go, because that post just pi- me off.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by robolee View Post
    could somebody just do it for me
    Quote Originally Posted by robolee View Post
    And I'm doing this because I want to do it
    Pick one.

    (EDIT: And I suppose I should mention that if you actually meant what you said about efficiency, that's the silliest thing ever, since, well, having functions that you don't use causes zero efficiency problems.)
    Last edited by tabstop; 10-17-2009 at 04:52 PM.

  8. #8
    Registered User
    Join Date
    Oct 2009
    Posts
    12
    hurr, you really are stupid, doing "it" in the first quote relates to turning my code into a template, doing "it" in the second quote relates to making a working linked list and making it as efficient as possible (i.e elimate a lot of code re-writing), if somebody turns it into a template then I will still have done more than 80% of the work so I would have achieved my aim and done "it", nowhere in the second quote does it say "on my own".
    Last edited by robolee; 10-17-2009 at 04:54 PM.

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by robolee View Post
    hurr, you really are stupid, doing "it" in the first quote relates to turning my code into a template, doing "it" in the second quote relates to making a working linked list and making it as efficient as possible (i.e elimate a lot of code re-writing), if somebody turns it into a template then I will still have done more than 80% of the work so I would have achieved my aim and done "it", nowhere in the second quote does it say "on my own".
    It's tempting to let you flounder. But I really fail to see the difficulty to turn this:
    Code:
    typedef struct Object{//an "object" of the list
    	Object *Next;
    	Object *Previous;
    	void Add();
    	void Remove(Object *n);
    	void CleanList();
    } Object;
    into this:
    Code:
    template <typename T>
    typedef struct Object{//an "object" of the list
    	Object<T> *Next;
    	Object<T> *Previous;
    	void Add();
    	void Remove(Object<T> *n);
    	void CleanList();
            T actual_data;
    } Object;
    which is what is required. If thirty seconds of reading a template tutorial can't get you to here, I don't know how much help anyone can be.

    (This assumes that your original works correctly. If it doesn't, you would need to fix this in the same way. For instance, it seems unlikely that you want Add() to be a void function that takes no arguments, but if you have it working then great.)
    Last edited by tabstop; 10-17-2009 at 05:01 PM.

  10. #10
    Registered User
    Join Date
    Oct 2009
    Posts
    12
    Everything from my initial code works absolutely bug free and perfectly, I fail to see why you would want add() to take an argument, add creates something how can you give it something that hasn't even been created yet?

    I didn't have a problem with that bit of the template, i was having a problem with the global functions
    (mainly failing at the global pointers)
    now none of the following work:
    Object *First;
    Object<T> *First;
    or anything including template. These pointers must be global and there must be one of each for each list otherwise it doesn't work. also I don't know how to use this template i another struct.
    Last edited by robolee; 10-17-2009 at 05:24 PM.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So ... what do you want it to store? Ints? Strings? What? You need to say, by doing
    Code:
    Object<WHAT DO YOU WANT TO STORE ANYWAY?> *First;

  12. #12
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I have a feeling this thread should be closed.

    Code:
    		if (n->Next){
    			Object *tempb;
    			tempb = new Object;
    			tempb->Previous = n->Previous;
    			delete tempb;
    		}
    Looking at something like this makes me really wonder, whether you want to learn some C++ (so you could later attempt to write a game) or spend the same time reinventing square linked lists and not be any further.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by anon View Post
    I have a feeling this thread should be closed.

    Code:
    		if (n->Next){
    			Object *tempb;
    			tempb = new Object;
    			tempb->Previous = n->Previous;
    			delete tempb;
    		}
    Looking at something like this makes me really wonder, whether you want to learn some C++ (so you could later attempt to write a game) or spend the same time reinventing square linked lists and not be any further.
    But remember, the original code works bug free and perfectly! Are you insinuating something about the OP's code!?!

    (I'm guessing OP hasn't quite the hang of the difference between "compiles with no errors" and "does what it is supposed to", but that's just a guess.)

  14. #14
    Registered User
    Join Date
    Oct 2009
    Posts
    12
    it compiles without error and does what it's supposed to do.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by robolee View Post
    it compiles without error and does what it's supposed to do.
    You're really claiming that your remove function actually removes something from the list? Are you sure you want to make that claim?

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, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10: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, 10:21 PM