Link List

This is a discussion on Link List within the C++ Programming forums, part of the General Programming Boards category; The way I created my generic, Linked List, class was w/an inner defined structure (chosen simply because it's public by ...

  1. #31
    Registered User
    Join Date
    Mar 2005
    Posts
    135
    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.

  2. #32
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote 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!

  3. #33
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,236
    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?
    Last edited by siavoshkc; 07-29-2006 at 01:19 AM.
    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

  4. #34
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote 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!
    Last edited by iMalc; 07-29-2006 at 05:34 PM.

  5. #35
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    iMalc wins the internet.

  6. #36
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,236
    Can I make another linken list to do so?
    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

  7. #37
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,848
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #38
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,236
    So I am going to build a new linked list with only 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

  9. #39
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,236
    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;
    }
    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

  10. #40
    Registered User Osaou's Avatar
    Join Date
    Nov 2004
    Location
    Stockholm, Sweden
    Posts
    69
    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. =)

  11. #41
    Registered User
    Join Date
    Mar 2005
    Posts
    135
    Quote 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

  12. #42
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    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?
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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.

  13. #43
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,236
    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;
    	}
    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

  14. #44
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,848
    You don't need a complicated count method - a simple isEmpty() test will suffice

    while ( !isEmpty(list1) ) push(list2,pop(list1));
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  15. #45
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,236
    It wont work. The list will never be empty. It will has at least one node.
    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

Page 3 of 4 FirstFirst 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Link List Insert prob
    By Bebs in forum C Programming
    Replies: 8
    Last Post: 12-03-2008, 10:28 PM
  3. reading data from a file - link list
    By peter_hii in forum C++ Programming
    Replies: 7
    Last Post: 10-25-2006, 10:11 AM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21