Linked List

This is a discussion on Linked List within the C++ Programming forums, part of the General Programming Boards category; Hi, I am trying to implement a double link list using C++ classes (Don't want to use structure). I declare ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    41

    Linked List

    Hi,

    I am trying to implement a double link list using C++ classes (Don't want to use structure).

    I declare the following as class private data:

    private:
    lList *pNext ; // lList is my list class
    lList *pEnd;
    lList *pHead; //start of the list
    int Data;


    I need to allocate memory to pHead only at the start or if I have to insert something before the head of the list.

    When I create the next list instances "phead" is of no use to me. But everytime I create a new list 4 bytes are allocated to the pointer "pHead".

    Is there any way I can avoid allocating memory to pHead everytime?

    Thanks and Regards,
    Shal

  2. #2
    Registered User
    Join Date
    May 2006
    Posts
    903
    Make it a static member.

  3. #3
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    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;
    };
    Last edited by SlyMaelstrom; 06-15-2006 at 10:51 AM.
    Sent from my iPad«

  4. #4
    Registered User
    Join Date
    May 2006
    Posts
    41
    Does making the pointer static avoid memory allocation for pointer itself i.e 4 bytes?

    In the second reply:
    Code:
    class list {
       public:
         // Constructors, Destructors, Accessors and Mutators
       private:
         node<Type> *head;
         node<Type> *tail;
    };
    Are you still not allocating 4 bytes for *head everytime u create list? I am confused here, i think head has still got 4 bytes but what it point to is null.

  5. #5
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    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? */
    Last edited by SlyMaelstrom; 06-15-2006 at 12:42 PM.
    Sent from my iPad«

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    41
    That was a very gud info.. but i work on a system with memory limitation. I have to think before I allocate every bit of memory.. so if every time the head pointer takes 4 bytes then if my list goes to say 100 elements im exhausted with 400 bytes for nothing!
    Any way to create list and get arnd this problem?

  7. #7
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    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.
    Last edited by SlyMaelstrom; 06-15-2006 at 01:37 PM.
    Sent from my iPad«

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    If you only need one list, you can make the head static and there will be only one head pointer in your program. There will not be one for each node (if you make it static).

    If you need more than one list, or you choose SlyMaelstrom's initial suggestion, then you have a list instance for each list, not for each node. Notice that there is a separate class for nodes. So if you have three lists, each with 100 nodes, then you will have three head pointers in your program.

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,451
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

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, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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