Thread: question about a working linked list

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    question about a working linked list

    Hi, this program is the solution to an excercise I found on a book...I wrote it reading tutorials and stuff...my problem is... as you can see in the CreateList function...I have no secondary node pointing to nothing....I have read that you need a second pointer because the first node is unchangeable and the second one is the one that's going to move in the list....but in this code I don't use that second node...so..why does this works correctly? does it have some kind of error? I can't figure it out because I'm kind of new in this kind of programming technique and I have never used linked list before...

    can you please tell what am I doing wrong? thanks..

    Edit:Sorry that I didn't format my code...I don't know HTML or how to place code...I did read the post about using code tags, but it doesn't specify what code one should use to insert tabs or spaces...

    Edit:Ok forget it... I just found out how to do it :P hahaha

    Code:
    #include <iostream>
    using namespace std;
    
    struct linkedList {
      int obj_number;  //Numbers the current list
      linkedList* Next;
    };
    
    void CreateList( linkedList* anyList, int nodes ){
    
      for(int i = 0; i < nodes; i++){
        anyList->obj_number = i + 1;  //put the number of the current node
        anyList->Next = new linkedList;  //creates a new node at the end of the list
        anyList = anyList->Next;  //moves to this new node
        anyList->Next = 0;  
      }
      
    }
    
    void DisplayList( linkedList* anyList ){
    
      while( anyList->Next != NULL ){
        cout << anyList->obj_number << endl;
        anyList = anyList->Next;
      }
    
    }
    
    int main(){
      linkedList* myList;
    
      myList = new linkedList;
      CreateList( myList, 5 );
      DisplayList( myList );
      cin.get();
      delete myList;
    }
    Last edited by cold_dog; 09-01-2006 at 12:55 AM.

  2. #2
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    You free your list incorrectly. You must delete every node in the list, not just the head.

    Code:
    void FreeList(linkedList * list)
    {
          if(list->Next)
          {
                FreeList(list->Next);
          }
          else delete list;
    }

  3. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    First, please enclose your code using code tags!!!
    Second, you have created linked list, how about destroying it? Please try to write functions for adding element to list, removing element from the list, for reversing list and so on...
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  4. #4
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    question about a working linked list

    Quote Originally Posted by Tonto

    Code:
    void FreeList(linkedList * list)
    {
          if(list->Next)
          {
                FreeList(list->Next);
          }
          else delete list;
    }
    Thanks... I didn't know that...but why does the list display correctly if I created the list incorrectly? I mean...it does what it is supposed to do...but the way I did it is not well...

  5. #5
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    question about a working linked list

    Quote Originally Posted by Micko
    First, please enclose your code using code tags!!!
    Second, you have created linked list, how about destroying it? Please try to write functions for adding element to list, removing element from the list, for reversing list and so on...
    well..ok I will try to write those functions...but...I have no idea of what I just did...my question is about the program running even though I did it wrong...I don't understand quite well about this linked list thing...

  6. #6
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by cold_dog
    well..ok I will try to write those functions...but...I have no idea of what I just did...my question is about the program running even though I did it wrong...I don't understand quite well about this linked list thing...
    The idea of a "linked list" is something of an abstract one. its easy to imagine a list being a big object in memory, wheras in fact its just a bunch of scattered objects in memory, which contain pointers. These pointers are the "links", which allow the objects to function as a list together. creating a linked list is a good test of how well you really understand pointers (one of the big milestone hurdles for any new programmer to jump across)
    Code:
       +----+-----------------------------+
       |1234|  Addr 58 (Pointer to Head)  |     We always know where the head is, but rely
       +----+-----------------------------+     on pointers to maintain the "links" between the
                                                other nodes
    
       +----+-----------------------------+
       | 1  |   gobbledeegook             |
       +----+------------------+----------+
       | 2  | Node Data(int 3) | Addr 10  |
       +----+------------------+----------+
       | 3  |   gobbledeegook             |
       +----+-----------------------------+
       | .. |   ...........               |
       +----+------------------+----------+
       | 10 | Node Data(int 2) | Addr 99  |
       +----+------------------+----------+
       | 11 |   gobbledeegook             |
       +----+-----------------------------+
       | 12 |   gobbledeegook             |
       +----+-----------------------------+
       | .. |   ..........                |
       +----+-----------------------------+
       | .. |   ..........                |
       +----+-----------------------------+
       | 57 |   gobbledeegook             |
       +----+------------------+----------+
       | 58 | Node Data(int 4) | Addr 2   |
       +----+------------------+----------+
       | .. |   ..........                |
       +----+------------------+----------+
       | 99 | Node Data(int 1) | Addr NULL|
       +----+------------------+----------+
    sorry for the naff ASCII drawing
    The numbers along the left-hand column might be your memory addresses. The bigger right-hand column might be whats at each address (gobbledeegook is unused by your program, maybe memory in use elsewhere, or junk left over from other programs.)


    Code:
    #include <iostream>
    
    struct node_t  // 'blueprint' for our list nodes.
    {
        int data;
        node_t* next;
    };
    
    node_t* node_create(node_t* head, int i)
    {
        node_t* newnode = new node_t; // new node is created  (will become new head)
        newnode->next = head; // old head becomes the 2nd element.
        newnode->data = i; // new node gets data
        return newnode; // returns a pointer to the new head,  back to the caller.
    }
    
    int main()
    {
        node_t* head(NULL);  // We begin with a pointer to NULL - our list has 0 elements to begin with.
                             // head is always a pointer to the first element in the list.
        const int size(10); // lets have 10 elements.
    
        // build a list in 'reverse' order.
        for(int i(0); i!=size; ++i)
            head=node_create(head, i);  
                // each time this is called, we add a new element, which becomes the new "head".
    
        // output list, and delete each node as we go along.
        // we built the list in reverse, so head is still always the first element
        while(head)
        {
            std::cout << head->data << std::endl;
            node_t* temp = head;  // temporary placeholder for old head before deleting
            head=head->next; // 2nd element becomes head
            delete temp; // clean up old head.
        }
    }
    Last edited by Bench82; 09-01-2006 at 04:46 AM.

  7. #7
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    Here is my last linked list. You can ignore the main() if you don't use Windows.

    Code:
    class linkedlist{
    	struct node{
    		int value;
    		node* nextadd;
    	};
    	node* lHandle;
    	
    public:
    	enum LLErrCodes{
    		errStackIsEmpty=1
    	};
    
    	linkedlist(){
    		lHandle=NULL;	
    	}
    
    	~linkedlist(){
    		if(lHandle!=NULL){
    			while(lHandle->nextadd!=NULL){
    				node* adr = lHandle->nextadd;
    				delete lHandle;
    				lHandle = adr;
    			}
    			delete lHandle;
    			lHandle = NULL;
    		}
    	}
    
    	void push(int val){
    		if(lHandle==NULL){
    			lHandle= new node;
    			lHandle->value=val;
    			lHandle->nextadd=NULL;
    		
    		}
    		else{
    			node* adr= new node;
    			adr->nextadd=lHandle;
    			adr->value = val;
    			lHandle = adr;
    		}
    	}
    	void pop(void){
    		if(lHandle!=NULL){
    			node* adr = lHandle->nextadd;
    			delete lHandle;
    			lHandle=adr;
    			
    		}
    	}
    	int top(void){
    			if(lHandle!=NULL)return lHandle->value;
    			else throw errStackIsEmpty;
    	}
    
    	bool isEmpty(void){
    		if(lHandle!=NULL)return false;
    		else return true;
    	}
    	bool operator== ( linkedlist &righth){
    		if(isEmpty() && righth.isEmpty()) return true;
    		else if((isEmpty() && !righth.isEmpty()) || (!isEmpty() && righth.isEmpty())) return false;
    		else{
    			while(!isEmpty() && !righth.isEmpty()){
    				if(top() != righth.top()) return false;
    				pop();
    				righth.pop();
    				if(isEmpty() && righth.isEmpty()) return true;
    			}
    			return false;
    		}
    	}
    	bool operator< ( linkedlist &righth){
    		if(isEmpty() && righth.isEmpty()) return false;
    		else if((isEmpty() && !righth.isEmpty()) ) return true;
    		else if( (!isEmpty() && righth.isEmpty())) return false;
    		else{
    			while(1){
    				if(top() > righth.top()) return false;
    				else if(top() < righth.top()) return true;
    				else{
    					pop();
    					righth.pop();
    					if(isEmpty() && righth.isEmpty()) return false;
    					else if(isEmpty() && !righth.isEmpty() ) return true;
    					else if( !isEmpty() && righth.isEmpty()) return false;
    				}
    			}
    		}
    	}
    
    	bool operator> ( linkedlist &righth){
    		if(isEmpty() && righth.isEmpty()) return false;
    		else if((isEmpty() && !righth.isEmpty()) ) return false;
    		else if( (!isEmpty() && righth.isEmpty())) return true;
    		else{
    			do{
    				if(top() > righth.top()) return true;
    				else if(top() < righth.top()) return false;
    				else{
    					pop();
    					righth.pop();
    					if(isEmpty() && righth.isEmpty()) return false;
    					else if(isEmpty() && !righth.isEmpty()) return false;
    					else if(!isEmpty() && righth.isEmpty()) return true;
    				}
    			}while(1);
    	
    		}
    	}
    	bool operator>=(linkedlist &righth){
    		return !(operator<(righth));
    	}
    	bool operator<=(linkedlist &righth){
    		return !(operator>(righth));
    	}
    	bool operator!= ( linkedlist &righth){
    		return !(operator==(righth));
    	}
    
    };
    
    int main(){
    	linkedlist ll,ll2;
    
    	stack<int> st;
    	int a=0,b=0;
    	DWORD llinit=GetTickCount();
    	for(int i=2;i<5000000;i++) ll.push(i);
    	llinit=GetTickCount()-llinit;
    	
    	DWORD Stackinit=GetTickCount();
    	for(int i=2;i<5000000;i++) st.push(i);
    	Stackinit=GetTickCount()-Stackinit;
    
    	DWORD llpop = GetTickCount();
    	for(int i=2;i<5000000;i++){
    		a=ll.top();
    		ll.pop();
    		
    	}
    	llpop=GetTickCount()-llpop;
    	cout<<a<<endl;
    
    	DWORD Stackpop=GetTickCount();
    	for(int i=2;i<5000000;i++){
    		b=st.top();
    		st.pop();
    	}
    	Stackpop=GetTickCount()-Stackpop;
    	cout<<b<<endl;
    
    	cout<<"Stackinit: "<< Stackinit<<"  Stackpop: "<<Stackpop<<endl;
    	cout<<"LLinit: "<<llinit<<"  LLpop: "<<llpop<<endl;
    
    	cin.get();
    	return 0;
    }
    Last edited by siavoshkc; 09-01-2006 at 05:47 PM.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318

    Eeek

    Dude - Simplify!!!
    Code:
    	~linkedlist() {
    		while (lHandle != NULL) {
    			node* adr = lHandle->nextadd;
    			delete lHandle;
    			lHandle = adr;			
    		}
    	}
    
    	void push(int val) {
    		node* adr = lHandle;
    		lHandle = new node;
    		lHandle->value = val;
    		lHandle->nextadd = adr;
    	}
    
    	bool isEmpty(void) const {
    		return lHandle == NULL;
    	}
    
    	bool operator> (linkedlist &righth) {
    		return righth < *this;
    	}
    That code does EXACTLY the same as yours, but is FAR less verbose and easier to understand.
    The rest can mostly be simplified just as much, but you get the idea. If you want me to show you how to simplify the rest, let me know.
    Last edited by iMalc; 09-01-2006 at 06:25 PM.

  9. #9
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    more confused than ever

    Thanks guys...I see that you all understand what you are talking about... Imma try to improve my list but I don't understand quite well your code...as you can see mine is simpler and my question hasn't been answered....I did the list...I know its wrong...but it works ok...I want to know what is the error....what can go wrong if I do it that way?...do I lost data...do I use more memory than I should?....you told me that the way I cleaned up the list was wrong...Ok thats a good starter...I know that I left unnecessary data in memory...but what else is wrong with the list?

    I know from the examples that you have to use two nodes, one for the head...and one to travel throuhgt the list....but why is my list working well if I don't have the second pointer?...

    As in the sample says...the conductor...I think that I am changing the data in my root pointer...which happens to be the only one that I have...so...why can I see the whole list if I am directly modifying the root pointer...the head or whatever...

    I supposed that I couldn't travel the list if I do it that way...and I rewrote the whole thing so I had a better list...and it worked too...but then I decided to go back and use the list I did first...so I could post the code here and ask this question...and see why is the list running...

    This code has fewer lines than the one that is correct...so...why do I have to use that many lines if this list is shorter and it works anyway? but...I suppose there must be some kind of error in that code so I want to know...why this aproach should be avoided if it works anyway...?

  10. #10
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by cold_dog
    my question hasn't been answered....I did the list...I know its wrong...but it works ok...I want to know what is the error....what can go wrong if I do it that way?...do I lost data...do I use more memory than I should?....you told me that the way I cleaned up the list was wrong...Ok thats a good starter...I know that I left unnecessary data in memory...but what else is wrong with the list?
    for a toy program, you can just about get away with it, but it's a very bad habit. You can't ignore memory leaks - ever! Because they have a cumulative effect in slowing down your system. eg, imagine your list creates new nodes which are 50 bytes in size, a memory leak of 50 bytes probably would go un-noticed, but your list is going to contain alot more nodes than that.. what if you have 100,000 nodes? that's 5MB of memory you might lose. Even that might not seem very much to a system with 2GB of RAM.. but if your program is copying the list all over the place, without freeing the unwanted memory, and maybe your program will be running non-stop for hours on end, eventually, all your leaks will take up the system's entire memory pool, and the computer will crash.

    I know from the examples that you have to use two nodes, one for the head...and one to travel throuhgt the list....but why is my list working well if I don't have the second pointer?...
    I think you meant to say "pointer" - in which case, you actually need one pointer inside each node (that's already defined in your node data-type/struct- the pointers contained in the nodes are the links.)
    Outside the list you will need a pointer to the first node, the head. You might also use a temporary pointer for traversing the list.

    As in the sample says...the conductor...I think that I am changing the data in my root pointer...which happens to be the only one that I have...so...why can I see the whole list if I am directly modifying the root pointer...the head or whatever...
    Again, there's confusion between the term "node" and the term "pointer".

    The term 'head' can be directly translated to "The first node in the list" - In other words, the actual node object - not a pointer.
    a pointer is a variable which contains the address of a node in your list. you will have a head pointer which always contains the address of your head.

    As i said before, each node contains a pointer aswell. each node's pointer is for the next element in the list

    Back to your original question, in your program your 'root pointer' is changing, it isn't always pointing to the head. it begins by pointing to the head, then it points to the 2nd, then the 3rd, then the 4th, etc. However, each time you traverse along the list, you effectively "lose" the previous nodes, since there's nothing pointing to them - But those previous nodes are still there in your memory, its just unreachable by your program (and therefore completely useless). That is your memory leak.
    You have several options
    1) Delete the data as you traverse the list (That's how my example worked - although obviously a little useless if you want to keep the data for later)
    2) Or, if you want to keep the data, maintain a pointer to the head, then delete all the data at once, at the end of the program (or whenever you want to destroy the list)
    3) Create a doubly-linked list where the nodes point to their previous node aswell as their next node (This is the most difficult option - singly linked lists are much easier to write - and either way you probably still want a pointer to the head, and maybe one to the tail aswell)

    This code has fewer lines than the one that is correct...so...why do I have to use that many lines if this list is shorter and it works anyway? but...I suppose there must be some kind of error in that code so I want to know...why this aproach should be avoided if it works anyway...?
    Everybody has a slightly different approach to linked lists. you could put 10 people in a room, and ask them to write a linked list, and all 10 may create programs which are a completely different size & complexity, but all work properly, and all do the same thing. Looking at the size of your program, it appears to be about the same length as the example I wrote (minus the comments). Don't worry about program length, as long as it works, and you understand what's going on.
    Last edited by Bench82; 09-02-2006 at 05:24 AM.

  11. #11
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    Thanks

    Dude thanks, Bench82 now I see the problem...thats what I wanted to know...thank you man... thanks to all of you

  12. #12
    Registered User
    Join Date
    Apr 2004
    Posts
    17
    Quote Originally Posted by Tonto
    You free your list incorrectly. You must delete every node in the list, not just the head.

    Code:
    void FreeList(linkedList * list)
    {
          if(list->Next)
          {
                FreeList(list->Next);
          }
          else delete list;
    }
    Hey..I followed your advice, and I did this function....

    Code:
    void cleanList( node* anyNode ){  //cleans the whole list
    
      node* temp;
    
      if( anyNode != 0 ){  //makes sure that the first pointer is pointing to something
    
        while( anyNode->next != 0 ){  //while is not the end of the list      
          temp = anyNode;  //temporary stores the current position
          anyNode = anyNode->next;  //moves to the next position
          delete temp;  //deletes the current position
        }  //while
     
      }  //if
    
    }
    I know that the head pointer is still there so in main, after calling cleanList() I did this:

    Code:
      int main(){
        node* root;
        ...
        ...                            //Creating and displaying list and other stuff
        ...
    
        cleanList( root );  
    
        delete root;
    }
    Is this OK?

  13. #13
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    That's much better

    Quote Originally Posted by cold_dog
    I know that the head pointer is still there so in main, after calling cleanList() I did this:
    Yes, the pointer still exists, but that's not a problem. It is the actual nodes which were leaking, not the pointers. When you call your cleanList() function, the head node is deleted, so the head pointer doesn't point to anything - therefore..

    Code:
        delete root;
    The final delete root; is unnecessary. (delete doesn't delete pointers, it deletes their referred objects, which, earlier in your program were created by new. so with that last line you're deleting something which doesn't exist)
    Last edited by Bench82; 09-03-2006 at 05:29 AM.

  14. #14
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    thanks again

    Quote Originally Posted by Bench82
    Much better, although the final delete root; is unnecessary because cleanList() has already deleted the first node in your list.
    Ok thanks...but now I have another problem....

    I created a function to add a new element at the beggining of the list...here's the code:

    Code:
    node* addToList( node* firstNode, node* newNode ){
    
      newNode->next = firstNode;
    
      firstNode = newNode;
    
      return firstNode;
    }
    
    int main(){
      node* root;
      node* newNode;
    
      root = new node;
    
      createNode( root, 10 );
    
      newNode = new node;
      newNode->x = 15;
    
      root = addToList( root, newNode );
    
      displayList( root );
    }
    When I call displayList() it prints these values:
    15
    1
    2
    3
    ...and so on. Yeaaaaaaaaaah! it's working, it's working!

    but if I do this before calling displayList:

    Code:
      delete newNode->next;
      delete newNode;
    then it displays:

    The address of the head, a 0(zero), and then it displays all the elements from 1 to 10....'bleeep'

    The teory to adding a node to the beggining of the list is to have a new node created, then make the next pointer of this new node point to the beggining of the list, then making the head point to this new node....like this:

    Code:
      newNode->next = firstNode;
    
      firstNode = newNode;
    I tried to figure out what was going wrong so I displayed the whole process inside of addToList(), and I see that the address of the head becomes the address of the newNode, so I suppose the code is right....but why when I change newNode in any way in main(), and then I call displayList() everything is messed up??

  15. #15
    Registered User
    Join Date
    Apr 2004
    Posts
    17

    Hey there

    Quote Originally Posted by jeganthecode
    hey! I saw ur codes... really nice and compact.. so.. why dont you send me some intresting problems daily...
    The code is compact because I'm writing it without knowing exactly what I'm doing...I suppose that I'm just guessing hehehehe it's not that I'm pretty sure of what I'm doing..but thanks for the suggestion...when I have a problem I'll try to post it

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM