Link List

**Salem** · 07-30-2006

Well yeah if you have such a thing as a dummy node.

You've just moved the problem away from a simple test in append to lots of ickyness in skipping the junk node everywhere else in the code.

My lists begin with
list = NULL; // an empty list

while ( list != NULL ) // traverse the list

Anything else just adds baggage IMO.

**siavoshkc** · 07-30-2006

What about this?

Code:

#include<iostream>
using namespace std;

class linkedlist{
	struct node{
		int value;
		node* nextadd;
	};
	node* lHandle;
	bool bisEmpty;

public:
	linkedlist(){
		if((lHandle = new node)!=NULL){
			lHandle->nextadd=NULL;
			lHandle->value=666;
			bisEmpty = true;
		}
		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(bisEmpty) {
			address->value=val; 
			bisEmpty = false;
		}
		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(!bisEmpty){
			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{
				bisEmpty=true;
				address->nextadd = NULL;
				return lHandle->value;
			}
		}
		else 
			return 666;
	}
	
	int top(void){
		if(!bisEmpty){
			node* address = lHandle;
			while(address->nextadd!=NULL) address=address->nextadd;
			return address->value;
		}
		else
			return 666;
	}

	bool isEmpty(void){
		return bisEmpty;
	}

};

int main(){
	linkedlist ll;
	cout<<"Empty? "<<ll.isEmpty()<<endl;

	for(int i=0;i<10;i++)ll.push(i);
	cout<<"Empty? "<<ll.isEmpty()<<endl;

	for(int i=0;i<5;i++) cout<<ll.pop()<<endl;
	cout<<endl<<"Empty? "<<ll.isEmpty()<<endl;

	for(int i=0;i<5;i++) cout<<ll.pop()<<endl;
	cout<<endl<<"Empty? "<<ll.isEmpty()<<endl;
	

	cin.get();
	return 0;
}

**iMalc** · 07-31-2006

Well I am happy to say you are definately on the right track now. Just one slight mixup at the moment. Your push, pop and top functions have the right idea, however they are actually operating on the wrong end of the list. I can remember back when I learnt these things, that one's instinct is to deal with the tail end of the list, but that turns out to be much more difficult.
A 'push' is the operation of placing something before all items, on the start of the list (not at the end, that is actually called a 'put', and is normally done using a tail pointer anyway, which I wont go into here)
A 'pop' is to remove the first item from the list, not the last item. There isn't really a name given to removing the last item as it is not something you generally do. It falls back to requiring O(n) time which means that it is bad.
A 'peek' as most would call it (or 'top' if you prefer) is to only examine the first item in the list (if it exists).
So, all three of the functions actually only deal with the very first item in the list. They never have to scan through the list to the end.

You'll notice that when you make changes to which item is at the front of the list, you keep having to update the pointer to the rest of the list. Don't worry about that. The variable storing the head of the list wont move anywhere, so you can happily update it at will. What you have actually done in your case, is put what is called a 'sentinel' node at the start of your list, which contains the value 666

, so you don't have to update 'lHandle'. That is okay, and if it makes things easier for now, then all the better. It is a valid practice and certainly has its uses. When you have the rest of the problem sorted out however, I would go back and try doing away with the sentinel node, but by all means wait until the rest of this is sorted.

Now, you're correct that often when you perform a 'pop' you return the value of the node being popped. However in this case it is actually more useful to pop the entire linked-list node off the top of the list, because the goal is to end up with the same number of items in the final list, so you can save having to delete and re-create any, but simply changing what the nodes point to, and what points to them. In this manner, you end up simply reordering the nodes in the list themselves.

By now, you quite likely have figured out that the thing with the books involves taking a book of one pile one at a time, and placing it on top of the other pile. It might still seem wrong or even as though it's cheating, at this stage, but it is where you want to be heading. Sure, you end up with the reversed pile sitting in a different place to the original piles was. But hey, in a PC you're dealing with pointers

. It doesn't matter where they point to, so long as what they point to is a list of nodes (or NULL). So really, you have achieved your goal afterall.

Let us know how you get on. Good on you for sticking at it anyway. Everyone went through a similiar learning process with this same task at some stage. Those of us who already know the answer often don't appreciate how much we truly have learnt.

When you're done, for another challenge you could try finding the recursive solution

**siavoshkc** · 07-31-2006

First I wish to thank you for spending time on it, iMalc.
I know about stack, LIFO and FIFO. What I didn't know was that a linked list should be like a LIFO stack. This is why I opened this thread. Nobody answered my question that was "How a standard linked list should behave?". Your last post was the answer.

