Link List

This is a discussion on Link List within the C++ Programming forums, part of the General Programming Boards category; Well yeah if you have such a thing as a dummy node. You've just moved the problem away from a ...

  1. #46
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    Well yeah if you have such a thing as a dummy node.

    You've just moved the problem away from a simple test in append to lots of ickyness in skipping the junk node everywhere else in the code.

    My lists begin with
    list = NULL; // an empty list

    while ( list != NULL ) // traverse the list

    Anything else just adds baggage IMO.
    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.

  2. #47
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    What about this?
    Code:
    #include<iostream>
    using namespace std;
    
    class linkedlist{
    	struct node{
    		int value;
    		node* nextadd;
    	};
    	node* lHandle;
    	bool bisEmpty;
    
    public:
    	linkedlist(){
    		if((lHandle = new node)!=NULL){
    			lHandle->nextadd=NULL;
    			lHandle->value=666;
    			bisEmpty = true;
    		}
    		else
    			cerr<<"ERROR: Linked list cannot be initialized!"<<endl;
    	}
    	~linkedlist(){
    		node* address=lHandle;
    		node *ad=NULL;
    		while(address->nextadd!=NULL){ 
    			ad=address->nextadd;
    			delete address;
    			address=ad;
    		}
    		if(ad!=NULL) delete ad;
    	}
    	void push(int val){
    		node* address=lHandle;
    		if(bisEmpty) {
    			address->value=val; 
    			bisEmpty = false;
    		}
    		else{
    			while(address->nextadd!=NULL) address=address->nextadd;
    			address->nextadd=new node;
    			address->nextadd->value=val;
    			address->nextadd->nextadd=NULL;
    		}
    	}
    	int pop(void){
    		node* address=lHandle;
    		if(!bisEmpty){
    			if(address->nextadd!=NULL){
    				while(address->nextadd->nextadd !=NULL) address=address->nextadd;
    				int val = address->nextadd->value;
    				delete address->nextadd;
    				address->nextadd=NULL;
    				return val;
    			}
    			else{
    				bisEmpty=true;
    				address->nextadd = NULL;
    				return lHandle->value;
    			}
    		}
    		else 
    			return 666;
    	}
    	
    	int top(void){
    		if(!bisEmpty){
    			node* address = lHandle;
    			while(address->nextadd!=NULL) address=address->nextadd;
    			return address->value;
    		}
    		else
    			return 666;
    	}
    
    	bool isEmpty(void){
    		return bisEmpty;
    	}
    
    };
    
    int main(){
    	linkedlist ll;
    	cout<<"Empty? "<<ll.isEmpty()<<endl;
    
    	for(int i=0;i<10;i++)ll.push(i);
    	cout<<"Empty? "<<ll.isEmpty()<<endl;
    
    	for(int i=0;i<5;i++) cout<<ll.pop()<<endl;
    	cout<<endl<<"Empty? "<<ll.isEmpty()<<endl;
    
    	for(int i=0;i<5;i++) cout<<ll.pop()<<endl;
    	cout<<endl<<"Empty? "<<ll.isEmpty()<<endl;
    	
    
    	cin.get();
    	return 0;
    }
    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

  3. #48
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Well I am happy to say you are definately on the right track now. Just one slight mixup at the moment. Your push, pop and top functions have the right idea, however they are actually operating on the wrong end of the list. I can remember back when I learnt these things, that one's instinct is to deal with the tail end of the list, but that turns out to be much more difficult.
    A 'push' is the operation of placing something before all items, on the start of the list (not at the end, that is actually called a 'put', and is normally done using a tail pointer anyway, which I wont go into here)
    A 'pop' is to remove the first item from the list, not the last item. There isn't really a name given to removing the last item as it is not something you generally do. It falls back to requiring O(n) time which means that it is bad.
    A 'peek' as most would call it (or 'top' if you prefer) is to only examine the first item in the list (if it exists).
    So, all three of the functions actually only deal with the very first item in the list. They never have to scan through the list to the end.

    You'll notice that when you make changes to which item is at the front of the list, you keep having to update the pointer to the rest of the list. Don't worry about that. The variable storing the head of the list wont move anywhere, so you can happily update it at will. What you have actually done in your case, is put what is called a 'sentinel' node at the start of your list, which contains the value 666, so you don't have to update 'lHandle'. That is okay, and if it makes things easier for now, then all the better. It is a valid practice and certainly has its uses. When you have the rest of the problem sorted out however, I would go back and try doing away with the sentinel node, but by all means wait until the rest of this is sorted.

    Now, you're correct that often when you perform a 'pop' you return the value of the node being popped. However in this case it is actually more useful to pop the entire linked-list node off the top of the list, because the goal is to end up with the same number of items in the final list, so you can save having to delete and re-create any, but simply changing what the nodes point to, and what points to them. In this manner, you end up simply reordering the nodes in the list themselves.

    By now, you quite likely have figured out that the thing with the books involves taking a book of one pile one at a time, and placing it on top of the other pile. It might still seem wrong or even as though it's cheating, at this stage, but it is where you want to be heading. Sure, you end up with the reversed pile sitting in a different place to the original piles was. But hey, in a PC you're dealing with pointers . It doesn't matter where they point to, so long as what they point to is a list of nodes (or NULL). So really, you have achieved your goal afterall.

    Let us know how you get on. Good on you for sticking at it anyway. Everyone went through a similiar learning process with this same task at some stage. Those of us who already know the answer often don't appreciate how much we truly have learnt.

    When you're done, for another challenge you could try finding the recursive solution

  4. #49
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231

    Lightbulb

    First I wish to thank you for spending time on it, iMalc.
    I know about stack, LIFO and FIFO. What I didn't know was that a linked list should be like a LIFO stack. This is why I opened this thread. Nobody answered my question that was "How a standard linked list should behave?". Your last post was the answer.

    Now, you're correct that often when you perform a 'pop' you return the value of the node being popped. However in this case it is actually more useful to pop the entire linked-list node off the top of the list, because the goal is to end up with the same number of items in the final list, so you can save having to delete and re-create any, but simply changing what the nodes point to, and what points to them. In this manner, you end up simply reordering the nodes in the list themselves.
    I didn't understand the goal of this paragraph.

    What I understood:
    1) Only deal with the first item in the linked list chain, because dealing with last item requires O(n) time (Linear time).

    2) We will do something to sentinel node later.
    OK, now I am going to rewrite a linked list with this specifications:
    It has:
    Code:
    int pop();   //Reads the first node then deletes it. (Does returning vlaue make any problem?)
    int push(int i);  //Inserts i into list from the back.
    bool isEmpty();  //Checks for list emptiness, it is actually the peek() you mentioned.
    Thats all it needs. Right? Just tell me what it should be.
    ---------------------------------------------------------------------------------------------------------------------
    I took a look at <vector> reference. It is a linked list, isn't it?
    It has a size() function.
    It has operator[] that returns a reference to the vector element at a specified position.
    It has insert() which inserts an element or a number of elements into the vector at a specified position.
    Why it has random access facilities?
    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

  5. #50
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    Hm... Let's get one thing straight here. A linked list have nothing to do with the order in which nodes are placed and/or taken off... In other words, it doesn't matter if it's LIFO, FIFO or random access.
    A stack is easily implemented by using a linked list structure, but it doesn't require it, nor vice versa.

    The definition of a linked list (in computer science) is basically a type of array that isn't guaranteed to be sequential in relation to memory positions - i.e. its items/nodes are not guaranteed to follow one after the other. And you usually only have one or two entry points (front and/or tail).

    Giving a linked list class random access facilities is a double edged sword.
    It is not suitable for a stack, but might be sweet for a vector-like structure. However, the user should be aware of the implications with such a facility.

    Consider the following two code snippets:
    Code:
    1: {
    	int choice;
    	List accounts;
    
    	cout << "Input which bank account you wish to print: ";
    	cin >> choice;
    
    	cout << "Account balance: " << accounts[choice];
    }
    
    2: {
    	List accounts;
    
    	// print all bank accounts
    	for (int i=0; i<accounts.size(); i++){
    		cout << "Account balance: " << accounts[i];
    	}
    }
    In the first example, it's quite OK to use random access, because we don't want that code to worry about the account list being a linked list at all (this would make the code harder to follow), and we only make one call to the []-operator.

    However, the second code listing is a disaster. It undermines the whole idea of a linked list! Why not just traverse the list node-to-node and print them?

    As you can see, random access comes with a responsibility. std::vector implements it, sure, but it also lets you use its iterator class for more "low level" access.


    Edit:

    And yeah, many single linked lists implements a LIFO algorithm, as iMalc suggested. Although, as I said earlier, it isn't a necessity.

    Double linked lists often have support for pushing and poping at both ends...

    And also, the std::vector class is not a linked list, it's a normal array dressed in a princess dress, actually.
    Last edited by Osaou; 07-31-2006 at 07:45 AM.

  6. #51
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    Here is the new linked list with a test program that compares its speed to a vector.
    Code:
    #include<iostream>
    #include<vector>
    #include<windows.h>
    using namespace std;
    
    class linkedlist{
    	struct node{
    		int value;
    		node* nextadd;
    	};
    	node* lHandle;
    	bool bisEmpty;
    
    public:
    	linkedlist(){
    		bisEmpty=true;	
    	}
    
    	~linkedlist(){
    		if(!bisEmpty){
    			while(lHandle->nextadd!=NULL){
    				node* adr = lHandle->nextadd;
    				delete lHandle;
    				lHandle = adr;
    			}
    			delete lHandle;
    		}
    	}
    
    	void push(int val){
    		if(bisEmpty){
    			lHandle= new node;
    			lHandle->value=val;
    			lHandle->nextadd=NULL;
    			bisEmpty = false;
    		}
    		else{
    			node* adr= new node;
    			adr->nextadd=lHandle;
    			adr->value = val;
    			lHandle = adr;
    		}
    	}
    	void pop(void){
    		if(!bisEmpty){
    			node* adr = lHandle->nextadd;
    			delete lHandle;
    			lHandle=adr;
    			if(lHandle == NULL) bisEmpty=true;
    		}
    	}
    	int top(void){
    		return lHandle->value;
    	}
    
    	bool isEmpty(void){
    		return bisEmpty;
    	}
    
    };
    
    int main(){
    	linkedlist ll;
    	vector<int> vec;
    	int a=0,b=0;
    	DWORD llinit=GetTickCount();
    	for(int i=2;i<5000000;i++) ll.push(i);
    	llinit=GetTickCount()-llinit;
    	
    	DWORD vecinit=GetTickCount();
    	for(int i=2;i<5000000;i++) vec.push_back(i);
    	vecinit=GetTickCount()-vecinit;
    
    	DWORD llpop = GetTickCount();
    	for(int i=2;i<5000000;i++){
    		a=ll.top();
    		ll.pop();
    	}
    	llpop=GetTickCount()-llpop;
    	cout<<a<<endl;
    
    	DWORD vecpop=GetTickCount();
    	for(int i=2;i<5000000;i++){
    		b=vec.back();
    		vec.pop_back();
    	}
    	vecpop=GetTickCount()-vecpop;
    	cout<<b<<endl;
    
    	cout<<"Vecinit: "<< vecinit<<"  Vecpop: "<<vecpop<<endl;
    	cout<<"LLinit: "<<llinit<<"  LLpop: "<<llpop<<endl;
    
    	cin.get();
    	return 0;
    }
    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

  7. #52
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    As a learning exercise, the original post was about

    "In-Place linked list reversing"
    To me, this means there will be only one linked list, not two, used in the process of reversal, irrespective of how inefficient or array like the process is. So far, there have been two solutions presented, swap values in nodes and swap nodes within the same list using array like manipulations of the list. A third solution has been proposed, recursion. The schemata for that could be based on either of the prior solutions or on something like this:

    Version 1:
    Call the first node targetNode.
    Always remove the last node of the list, setting the new last nodes pointer to NULL
    Always reinsert the popped node immediately to the left of targetNode.
    Stop when targetNodes pointer is NULL

    OR

    Version 2:
    Call the last node of the list targetNode.
    Always remove the first node in the list, changing value of the head node with each extraction.
    Always reinsert the extracted node immediately to right of targetNode
    Stop when head node == targetNode

    Either of which could be implemented using either iteration or recursion, though there may be reasons to prefer one version over the other from a theoretical standpoint. From a learning standpoint, implementing both versions could be educational, or boring, depending how comfortable you are manipulating linked lists and pointers using your own code; which, IMO, was the point of the challenge in the first place.
    You're only born perfect.

  8. #53
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    To me, in-place linked list manipulation simply means not allocating new nodes. Under this interpretation, you can use the simple pop-push mechanism, by building a new list from the nodes of the old.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #54
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    I am going to find out what a normal linked list requires, then I will solve the reversing problem. I am waiting for the iMalc response to know his idea about my last code.
    Last edited by siavoshkc; 07-31-2006 at 02:13 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

  10. #55
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    To me, in-place linked list manipulation simply means not allocating new nodes.
    Seems reasonable, too, now that you point it out. So depending how you interpret what "in-place" means, go either way.
    You're only born perfect.

  11. #56
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    A bug in top() discovered. And vector replaced by stack.
    Code:
    #include<iostream>
    #include<stack>
    #include<windows.h>
    using namespace std;
    
    class linkedlist{
    	struct node{
    		int value;
    		node* nextadd;
    	};
    	node* lHandle;
    	bool bisEmpty;
    
    public:
    	linkedlist(){
    		bisEmpty=true;	
    	}
    
    	~linkedlist(){
    		if(!bisEmpty){
    			while(lHandle->nextadd!=NULL){
    				node* adr = lHandle->nextadd;
    				delete lHandle;
    				lHandle = adr;
    			}
    			delete lHandle;
    		}
    	}
    
    	void push(int val){
    		if(bisEmpty){
    			lHandle= new node;
    			lHandle->value=val;
    			lHandle->nextadd=NULL;
    			bisEmpty = false;
    		}
    		else{
    			node* adr= new node;
    			adr->nextadd=lHandle;
    			adr->value = val;
    			lHandle = adr;
    		}
    	}
    	void pop(void){
    		if(!bisEmpty){
    			node* adr = lHandle->nextadd;
    			delete lHandle;
    			lHandle=adr;
    			if(lHandle == NULL) bisEmpty=true;
    		}
    	}
    	int top(void){
    		if(!bisEmpty)
    			return lHandle->value;
    		else
    			return 666;
    	}
    
    	bool isEmpty(void){
    		return bisEmpty;
    	}
    
    };
    
    int main(){
    	linkedlist ll;
    	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;
    }
    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

  12. #57
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,434
    A shame that at some point during your experiments you decided to make your code non portable. All because of a single windows.h typedef
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  13. #58
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    Why have:

    Code:
    struct node
    {
    	int value;
    	node* nextadd;
    };
    inside the class? Wouldn't
    it make more sense to put
    it outside? no?

  14. #59
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    >>A shame that at some point during your experiments you decided to make your code non portable. All because of a single windows.h typedef

    Only a typedef? What about GetTickCount()? Finally it is only a speed test you can ignore main().

    inside the class? Wouldn't
    it make more sense to put
    it outside? no?
    Class has private access to nodes so struct should be in the class.
    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

  15. #60
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    With overloaded operators:
    Code:
    class linkedlist{
    	struct node{
    		int value;
    		node* nextadd;
    	};
    	node* lHandle;
    	bool bisEmpty;
    
    public:
    	linkedlist(){
    		bisEmpty=true;	
    	}
    
    	~linkedlist(){
    		if(!bisEmpty){
    			while(lHandle->nextadd!=NULL){
    				node* adr = lHandle->nextadd;
    				delete lHandle;
    				lHandle = adr;
    			}
    			delete lHandle;
    		}
    	}
    
    	void push(int val){
    		if(bisEmpty){
    			lHandle= new node;
    			lHandle->value=val;
    			lHandle->nextadd=NULL;
    			bisEmpty = false;
    		}
    		else{
    			node* adr= new node;
    			adr->nextadd=lHandle;
    			adr->value = val;
    			lHandle = adr;
    		}
    	}
    	void pop(void){
    		if(!bisEmpty){
    			node* adr = lHandle->nextadd;
    			delete lHandle;
    			lHandle=adr;
    			if(lHandle == NULL) bisEmpty=true;
    		}
    	}
    	int top(void){
    		if(!bisEmpty)
    			return lHandle->value;
    		else
    			return 666;
    	}
    
    	bool isEmpty(void){
    		return bisEmpty;
    	}
    	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{
    			while(1){
    				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;
    				}
    			}
    	
    		}
    	}
    	bool operator>=(linkedlist &righth){
    		return !(operator<(righth));
    	}
    	bool operator<=(linkedlist &righth){
    		return !(operator>(righth));
    	}
    	bool operator!= ( linkedlist &righth){
    		return !(operator==(righth));
    	}
    
    };
    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

Page 4 of 4 FirstFirst 1234
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, 03:09 AM
  2. Link List Insert prob
    By Bebs in forum C Programming
    Replies: 8
    Last Post: 12-03-2008, 09:28 PM
  3. reading data from a file - link list
    By peter_hii in forum C++ Programming
    Replies: 7
    Last Post: 10-25-2006, 09:11 AM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 09:16 AM
  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