Yes indeed, and you might also want to wrap it all in a nice little class.
Yes indeed, and you might also want to wrap it all in a nice little class.
>>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
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.
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.
>> 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'
Depends on the compiler. Probably a warning at most. But the most common is to simply ignore the [] and provide no warning.Originally Posted by twomers
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.
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.
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 ...
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
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
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
Could you expand on your problems a bit.
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... };The strength of the first one (templated) is its inherent ease of use. Example: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); };
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.Code:TList<int> int_list;
>>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
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.