Thread: Link List

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

    Link List

    I am solving the helpfree challenge in the main site "In-Place linked list reversing"

    My problem is that I don't know what link list should I use. I made a simple one
    Code:
    struct lilist{
    	int val;
    	lilist* node;
    } ;
    lilist *fad;
    lilist* listinit(){
    	fad=new lilist;
    	return fad;
    }
    lilist* put(int p){
    	static lilist *ad=fad;
    	ad->val=p;
    	ad->node=new lilist;
    	ad->node->node=NULL;
    	//cout<<ad<<"  "<<ad->node<<endl;
    	ad=ad->node;
    	
    	return ad->node;
    }
    
    int get(bool f=false){
    	static lilist* as = fad;
    	if(f) {as=fad; return 0;}
    	int ret=as->val;
    
    	if(as->node!= NULL) 
    		as=as->node;
    	else return 0;
    	return ret;
    
    }
    Is this enough for the challenge?
    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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Can you do it without using any static variables or any globals?

    Neither are very good if you want to make a list which is useful.
    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.

  3. #3
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    I think I can. But because challenge is not about making a link list, I don't want to wast my time on it. I only want to know if my LL functionality is enough for challenge or not.
    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

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Depends on how you plan to reverse it.

    I guess you could try it as it stands, and see what happens.
    If it doesn't work, at least you'll learn something.
    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.

  5. #5
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    Please read the challenge and tell me is this possible or not.
    http://www.cprogramming.com/helpfree.html
    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

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Jeez, you could have done it by now and found the answer.

    It's just another "will this work?" thread.
    The answer being "why don't you spend 5 minutes finding out rather than wasting hours on a message board thread" (looks at clock - 1h45m gone already).

    If I say "yes", and you can't do it, what are you going to do - blame me for bad advice ?
    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.

  7. #7
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    I don't know what an standard link list needs.
    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
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    It needs a pointer to the next element in the list
    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.

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    If I understand "in-place" correctly, it would be a lot simpler with a double-linked list, where you should have a pointer to the previous node, too.

    But maybe I misunderstand it and you can use the simple implementation.
    Code:
    while node is not null
      temp = node->next
      node->next = othernode
      othernode = node
      node = temp
    end while
    head = othernode
    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

  10. #10
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    It should be singly linked list.
    I am going to build a more advanced link list, I will place it here.
    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

  11. #11
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    This is my new linked list no globals no statics
    Code:
    struct linklist{
    	int val;
    	linklist* node;
    } ;
    
    linklist* list_init(){
    	linklist *address =new linklist;
    	address->node=NULL;
    	return (address);
    }
    
    linklist* getNodeAddress(linklist* address, int pos=-1){
    	if(pos>=0) 
    		for(int i = 0; i<pos;i++)
    			if(address->node!=NULL) address=address->node;
    			else break;
    	else
    		while(address->node!=NULL) address=address->node;
    	return address;
    }
    
    int getNodeValue(linklist* address, int pos=-1){
    	return getNodeAddress(address, pos)->val;
    }
    
    void setNodeValue(linklist* address,int value, int pos=-1){
    	address=getNodeAddress(address, pos);
    	address->val=value;
    	address->node=new linklist;
    	address->node->node = NULL;
    }
    
    int getNodeCount(linklist* address){
    	int count=0;
    	while(address->node!=NULL) {
    		count++; 
    		address=address->node;	
    	}
    	return count;
    }
    
    int destroyAllNodes(linklist* address){
    	int count=0;
    	while(address->node!=NULL) {
    		count++; 
    		linklist* nextNodeAddress=address->node;
    		delete[] address;
    		address=nextNodeAddress;
    	}
    	delete[] address;
    	return count;
    }
    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. #12
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    Here is the debugged version with a test code
    Code:
    #include<iostream>
    using namespace std;
    
    struct linklist{
    	int val;
    	linklist* node;
    } ;
    
    linklist* list_init(){
    	linklist *address =new linklist;
    	address->node=NULL;
    	return (address);
    }
    int getNodeCount(linklist* address){
    	int count=0;
    	while(address->node!=NULL) {
    		count++; 
    		address=address->node;	
    	}
    	return count;
    }
    
    linklist* getNodeAddress(linklist* address, int pos=-1, bool read=false){
    	if(pos>=0)
    		for(int i = 0; i<pos;i++)
    			if(address->node!=NULL && !(read && address->node->node==NULL)) 
    				address=address->node;
    			
    			else break;
    	else
    		while(address->node!=NULL && !(read && address->node->node==NULL)) address=address->node;
    	return address;
    }
    
    
    int getNodeValue(linklist* address, int pos=-1){
    	return getNodeAddress(address,pos,true)->val;
    	
    }
    
    void setNodeValue(linklist* address,int value, int pos=-1){
    	int nCount=getNodeCount(address);
    	if(pos>nCount) throw 1;
    	address=getNodeAddress(address, pos);
    	if(address->node!=NULL) address->val=value;
    	else {
    		address->val=value;
    		address->node=new linklist;
    		address->node->node = NULL;
    	}
    }
    
    
    int destroyAllNodes(linklist* address){
    	int count=0;
    	while(address->node!=NULL) {
    		count++; 
    		linklist* nextNodeAddress=address->node;
    		delete[] address;
    		address=nextNodeAddress;
    	}
    	delete[] address;
    	return count;
    }
    
    int main(){
    	linklist *hList = list_init();
    	
    	for(int i=0;i<10;i++) setNodeValue(hList,i);
    	int limit = getNodeCount(hList);
    
    	for(int i=0; i<limit/2;i++){
    		int p =getNodeValue(hList,limit-i-1);
    		setNodeValue(hList,getNodeValue(hList,i),limit-i-1);
    		setNodeValue(hList,p,i);	
    	}
    
    	limit = getNodeCount(hList);
    	cout<<"After reverse"<<endl;
    	for(int i=0; i<limit;i++) cout<<getNodeValue(hList,i)<<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

  13. #13
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    The latest code seems to reverse the values in the list but leaves the nodes in place, which would be one way to reverse the values. To test your understanding of linked lists can you do it by switching nodes rather than values in nodes? For example, you could switch the first node with the last, the second node with the second to last node, the third node with the third to last node, etc.

    for(i = 0; i < halfTheNodesInTheList; ++i)
    FindNodeA
    FindNodeB
    SwitchNodesAandB
    You're only born perfect.

  14. #14
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    I did something:
    Code:
    #include<iostream>
    using namespace std;
    
    struct linklist{
    	int val;
    	linklist* node;
    } ;
    
    linklist* list_init(){
    	linklist *address =new linklist;
    	address->node=NULL;
    	return (address);
    }
    int getNodeCount(linklist* address){
    	int count=0;
    	while(address->node!=NULL) {
    		count++; 
    		address=address->node;	
    	}
    	return count;
    }
    
    linklist* getNodeAddress(linklist* address, int pos=-1, bool read=false){
    	if(pos>=0)
    		for(int i = 0; i<pos;i++)
    			if(address->node!=NULL && !(read && address->node->node==NULL)) 
    				address=address->node;
    			
    			else break;
    	else
    		while(address->node!=NULL && !(read && address->node->node==NULL)) address=address->node;
    	return address;
    }
    
    
    int getNodeValue(linklist* address, int pos=-1){
    	return getNodeAddress(address,pos,true)->val;
    	
    }
    
    void setNodeValue(linklist* address,int value, int pos=-1){
    	int nCount=getNodeCount(address);
    	if(pos>nCount) throw 1;
    	address=getNodeAddress(address, pos);
    	if(address->node!=NULL) address->val=value;
    	else {
    		address->val=value;
    		address->node=new linklist;
    		address->node->node = NULL;
    		address->node->val = 666;
    	}
    }
    
    linklist* swapNodes(linklist* address, int node1, int node2){
    	linklist* n1=NULL,*n2=NULL,*p1=NULL,*p2=NULL,*tmp;
    	cout<<node1<<"  "<<node2<<endl;
    	int count=getNodeCount(address);
    	if(node1 > count || node2 >count){cout<<"if"<<endl; return NULL;}
    	if(node1 > -1){ n1= getNodeAddress(address, node1);}
    	if(node2 > -1)  n2= getNodeAddress(address, node2);
    	if(node1-1 >= 0)  p1= getNodeAddress(address, node1-1);
    	else p1 = NULL;
    	if(node2-1 >= 0)  p2= getNodeAddress(address, node2-1);
    	else p2= NULL;
    	if(p1!=NULL && p2!=NULL && (p1 == n2 || p2 == n1)) {
    		p1->node=n1->node;
    		tmp=n2->node;
    		n2->node=n1;
    		n1->node=tmp;
    		return address;
    	}
    	else if(p1==NULL && p2!=NULL && (p1 == n2 || p2 == n1)){
    		
    		tmp=n2->node;
    		n2->node=address;
    		n1->node=tmp;
    		return n2;
    	
    	}
    	else if(p1!=NULL && p2==NULL && (p1 == n2 || p2 == n1)){
    		tmp=n1->node;
    		n1->node=address;
    		n2->node=tmp;
    		return n1;
    	}
    	else{
    		tmp= n1->node;
    		n1->node=n2->node;
    		n2->node= tmp;
    	
    	
    		if(p1!=NULL && p2!= NULL){
    			tmp=p1->node;
    			p1->node=p2->node;
    			p2->node=tmp;
    			return address;
    		}
    
    		else if(p1==NULL) {cout<<"NULL"<<endl;tmp= p2->node; p2->node=address; return tmp;}
    		else if(p2==NULL) {cout<<"NULL"<<endl;tmp= p1->node; p1->node=address; return tmp;}
    		else {cout<<"else"<<endl; return NULL;}
    	}
    	
    }
    int destroyAllNodes(linklist* address){
    	int count=0;
    	while(address->node!=NULL) {
    		count++; 
    		linklist* nextNodeAddress=address->node;
    		delete[] address;
    		address=nextNodeAddress;
    	}
    	delete[] address;
    	return count;
    }
    
    int main(){
    	linklist *hList = list_init();
    	
    	for(int i=0;i<10;i++) setNodeValue(hList,i);
    	int limit = getNodeCount(hList);
    	for(int i=0; i<limit;i++) cout<<getNodeAddress(hList,i)<<" -> "<<getNodeAddress(hList,i)->node<<"  "<<getNodeValue(hList,i)<<endl;
    	for(int i=0; i<limit/2;i++){
    		int p =getNodeValue(hList,limit-i-1);
    		setNodeValue(hList,getNodeValue(hList,i),limit-i-1);
    		setNodeValue(hList,p,i);	
    	}
    	
    		
    
    	limit = getNodeCount(hList);
    	cout<<"After reverse"<<endl;
    	for(int i=0; i<limit;i++) cout<<getNodeAddress(hList,i)<<" -> "<<getNodeAddress(hList,i)->node<<"  "<<getNodeValue(hList,i)<<endl;
    	cout<<endl;
    	for(int i=0; i<limit/2;i++){
    		if((hList = swapNodes(hList,i,limit-i-1)) == NULL) break;
    	}
    	for(int i=0; i<limit;i++) cout<<getNodeAddress(hList,i)<<" -> "<<getNodeAddress(hList,i)->node<<"  "<<getNodeValue(hList,i)<<endl;
    	cout<<endl;
    	hList = swapNodes(hList,0,1);
    	for(int i=0; i<limit;i++) cout<<getNodeAddress(hList,i)<<" -> "<<getNodeAddress(hList,i)->node<<"  "<<getNodeValue(hList,i)<<endl;
    	cout<<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

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You're heading down the wrong path!

    I suggest learning the concept of Push, and Pop, in terms of stacks implemented using linked lists.

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. Link List Insert prob
    By Bebs in forum C Programming
    Replies: 8
    Last Post: 12-03-2008, 10: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, 10:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM