linked list help

This is a discussion on linked list help within the C++ Programming forums, part of the General Programming Boards category; hi, i need serious help with linked lists. the book i have is by larry nyhoff and its completely useless ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    84

    linked list help

    hi,

    i need serious help with linked lists. the book i have is by larry nyhoff and its completely useless when it comes to the basics of linked lists. there's a lot of theory but no code.

    can someone show me how to create a linked list using a class (not a struct)? or at least point me to a site that will explain it?

    thanks,
    barneygumble742

  2. #2
    myNegReal
    Join Date
    Jun 2005
    Posts
    100
    I made a nice little linked list class a while ago if you want the code I can post it for you. It uses structs and a class, and also templates if you don't understand them yet maybe I should off, but if you wanna see it let me know.
    Using Dev-C++ on Windows

  3. #3
    Registered User
    Join Date
    Sep 2004
    Posts
    84
    sure. sounds great.

    thanks,
    barneygumble742

  4. #4
    myNegReal
    Join Date
    Jun 2005
    Posts
    100
    Code:
    template <class obj_type> class LinkedList {
        struct LLNode {
            obj_type value;
            LLNode* next;
        };
        public:
                 LinkedList();
                 ~LinkedList();
                 void add(obj_type value);
                 bool set(int index, obj_type value);
                 obj_type get(int index);
                 obj_type remove(int index);
                 int size();
        private:
                 LLNode *root;
                 LLNode *traverser;
                 void cleanup(LLNode *next);
    };
    
    template <class obj_type> LinkedList<obj_type>::LinkedList() : root(NULL), traverser(NULL) {
                             root = new LLNode;
                             root->next = 0;
                             traverser = root;
    }
    
    template <class obj_type> LinkedList<obj_type>::~LinkedList() {
    }
    
    template <class obj_type> void LinkedList<obj_type>::add(obj_type value) {
         traverser = root;
         if (traverser != 0) {
                     while (traverser->next != 0) {
                           traverser = traverser->next;
                     }
                     traverser->value = value;
                     traverser->next = new LLNode;
                     traverser->next->next = 0;
         }
    }
    
    template <class obj_type> bool LinkedList<obj_type>::set(int index, obj_type value) {
         traverser = root;
         for (int i=0;traverser!=0;i++) {
             if (i == index) {
                   traverser->value = value;
                   return true;
             }
             traverser = traverser->next;
         }
         return false;
    }
    
    template <class obj_type> obj_type LinkedList<obj_type>::get(int index) {
        traverser = root;
        for (int i=0;traverser!=0;i++) {
            if (i == index)
                  return traverser->value;
            traverser = traverser->next;
        }
        return 0;
    }
    The code is kinda noobish and probably hard to understand at first (my fault). Also I never implemented a destructor lolol. Any other memory leaks I'm not aware of don't think there are, but it's possible. But it demonstrates the basics on how it works check it out maybe you could improve it. And go here for an explanation if you want: http://www.cprogramming.com/tutorial/lesson15.html
    Using Dev-C++ on Windows

  5. #5
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    Thumbs up

    Here is some basic linked list theory as decribed to me by my CS201 instructor:


    1) You will probably always need a dedicated pointer to the head node of the list.
    (especially if you plan to add new nodes to the beginning of the list)

    2) Having a pointer to the tail of the list is optional
    (but is necessary if you plan to add new nodes at the end of the list)

    3) Unlike an array, you will probably not be able to access nodes of the list directly.. you will have to implement a basic linked list traversal algorithm.. that will start either at the head node or tail node.. and traverse the list to the desired node:

    Code:
    node* Myclass::name_search(string target)      //function will accept a string (for example) and will return a pointer to the desired node (struct) in the list of link
    {
    
         node *temp = head_ptr;    //preserve head pointer integrity right away.  (for this case assume head_ptr is a Myclass var and is not passed into this function)
    
         while(temp && temp->name != target)   //testing nodes will usually include at least two conditions..  one should always test to see if the node != NULL to prevent dereferrencing a NULL pointer
         {
              //Starting with the head node in this example (initially assigned to 'temp') start a cycle of dereferrincing, testing, and re-assigning temp until either the target is found.. or until end of list (NULL)
    
              temp = temp->next;  //target name was not found.. so make 'temp' the next node in the list..  and try again.  simple pointer reassignment
         }
    
              return temp;  //temp will either be the first node in the list that matches the target..  or temp will be NULL.   
    }
    4) if you want to add nodes to the list.. you will probably use 'head node insertion' or 'tail node insertion' which will involve creating a new node.. and re-assigning the head_ptr (or tail_ptr) to point to that new node.. and then have that new node point to the previous head/tail pointer.

    5) if you want to delete a node from the list.. you will probably either use "head node deletion" or "tail node deletion".. which will involve first re-assigning the head_ptr (or tail_ptr) and then deleteting the previous head/tail pointer.


    the new and delete keywords are what make linked lists unique and very powerful when it comes to creating new objects (nodes) at runtime.. unlike arrays.

    your class destructor.. will probably be nothing more than a loop that will call your "delete_node( )" function until there are no more nodes in the list.. so when your program exits, it will have returned all that memory created at runtime back to the freestore.

    remember: always keeping track of the beginning and/or end of the list is half the battle when using a linked list.

    tip: if you create a pointer.. and it is not initialized to anything specifically, always initialize it to NULL. (it's a bad idea just to declare a pointer variable.. and have it just exist without either pointing to something.. or being set to NULL)

    finally: after you've written basic linked list functions for your program (adding nodes.. locating a desired node etc) remember to test your functions for the "empty list case".. or see how your functions react to having no nodes in the list (head_ptr = NULL) Testing for the 'empty list case' will ensure that you will not dereferrence a NULL pointer.. which is very not good.

    hope this gets you pointed (pun) in the right direction
    Last edited by The Brain; 10-03-2005 at 07:10 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  6. #6
    Registered User
    Join Date
    Sep 2004
    Posts
    84
    hi everyone...thanks for the help but i'm still not understanding. i think i know exactly what do to once i have a linked list and a structure in place. however creating the structure and the list is becoming more than a pain in the neck.

    | string | link | -> | str...

    how can i make this happen? i guess i'm simply not seeing where the structure is created. except without a struct but with a class.

    thanks,
    barneygumble742

  7. #7
    Bioport Productions
    Join Date
    Oct 2005
    Posts
    215
    Quote Originally Posted by barneygumble742
    hi everyone...thanks for the help but i'm still not understanding. i think i know exactly what do to once i have a linked list and a structure in place. however creating the structure and the list is becoming more than a pain in the neck.

    | string | link | -> | str...

    how can i make this happen? i guess i'm simply not seeing where the structure is created. except without a struct but with a class.

    thanks,
    barneygumble742
    a class in a sense, is a struct. Ganoosh gave you a quite complex linked list for someone just learning. I'll tell you how I learned, search google. This subject is pretty hard and you will need a detailed explanation of it and a thorough understanding of pointers before beginning. search google for "linked lists tutorials C++", that should yield some nice explanations.

    Hope this helps.
    -"What we wish, we readily believe, and what we ourselves think, we imagine others think also."
    PHP Code:
    sadf 

  8. #8
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    5) if you want to delete a node from the list.. you will probably either use "head node deletion" or "tail node deletion".. which will involve first re-assigning the head_ptr (or tail_ptr) and then deleteting the previous head/tail pointer.
    This is a mistake on my part.. deleting a node from a linked list can occur anywhere along the list (not just at the head or tail pointer)
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

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