Now, you're correct that often when you perform a 'pop' you return the value of the node being popped. However in this case it is actually more useful to pop the entire linked-list node off the top of the list, because the goal is to end up with the same number of items in the final list, so you can save having to delete and re-create any, but simply changing what the nodes point to, and what points to them. In this manner, you end up simply reordering the nodes in the list themselves.

I didn't understand the goal of this paragraph.

What I understood:
1) Only deal with the first item in the linked list chain, because dealing with last item requires O(n) time (Linear time).

2) We will do something to sentinel node later.
OK, now I am going to rewrite a linked list with this specifications:
It has:

Code:

int pop();   //Reads the first node then deletes it. (Does returning vlaue make any problem?)
int push(int i);  //Inserts i into list from the back.
bool isEmpty();  //Checks for list emptiness, it is actually the peek() you mentioned.

Thats all it needs. Right? Just tell me what it should be.
---------------------------------------------------------------------------------------------------------------------
I took a look at <vector> reference. It is a linked list, isn't it?
It has a size() function.
It has operator[] that returns a reference to the vector element at a specified position.
It has insert() which inserts an element or a number of elements into the vector at a specified position.
Why it has random access facilities?

**Osaou** · 07-31-2006

Hm... Let's get one thing straight here. A linked list have nothing to do with the order in which nodes are placed and/or taken off... In other words, it doesn't matter if it's LIFO, FIFO or random access.
A stack is easily implemented by using a linked list structure, but it doesn't require it, nor vice versa.

The definition of a linked list (in computer science) is basically a type of array that isn't guaranteed to be sequential in relation to memory positions - i.e. its items/nodes are not guaranteed to follow one after the other. And you usually only have one or two entry points (front and/or tail).

Giving a linked list class random access facilities is a double edged sword.
It is not suitable for a stack, but might be sweet for a vector-like structure. However, the user should be aware of the implications with such a facility.

Consider the following two code snippets:

Code:

1: {
	int choice;
	List accounts;

	cout << "Input which bank account you wish to print: ";
	cin >> choice;

	cout << "Account balance: " << accounts[choice];
}

2: {
	List accounts;

	// print all bank accounts
	for (int i=0; i<accounts.size(); i++){
		cout << "Account balance: " << accounts[i];
	}
}

In the first example, it's quite OK to use random access, because we don't want that code to worry about the account list being a linked list at all (this would make the code harder to follow), and we only make one call to the []-operator.

However, the second code listing is a disaster. It undermines the whole idea of a linked list! Why not just traverse the list node-to-node and print them?

As you can see, random access comes with a responsibility. std::vector implements it, sure, but it also lets you use its iterator class for more "low level" access.

Edit:

And yeah, many single linked lists implements a LIFO algorithm, as iMalc suggested. Although, as I said earlier, it isn't a necessity.

Double linked lists often have support for pushing and poping at both ends...

And also, the std::vector class is not a linked list, it's a normal array dressed in a princess dress, actually.

**siavoshkc** · 07-31-2006

Here is the new linked list with a test program that compares its speed to a vector.

Code:

#include<iostream>
#include<vector>
#include<windows.h>
using namespace std;

class linkedlist{
	struct node{
		int value;
		node* nextadd;
	};
	node* lHandle;
	bool bisEmpty;

public:
	linkedlist(){
		bisEmpty=true;	
	}

	~linkedlist(){
		if(!bisEmpty){
			while(lHandle->nextadd!=NULL){
				node* adr = lHandle->nextadd;
				delete lHandle;
				lHandle = adr;
			}
			delete lHandle;
		}
	}

	void push(int val){
		if(bisEmpty){
			lHandle= new node;
			lHandle->value=val;
			lHandle->nextadd=NULL;
			bisEmpty = false;
		}
		else{
			node* adr= new node;
			adr->nextadd=lHandle;
			adr->value = val;
			lHandle = adr;
		}
	}
	void pop(void){
		if(!bisEmpty){
			node* adr = lHandle->nextadd;
			delete lHandle;
			lHandle=adr;
			if(lHandle == NULL) bisEmpty=true;
		}
	}
	int top(void){
		return lHandle->value;
	}

	bool isEmpty(void){
		return bisEmpty;
	}

};

