Thread: Link List

>>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;
}

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.

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 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.

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.

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.

>>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.

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