Thread: Linked List

Make it a static member.

EDIT: I guess I see what your saying. The proper way to do this is to have two classes, though. A node class and a list class. As your code stands, each node represents the start of a new list, this is unnessasary as the head would simply be pointing to itself all the time. Try structuring something like this:

Code:

template <class Type> class list;

template <class Type>
class node {
   friend class list<Type>;
   public:
     // Constructors, Destructors, Accessors and Mutators
   private:
     node<Type> *next;
     node<Type> *prev;
     Type data;
};

template <class Type>
class list {
   public:
     // Constructors, Destructors, Accessors and Mutators
   private:
     node<Type> *head;
     node<Type> *tail;
};

Of course it does, but then each new list is supposed to have it's own head. The difference is, when you add a node, you don't create a new list, you create a new node. The distinction between the two should be noted.

Let me draw you a diagram:

Code:

/* This is what your data structure looks like when you have 
   multiple nodes *//* All pointers point to lLists */
--List--    --List--    --List--    --List--    --List--
 *head       *head       *head       *head       *head   
 *next   --> *next   --> *next   --> *next   --> *next  -->
  data        data        data        data        data 
--------    --------    --------    --------    --------

/* This is what mine looks like *//* All pointers point to nodes */
--List--
 -head-      -Node-      -Node-      -Node-      -Node-
 *next  -->  *next  -->  *next  -->  *next  -->  *next  -->
 *prev  <--  *prev  <--  *prev  <--  *prev  <--  *prev
  data        data        data        data        data
 ------      ------      ------      ------      ------      
 *tail
--------

/* See the difference? */

What the hell am I even talking for.

My example only has one head. If you create a new list, you need a new head. That new head represents the beginning of a different list. The minimum(and really maximum) number of heads each list has is one not zero. Now if you're restricted in memory, perhaps a doubly linked list isn't the best choice. Make a singly linked list and sacrifice speed in iteration for more compact structures.

> Are you still not allocating 4 bytes for *head everytime u create list? I am confused here,
Well if you ever want to have more than one list, say a list of students AND a list of teachers AND a list of courses, then of course you'll be glad that head isn't part of the list at all.

Just listen to Sly for a while.