int main(){
	linkedlist ll;
	vector<int> vec;
	int a=0,b=0;
	DWORD llinit=GetTickCount();
	for(int i=2;i<5000000;i++) ll.push(i);
	llinit=GetTickCount()-llinit;
	
	DWORD vecinit=GetTickCount();
	for(int i=2;i<5000000;i++) vec.push_back(i);
	vecinit=GetTickCount()-vecinit;

	DWORD llpop = GetTickCount();
	for(int i=2;i<5000000;i++){
		a=ll.top();
		ll.pop();
	}
	llpop=GetTickCount()-llpop;
	cout<<a<<endl;

	DWORD vecpop=GetTickCount();
	for(int i=2;i<5000000;i++){
		b=vec.back();
		vec.pop_back();
	}
	vecpop=GetTickCount()-vecpop;
	cout<<b<<endl;

	cout<<"Vecinit: "<< vecinit<<"  Vecpop: "<<vecpop<<endl;
	cout<<"LLinit: "<<llinit<<"  LLpop: "<<llpop<<endl;

	cin.get();
	return 0;
}

**elad** · 07-31-2006

As a learning exercise, the original post was about

"In-Place linked list reversing"

To me, this means there will be only one linked list, not two, used in the process of reversal, irrespective of how inefficient or array like the process is. So far, there have been two solutions presented, swap values in nodes and swap nodes within the same list using array like manipulations of the list. A third solution has been proposed, recursion. The schemata for that could be based on either of the prior solutions or on something like this:

Version 1:
Call the first node targetNode.
Always remove the last node of the list, setting the new last nodes pointer to NULL
Always reinsert the popped node immediately to the left of targetNode.
Stop when targetNodes pointer is NULL

OR

Version 2:
Call the last node of the list targetNode.
Always remove the first node in the list, changing value of the head node with each extraction.
Always reinsert the extracted node immediately to right of targetNode
Stop when head node == targetNode

Either of which could be implemented using either iteration or recursion, though there may be reasons to prefer one version over the other from a theoretical standpoint. From a learning standpoint, implementing both versions could be educational, or boring, depending how comfortable you are manipulating linked lists and pointers using your own code; which, IMO, was the point of the challenge in the first place.

**CornedBee** · 07-31-2006

To me, in-place linked list manipulation simply means not allocating new nodes. Under this interpretation, you can use the simple pop-push mechanism, by building a new list from the nodes of the old.

**siavoshkc** · 07-31-2006

I am going to find out what a normal linked list requires, then I will solve the reversing problem. I am waiting for the iMalc response to know his idea about my last code.

**elad** · 07-31-2006

To me, in-place linked list manipulation simply means not allocating new nodes.

Seems reasonable, too, now that you point it out. So depending how you interpret what "in-place" means, go either way.

**siavoshkc** · 08-01-2006

A bug in top() discovered. And vector replaced by stack.

Code:

#include<iostream>
#include<stack>
#include<windows.h>
using namespace std;

class linkedlist{
	struct node{
		int value;
		node* nextadd;
	};
	node* lHandle;
	bool bisEmpty;

public:
	linkedlist(){
		bisEmpty=true;	
	}

	~linkedlist(){
		if(!bisEmpty){
			while(lHandle->nextadd!=NULL){
				node* adr = lHandle->nextadd;
				delete lHandle;
				lHandle = adr;
			}
			delete lHandle;
		}
	}

	void push(int val){
		if(bisEmpty){
			lHandle= new node;
			lHandle->value=val;
			lHandle->nextadd=NULL;
			bisEmpty = false;
		}
		else{
			node* adr= new node;
			adr->nextadd=lHandle;
			adr->value = val;
			lHandle = adr;
		}
	}
	void pop(void){
		if(!bisEmpty){
			node* adr = lHandle->nextadd;
			delete lHandle;
			lHandle=adr;
			if(lHandle == NULL) bisEmpty=true;
		}
	}
	int top(void){
		if(!bisEmpty)
			return lHandle->value;
		else
			return 666;
	}

	bool isEmpty(void){
		return bisEmpty;
	}

};

int main(){
	linkedlist ll;
	stack<int> st;
	int a=0,b=0;
	DWORD llinit=GetTickCount();
	for(int i=2;i<5000000;i++) ll.push(i);
	llinit=GetTickCount()-llinit;
	
	DWORD Stackinit=GetTickCount();
	for(int i=2;i<5000000;i++) st.push(i);
	Stackinit=GetTickCount()-Stackinit;

	DWORD llpop = GetTickCount();
	for(int i=2;i<5000000;i++){
		a=ll.top();
		ll.pop();
	}
	llpop=GetTickCount()-llpop;
	cout<<a<<endl;

	DWORD Stackpop=GetTickCount();
	for(int i=2;i<5000000;i++){
		b=st.top();
		st.pop();
	}
	Stackpop=GetTickCount()-Stackpop;
	cout<<b<<endl;

	cout<<"Stackinit: "<< Stackinit<<"  Stackpop: "<<Stackpop<<endl;
	cout<<"LLinit: "<<llinit<<"  LLpop: "<<llpop<<endl;

	cin.get();
	return 0;
}

