linked list help

[barneygumble742]

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

[Ganoosh]

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.

[barneygumble742]

sure. sounds great.

thanks,
barneygumble742

[Ganoosh]

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

[The Brain]

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:

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

[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

[durban]

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.

[The Brain]

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)