Link List

The way I created my generic, Linked List, class was w/an inner defined structure (chosen simply because it's public by default) that the outer class would instantiate an instance of and, therefore, keep it self contained without having to rely on a static implimentation - which would limit it to only one instance of the outer class per project:

class:

Code:

class Linker {
	struct BiDirectional {
		BiDirectional* next;
		BiDirectional* prev;
		void* pData;

		BiDirectional();
		~BiDirectional();
	};

	unsigned int counter;
	BiDirectional* head;
	BiDirectional* tail;

public:
	Linker();
	~Linker();
	void AddLink(void*);
	void* RetrieveLink(unsigned int);
	void* RetrieveLink(void*);
	void* RemoveLink(unsigned int);
	void* RemoveLink(void*);
	unsigned int Size();
};

Here's my implementation to remove any given link from doubly linked list:

Code:

void* Linker::RemoveLink(unsigned int index) {
	BiDirectional* temp = head;
	for ( unsigned int i = 0; i < counter; ++i, temp = temp->next ) {
		if ( i == index ) {
			// checks against first link
			if ( temp == head ) {
				if ( temp->next != NULL ) {
					temp->next->prev = NULL;
					head = temp->next;
					void* pData = temp->pData;
					delete temp;
					counter--;
					return pData;
				}
				else {
					head = tail = NULL;
					void* pData = temp->pData;
					delete temp;
					counter--;
					return pData;
				}
			} // checks against last link
			else if ( temp == tail ) {
				temp->prev->next = NULL;
				tail = temp->prev;
				void* pData = temp->pData;
				delete temp;
				counter--;
				return pData;
			} // checks against middle links
			else {
				temp->prev->next = temp->next;
				temp->next->prev = temp->prev;
				void* pData = temp->pData;
				delete temp;
				counter--;
				return pData;
			}
		}
	}

	// no match
	return NULL;
}

I hope that's of any help.

Originally Posted by siavoshkc

>>You're heading down the wrong path!
Why?
My linked list can do Pop and Push with its functions. I added pop.

Because you have about 20 times more lines of code than you actually need! The solution should be about 10-20 lines of code, TOTAL! Push and Pop were a massive hint. That's basically about all you need!

You absolutely MUST stop treating a list like an array. By that I mean, looking up an item by index should be TOTALLY FORBIDDEN!
Never, and I mean NEVER EVER use a linked list like that. Not in a million years!

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!

iMalc wins the internet.

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

Algorithm-wise it looks alot better than your last one!

Personally I don't really like the way you format your code nor the names you choose, but that's not really on topic and is a matter of taste I guess. =)

Originally Posted by iMalc

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!

Sorry about posting that bad code then . Given your exercise, how would I go about reversing the order with only being able to move the top book? I can think of a couple of ways but, I don't think they're right... I need more hints.

Thanks

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.