Link List

This is a discussion on Link List within the C++ Programming forums, part of the General Programming Boards category; Yes indeed, and you might also want to wrap it all in a nice little class....

  1. #16
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    Yes indeed, and you might also want to wrap it all in a nice little class.

  2. #17
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    >>You're heading down the wrong path!
    Why?
    My linked list can do Pop and Push with its functions. I added pop.
    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;
    	
    }
    
    int popNode(linklist* address){
    	int ret = getNodeAddress(address,-1, true)->val;
    	delete[] getNodeAddress(address,-1, false);
    	getNodeAddress(address,-1, true)->node=NULL;
    	return ret;
    }
    	
    
    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

  3. #18
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    I think it would be better in a 'nice little class', as the previous poster said! It would make lots of things lots easier!

    In your pop node function,

    >> delete[] getNodeAddress(address,-1, false);

    does that delete the array? The [] deletes arrays, just delete getNodeAddress( address, -1, false ); to delete one entry.
    Last edited by twomers; 07-28-2006 at 04:32 AM.

  4. #19
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    There's usually no difference between delete pWhatever; and delete [] pWhatever;. However, you are encouraged to use the latter on arrays.

    So yes, siavoshkc might want to remove the square bracers in his code.

  5. #20
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    >> delete pWhatever; and delete [] pWhatever;

    Well, if I have an array, and I 'delete pWhatever;', it will only delete the first element of the array. So to use that to delete an array, with that method, I'd have to loop it.

    I don't know what happens if I do 'delete []pWatever;' to a non-array. I assume it will tell me that it's not an array or something when building/debuggin'

  6. #21
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,435
    Quote Originally Posted by twomers
    I don't know what happens if I do 'delete []pWatever;' to a non-array. I assume it will tell me that it's not an array or something when building/debuggin'
    Depends on the compiler. Probably a warning at most. But the most common is to simply ignore the [] and provide no warning.
    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.

  7. #22
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    twomers> Well, if I have an array, and I 'delete pWhatever;', it will only delete the first element of the array. So to use that to delete an array, with that method, I'd have to loop it.

    As I said, a common implementation is that they are interchangeable (i.e. you can use whichever for any situation - array or not), but yes, your compiler may do it in a specific way.

  8. #23
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    I never knew that, Osaou. I was told that [] was a quick exit for the memory with respect to arrays. Didn't know they were interchangable. I suppose it kinda makes sense ... kinda ...

  9. #24
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    The standard says that using the wrong one (i.e. delete for new[] and delete[] for new) is undefined behaviour. What any specific implementation does is completely irrelevant. Don't ever do it. Don't ever let anybody tell you that it doesn't matter. Don't let anybody tell you what the effects of using the wrong one are. (Typically, they're wrong.) Just use the right one - it's really not that hard, and you avoid a lot of problems, both theoretical and practical.
    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. #25
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    Ok I will delete them but please focus on my linklist and tell me its problems. Maybe I put them in a class later don't worry about that.
    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. #26
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Your primary access functions focus on an offset and thus something resembling random access. With a linear list, where random access is O(N), that doesn't make sense.
    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

  12. #27
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    Could you expand on your problems a bit.

  13. #28
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    The two best implementations of a linked list I've seen/written is a templated one and one with abstract nodes. Doesn't matter if they're single or double linked.

    Pseudo examples:
    Code:
    template <typename T>
    class TList{
    public:
    
    	class Node{
    	public:
    
    		// linkage in list
    		TList<T>::Node *pN_previous;
    		TList<T>::Node *pN_next;
    
    		// data
    		T t_data;
    
    		Node(void);
    		...
    	};
    
    	// pointers to beginning and end of list
    	TList<T>::Node *pN_head;
    	TList<T>::Node *pN_tail;
    
    	TList(void);
    	...
    
    	void v_PushBack(T const &t_node);
    	void v_PushFront(T const &t_node);
    	...
    
    	void v_PopBack(void);
    	void v_PopFront(void);
    	...
    
    	// etcetera...
    };
    Code:
    class Node{
    public:
    
    	// linkage in list
    	Node *pN_previous;
    	Node *pN_next;
    
    private:
    
    	Node(void);
    	...
    };
    
    class AList{
    	// pointers to beginning and end of list
    	Node *pN_head;
    	Node *pN_tail;
    
    	AList(void);
    	...
    
    	void v_PushBack(Node *pN_node);
    	void v_PushFront(Node *pN_node);
    	...
    
    	void v_PopBack(void);
    	void v_PopFront(void);
    };
    The strength of the first one (templated) is its inherent ease of use. Example:
    Code:
    TList<int> int_list;
    And the second list implementation excels in speed/customization... and thus is a bit trickier to use, but will give you more freedom in more advanced scenarios.

  14. #29
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    >>Your primary access functions focus on an offset and thus something resembling random access. With a linear list, where random access is O(N), that doesn't make sense.

    In a linked list, to access any node, you should begin from the first node, that you have its address as a handle to that list. I have added this capability to access any node at any time and change it. If you send a negative number to getNodeAddress() it will return th address of the last node (readable and not readable(empty)) that is good for push and pop.
    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. #30
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    siavoshkc:

    In the program where you reverse the list internally by swapping nodes, I think you could improve the code somewhat. In my opinion:

    1) swapNodes() could be declared with return type void if you pass the first parameter as a reference to the first pointer in the node. That way if you change the address of the first node in the list done within swapNodes() it will be maintained back in main().

    2) swapNodes() should only be called if the variable called limit is greater than 1.

    3) You could pass the value of limit to swapNodes() and spare a separate call to getNodeCount() withing swapNodes().

    4) If node1 equals zero then you need to find n1, n2 and if the length of the list is longer than 2 then you need to find p2, but you don't need to find p1 as it will always be NULL.

    5) If node1 != zero, then you are swapping internal nodes and you need to find n1, n2, p1 and p2.
    Code:
    void swapNodes(linklist*& address, int node1, int node2, int count)
          //declare n1, n2, p1, p2, temp
                 	
          //always get n1 and n2                
          n1= getNodeAddress(address, node1);
          n2= getNodeAddress(address, node2);
                    
          if(count  == 2)    //swap first and last nodes in list of 2 nodes
                //address will change in this case
          else
             p2 = getNodeAddress(address, node2 - 1);
    
             if(node1 == 0)   //swapping first and last nodes in list longer than 2 nodes
                 //address will change in this case, too
             else   //swapping internal nodes
                p1= getNodeAddress(address, node1-1);
                //address will not change in this case
    You're only born perfect.

Page 2 of 4 FirstFirst 1234 LastLast
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