**Mario F.** · 08-01-2006

A shame that at some point during your experiments you decided to make your code non portable. All because of a single windows.h typedef

**twomers** · 08-01-2006

Why have:

Code:

struct node
{
	int value;
	node* nextadd;
};

inside the class? Wouldn't
it make more sense to put
it outside? no?

**siavoshkc** · 08-01-2006

>>A shame that at some point during your experiments you decided to make your code non portable. All because of a single windows.h typedef

Only a typedef? What about GetTickCount()? Finally it is only a speed test you can ignore main().

inside the class? Wouldn't
it make more sense to put
it outside? no?

Class has private access to nodes so struct should be in the class.

**siavoshkc** · 08-01-2006

With overloaded operators:

Code:

class linkedlist{
	struct node{
		int value;
		node* nextadd;
	};
	node* lHandle;
	bool bisEmpty;

public:
	linkedlist(){
		bisEmpty=true;	
	}

	~linkedlist(){
		if(!bisEmpty){
			while(lHandle->nextadd!=NULL){
				node* adr = lHandle->nextadd;
				delete lHandle;
				lHandle = adr;
			}
			delete lHandle;
		}
	}

	void push(int val){
		if(bisEmpty){
			lHandle= new node;
			lHandle->value=val;
			lHandle->nextadd=NULL;
			bisEmpty = false;
		}
		else{
			node* adr= new node;
			adr->nextadd=lHandle;
			adr->value = val;
			lHandle = adr;
		}
	}
	void pop(void){
		if(!bisEmpty){
			node* adr = lHandle->nextadd;
			delete lHandle;
			lHandle=adr;
			if(lHandle == NULL) bisEmpty=true;
		}
	}
	int top(void){
		if(!bisEmpty)
			return lHandle->value;
		else
			return 666;
	}

	bool isEmpty(void){
		return bisEmpty;
	}
	bool operator== ( linkedlist &righth){
		if(isEmpty() && righth.isEmpty()) return true;
		else if((isEmpty() && !righth.isEmpty()) || (!isEmpty() && righth.isEmpty())) return false;
		else{
			while(!isEmpty() && !righth.isEmpty()){
				if(top() != righth.top()) return false;
				pop();
				righth.pop();
				if(isEmpty() && righth.isEmpty()) return true;
			}
			return false;
		}
	}
	bool operator< ( linkedlist &righth){
		if(isEmpty() && righth.isEmpty()) return false;
		else if((isEmpty() && !righth.isEmpty()) ) return true;
		else if( (!isEmpty() && righth.isEmpty())) return false;
		else{
			while(1){
				if(top() > righth.top()) return false;
				else if(top() < righth.top()) return true;
				else{
					pop();
					righth.pop();
					if(isEmpty() && righth.isEmpty()) return false;
					else if(isEmpty() && !righth.isEmpty() ) return true;
					else if( !isEmpty() && righth.isEmpty()) return false;
				}
			}
			
		}
	}

	bool operator> ( linkedlist &righth){
		if(isEmpty() && righth.isEmpty()) return false;
		else if((isEmpty() && !righth.isEmpty()) ) return false;
		else if( (!isEmpty() && righth.isEmpty())) return true;
		else{
			while(1){
				if(top() > righth.top()) return true;
				else if(top() < righth.top()) return false;
				else{
					pop();
					righth.pop();
					if(isEmpty() && righth.isEmpty()) return false;
					else if(isEmpty() && !righth.isEmpty()) return false;
					else if(!isEmpty() && righth.isEmpty()) return true;
				}
			}
	
		}
	}
	bool operator>=(linkedlist &righth){
		return !(operator<(righth));
	}
	bool operator<=(linkedlist &righth){
		return !(operator>(righth));
	}
	bool operator!= ( linkedlist &righth){
		return !(operator==(righth));
	}

};

Thread: Link List

Thread Tools

Search Thread

Display

Similar Threads

Unknown memory leak with linked lists...

Link List Insert prob

reading data from a file - link list

compiler build error

singly linked list