Thread: Link List

I made it tis way

Code:

void 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 || node1 < 0 || node2 < 0 || count < 2){cout<<"swapNodes(): illegal position!"<<endl; return;}
	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;

	}
	else if(p1==NULL && p2!=NULL && (p1 == n2 || p2 == n1)){
		
		tmp=n2->node;
		n2->node=address;
		n1->node=tmp;
		address=n2;
	
	}
	else if(p1!=NULL && p2==NULL && (p1 == n2 || p2 == n1)){
		tmp=n1->node;
		n1->node=address;
		n2->node=tmp;
		address=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;
			
		}

		else if(p1==NULL) {cout<<"NULL"<<endl;tmp= p2->node; p2->node=address; address= tmp;}
		else if(p2==NULL) {cout<<"NULL"<<endl;tmp= p1->node; p1->node=address; address= tmp;}
		else cout<<"Error in swapNode()"<<endl; 
	}
	
}
int destroyAllNodes(linklist* address){
	int count=0;
	while(address->node!=NULL) {
		count++; 
		linklist* nextNodeAddress=address->node;
		delete address;
		address=nextNodeAddress;
	}
	delete address;
	return count;
}

C++ Linked list in STL gives random access permission, doesn't it?

Originally Posted by siavoshkc

I made it tis way

... source snippet removed ...

C++ Linked list in STL gives random access permission, doesn't it?

Absolutely not. No STL data structure will ever provide random access where it would take a linear amount of time i.e. O(n)

You absolutely MUST get rid of your getNodeAddress function altogether, and stop treating a list like an array. The whole idea of performing item swaps can be totally thrown out the window when it comes to lists. Please ignore the code xeddiex posted because it too makes this same mistake!
You can reverse the list without ever having the slightest clue how long it is. This is very very important and you should think about it for a while. Get rid of that "count" variable!

Here's an exersize you can try to help shift your thinking, such that you may understand how to solve the problem:

Make a stack of something on your desk (blocks, mail, books, whatever you like). Actually put them on top of one another in a pile.
Okay, now reverse the order of the items on your desk, such that the item that is now on the top wil be on the bottom. But the catch is, you cannot touch any object except one that is on the top of a pile.
Well, the first step is easy, you simply lift the top item off the top and put it in a new pile. This one needs to go on the bottom, so it can just stay where you put it... Now keep going!

Can I make another linken list to do so?

> Can I make another linken list to do so?
I thought that was the whole essense of the problem (as iMalc kept saying).

A bit like this pseudo-code
while ( pop(list1) ) push(list2);

You've just got to make sure you push and pop from the right ends of the respective lists.

So I am going to build a new linked list with only push and pop.

Here it is:

Code:

#include<iostream>
using namespace std;

class linkedlist{
	struct node{
		int value;
		node* nextadd;
	};
	node* lHandle;
public:
	linkedlist(){
		if((lHandle = new node)!=NULL){
			lHandle->nextadd=NULL;
			lHandle->value=666;
		}
		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(address->nextadd==NULL) address->value=val;
		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(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 return lHandle->value;
	}
};

int main(){
	linkedlist ll,ll2;
	for(int i=4; i<200; i++) {ll.push(i);}
	for(int i=0; i<230; i++) ll2.push(ll.pop());
	for(int i=0; i<230; i++) cout<<ll2.pop()<<endl;
	cin.get();
	return 0;
}

How about this for an hint:

when you are halfway through, how many piles do you have on your desk? How many piles will be left when you are done? How many piles there were before you started? And... more importantly, taken into consideration the objective of the exercise, how many items will there be at all times?

I added these two methods:

Code:

int top(void){
		node* address = lHandle;
		while(address->nextadd!=NULL) address=address->nextadd;
		return address->value;
	}

	unsigned int size(void){
		unsigned int count=0;
		node* address = lHandle;
		while(address->nextadd!=NULL){ 
			address=address->nextadd;
			count++;
		}
		return count;
	}

You don't need a complicated count method - a simple isEmpty() test will suffice

while ( !isEmpty(list1) ) push(list2,pop(list1));

It wont work. The list will never be empty. It will has at least one node.