Checking for duplicates in a orderedered linked list

Please support our C++ advertiser: Download Intel® Parallel Studio Eval
Reply

•
•
Join Date: Oct 2004
Posts: 24
Reputation: cblue is an unknown quantity at this point 
Solved Threads: 0
cblue cblue is offline Offline
Newbie Poster

Checking for duplicates in a orderedered linked list

 
0
  #1
Jul 11th, 2005
I was wondering if anyone can give me an idea on how i can modify this function to check for duplicates, if it contains a duplicate, since duplicates are not aloowed, output a message.
Any help would greatly be appreciated.

C++ Syntax (Toggle Plain Text) 
  1. template<class Type>
  2. void orderedLinkedListType<Type>::insertNode(const Type& newItem)
  3. {
  4. 	nodeType<Type> *current; //pointer to traverse the list
  5. 	nodeType<Type> *trailCurrent; //pointer just before current
  6. 	nodeType<Type> *newNode;  //pointer to create a node
  7.  
  8. 	bool  found;
  9.  
  10. 	newNode = new nodeType<Type>; //create the node
  11.  	assert(newNode != NULL);
  12.  
  13. 	newNode->info = newItem;   //store newitem in the node
  14. 	newNode->link = NULL;      //set the link field of the node 
  15. 	                           //to NULL
  16.  
  17. 	if(first == NULL)  //Case 1	
  18. 	{	
  19. 	   first = newNode;
  20. 	   count++;
  21.  	}
  22. 	else
  23. 	{
  24. 	   current = first;
  25. 	   found = false;
  26.  
  27. 	   while(current != NULL && !found) //search the list
  28. 			if(current->info >= newItem)
  29. 				found = true;
  30.      		else
  31. 			{
  32. 				trailCurrent = current;
  33. 				current = current->link;
  34. 			}
  35.  
  36. 	   if(current == first)  	//Case 2
  37. 	   {
  38. 			newNode->link = first;
  39. 			first = newNode;
  40.  			count++;
  41. 	   }
  42. 	   else				//Case 3
  43. 	   {
  44. 			trailCurrent->link = newNode;
  45. 			newNode->link = current;
  46.  			count++;
  47. 	   }
  48. 	}//end else
  49. }//end insertNode
<< moderator edit: added [code][/code] tags >>
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2004
Posts: 8,132
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 800
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Checking for duplicates in a orderedered linked list

 
0
  #2
Jul 11th, 2005
It's an ordered list, so all you need to do is break off the search when the node's value is not less than the new item. To test for a duplicate, check and see if the next node has the same value as the new item:
C++ Syntax (Toggle Plain Text) 
  1. // Empty list case
  2. if ( first == NULL )
  3.   first = newNode;
  4.  
  5. // First node case
  6. if ( newItem->info < first->info ) {
  7.   newNode->next = first;
  8.   first = newNode;
  9. }
  10.  
  11. // Find an insertion point
  12. while ( current->next != NULL && current->next->info < newItem )
  13.   current = current->next;
  14.  
  15. // Check for a duplicate
  16. if ( current->next->info == newItem )
  17.   return DUPLICATE;
  18. else {
  19.   newNode->next = current->next;
  20.   current->next = newItem;
  21. }
In case you were wondering, yes, I do hate you.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2004
Posts: 24
Reputation: cblue is an unknown quantity at this point 
Solved Threads: 0
cblue cblue is offline Offline
Newbie Poster

Re: Checking for duplicates in a orderedered linked list

 
0
  #3
Jul 12th, 2005
since this is an ordered list and it is searching where to place the new item in the list so it is in order, do i need another while loop to check for the duplicates, i know you need to go through the whole list and compare each item by moving another pointer along, i'm just not sure where in the insertNode where to code it. it uses the linkedlist.h file which i'll sent as well. I appreciate your help, thanks one again.

C++ Syntax (Toggle Plain Text) 
  1. #ifndef H_orderedLinkedListType
  2. #define H_orderedLinkedListType
  3.  
  4. #include <iostream>
  5. #include <cassert>
  6.  
  7. #include "linkedList.h"
  8.  
  9. using namespace std;
  10.  
  11. template<class Type>
  12. class orderedLinkedListType: public linkedListType<Type>
  13. {
  14. public:
  15.    bool search(const Type& searchItem);
  16.      //Function to determine whether searchItem is in the list.
  17.      //Postcondition: Returns true if searchItem is found in
  18.      //               the list; otherwise, it returns false
  19.  
  20.    void insertNode(const Type& newItem);
  21.      //Function to insert newItem in the list.
  22.      //Postcondition: first points to the new list and newItem is 
  23.      //               inserted at the proper place in the list.
  24.  
  25.    void deleteNode(const Type& deleteItem);
  26.      //Function to delete deleteItem from the list.
  27.      //Postcondition: If found, the node containing deleteItem
  28.      //               is deleted from the list; first points 
  29.      //               to the first node of the new list.
  30.      //               If deleteItem is not in the list, an 
  31.      //               appropriate message is printed.
  32. };
  33.  
  34.  
  35.  
  36. template<class Type>
  37. bool orderedLinkedListType<Type>::search(const Type& searchItem)
  38. {
  39.     bool found;
  40.     nodeType<Type> *current; //pointer to traverse the list
  41.  
  42.     found = false;    //initialize found to false
  43.     current = first;  //start the search at the first node
  44.  
  45.     while(current != NULL && !found)
  46.        if(current->info >= searchItem)
  47.           found = true;
  48.        else
  49.           current = current->link;
  50.  
  51.       if(found)       
  52.          found = (current->info == searchItem); //test for equality
  53.  
  54.     return found;
  55. }//end search
  56.  
  57.  
  58. template<class Type>
  59. void orderedLinkedListType<Type>::insertNode(const Type& newItem)
  60. {
  61. 	nodeType<Type> *current; //pointer to traverse the list
  62. 	nodeType<Type> *trailCurrent; //pointer just before current
  63. 	nodeType<Type> *newNode;  //pointer to create a node
  64.  
  65. 	bool  found;
  66.  
  67. 	newNode = new nodeType<Type>; //create the node
  68.  	assert(newNode != NULL);
  69.  
  70. 	newNode->info = newItem;   //store newitem in the node
  71. 	newNode->link = NULL;      //set the link field of the node 
  72. 	                           //to NULL
  73.  
  74. 	if(first == NULL)  //Case 1	
  75. 	{	
  76. 	   first = newNode;
  77. 	   count++;
  78.  	}	
  79. 	if(newItem < first->info)
  80. 	{
  81. 		newNode->link = first;
  82. 		first = newNode;
  83. 	}
  84. 	else
  85. 	{
  86. 	   current = first;
  87. 	   found = false;
  88.  
  89. 	   while(current != NULL && !found && current->link->info < newItem) //search the list
  90. 		   current = current->link;
  91.  
  92. 		   if(current->info >= newItem)
  93. 				found = true;
  94.      	   else
  95. 		   {
  96. 			   trailCurrent = current;
  97. 			   current = current->link;
  98. 		   }
  99. 		   if(newNode->link == current->link)
  100. 			   cout << "No Duplicates Allowed"<<endl;
  101. 		   else
  102. 		   {
  103. 			   newNode = current->link;
  104. 			   current->info = newItem;
  105. 		   }
  106. 	   if(current == first)  	//Case 2
  107. 	   {
  108. 			newNode->link = first;
  109. 			first = newNode;
  110.  			count++;
  111. 	   }
  112. 	   else				//Case 3
  113. 	   {
  114. 			trailCurrent->link = newNode;
  115. 			newNode->link = current;
  116.  			count++;
  117. 	   }
  118. 	}//end else
  119. }//end insertNode
  120.  
  121. template<class Type>
  122. void orderedLinkedListType<Type>::deleteNode
  123.                                     (const Type& deleteItem)
  124. {
  125. 	nodeType<Type> *current; //pointer to traverse the list
  126. 	nodeType<Type> *trailCurrent; //pointer just before current
  127. 	bool found;
  128.  
  129. 	if(first == NULL) //Case 1
  130. 		cerr<<"Cannot delete from an empty list."<<endl;
  131. 	else
  132. 	{
  133. 		current = first;
  134. 		found = false;
  135.  
  136. 		while(current != NULL && !found)  //search the list
  137. 			if(current->info >= deleteItem)
  138. 				found = true;
  139. 			else
  140. 			{
  141. 				trailCurrent = current;
  142. 				current = current->link;
  143. 			}
  144.  
  145. 		if(current == NULL)   //Case 4
  146. 			cout<<"The item to be deleted is not in the list."
  147. 			    <<endl;
  148. 		else
  149.  			if(current->info == deleteItem) //item to be deleted  
  150. 											//is in the list
  151. 			{
  152.   				if(first == current) 		//Case 2
  153. 				{
  154. 					first = first->link;
  155.  
  156. 					delete current;
  157. 				}
  158. 				else     				//Case 3
  159. 				{
  160. 					trailCurrent->link = current->link;
  161. 					delete current;
  162. 				}
  163.  				count--;
  164. 			}
  165. 			else  					//Case 4
  166. 				cout<<"The item to be deleted is not in the list."
  167. 				    <<endl;
  168. 	}
  169. } //end deleteNode
  170.  
  171. #endif

C++ Syntax (Toggle Plain Text) 
  1. #ifndef H_LinkedListType
  2. #define H_LinkedListType
  3.  
  4. #include <iostream>
  5. #include <cassert>
  6. using namespace std;
  7.  
  8. template <class Type>
  9. struct nodeType
  10. {
  11. 	Type info;
  12. 	nodeType<Type> *link;
  13. };
  14.  
  15. template<class Type>
  16. class linkedListType
  17. {
  18. 	template<class Type>
  19. 	friend ostream& operator<<(ostream&, const linkedListType<Type>&);
  20.  
  21. public:
  22.     const linkedListType<Type>& operator=
  23.           			      (const linkedListType<Type>&); 
  24. 		//Overload the assignment operator.
  25.     void initializeList(); 
  26.  		//Initializes the list to an empty state.
  27. 	    //Postcondition: first = NULL, last = NULL,
  28. 		//                count = 0
  29.     bool isEmptyList();
  30.  		//Function to determine whether the list is empty. 
  31. 		//Postcondition: Returns true if the list is empty;
  32. 		//               otherwise, returns false.
  33.  
  34. 	int length();
  35. 		//Function to return the number of nodes in the 
  36. 		//list.
  37. 		//Postcondition: The value of count is returned.
  38.     void destroyList();
  39.  		//Function to delete all the nodes from the list.
  40.   		//Postcondition: first = NULL, last = NULL, 
  41. 		//               count = 0
  42.     Type front(); 
  43.  		//Function to return the first element of the list.
  44.  		//Precondition: The list must exist and must not be
  45. 		//empty.
  46.   		//Postcondition: If the list is empty, then the 
  47.  		//               program terminates; otherwise, 
  48. 	    //               the first element of the list is 
  49. 		//               returned.
  50.     Type back(); 
  51.        //Function to return the last element of the
  52.        //list.
  53. 		//Precondition: The list must exist and must not
  54. 		//be empty.
  55. 		//Postcondition: If the list is empty, then the 
  56. 		//               program terminates; otherwise,
  57. 		//               the last element of the list is 
  58. 		//               returned.
  59.  
  60.    bool search(const Type& searchItem);
  61. 		//Function to determine whether searchItem is in 
  62. 		//the list.
  63. 		//Postcondition: Returns true if searchItem is found
  64. 		//               in the list; otherwise, it returns
  65. 		//               false.
  66.  
  67.     void insertFirst(const Type& newItem);
  68. 		//Function to insert newItem in the list.
  69. 		//Postcondition: first points to the new list 
  70. 		//                and newItem is inserted at the
  71. 		//                beginning of the list.
  72.  
  73.     void insertLast(const Type& newItem);
  74. 		//Function to return newItem at the end of the
  75. 		//list.
  76. 	    //Postcondition: first points to the new list, 
  77. 		//                newItem is inserted at the end
  78. 		//                of the list, and last points to
  79. 		//                the last node in the list.
  80.  
  81.     void deleteNode(const Type& deleteItem);
  82.   		//Function to delete deleteItem from the list.
  83.  		//Postcondition: If found, the node containing 
  84.    		//               deleteItem is deleted from the 
  85. 		//                list, first points to the first
  86. 		//                node, and last points to the last 
  87. 		//                node of the updated list. 
  88.  
  89.     linkedListType(); 
  90.    		//default constructor
  91.  		//Initializes the list to an empty state.
  92.  		//Postcondition: first = NULL, last = NULL, 
  93. 		//               count = 0 
  94.  
  95.     linkedListType(const linkedListType<Type>& otherList); 
  96.          //copy constructor
  97.  
  98.     ~linkedListType();   
  99.     	//destructor
  100.    		//Deletes all the nodes from the list.
  101.     	//Postcondition: The list object is destroyed. 
  102.  
  103. protected:
  104.     int count;		//variable to store the number of 
  105.  					//elements in the list
  106.     nodeType<Type> *first; //pointer to the first node of 
  107.                            //the list
  108.     nodeType<Type> *last;  //pointer to the last node of 
  109.                            //the list 
  110. private:
  111.     void copyList(const linkedListType<Type>& otherList); 
  112. 		//Function to make a copy of otherList.
  113. 		//Postcondition: A copy of otherList is created 
  114. 		//               and assigned to this list.
  115. };
  116.  
  117. template<class Type>
  118. bool linkedListType<Type>::isEmptyList()
  119. {
  120. 	return(first == NULL);
  121. }
  122.  
  123. template<class Type>
  124. linkedListType<Type>::linkedListType() // default constructor
  125. {
  126. 	first = NULL;
  127. 	last = NULL;
  128. 	count = 0;
  129. }
  130.  
  131. template<class Type>
  132. void linkedListType<Type>::destroyList()
  133. {
  134. 	nodeType<Type> *temp;   //pointer to deallocate the memory 
  135. 							//occupied by the node
  136. 	while(first != NULL)    //while there are nodes in the list
  137. 	{
  138. 	   temp = first;        //set temp to the current node
  139. 	   first = first->link; //advance first to the next node
  140. 	   delete temp;         //deallocate memory occupied by temp
  141. 	}
  142.  
  143. 	last = NULL;	//initialize last to NULL; first has already
  144.                    //been set to NULL by the while loop
  145.  	count = 0;
  146. }
  147.  
  148.  
  149. template<class Type>
  150. void linkedListType<Type>::initializeList()
  151. {
  152. 	destroyList(); //if the list has any nodes, delete them
  153. }
  154.  
  155. template<class Type>
  156. int linkedListType<Type>::length()
  157. {
  158.  	return count;
  159. }  // end length
  160.  
  161. template<class Type>
  162. Type linkedListType<Type>::front()
  163. {   
  164.     assert(first != NULL);
  165.    	return first->info; //return the info of the first node	
  166. }//end front
  167.  
  168.  
  169. template<class Type>
  170. Type linkedListType<Type>::back()
  171. {   
  172. 	 assert(last != NULL);
  173.    	 return last->info; //return the info of the first node	
  174. }//end back
  175.  
  176. template<class Type>
  177. bool linkedListType<Type>::search(const Type& searchItem)
  178. {
  179.     nodeType<Type> *current; //pointer to traverse the list
  180.     bool found;
  181.  
  182.     current = first; //set current to point to the 
  183.                      //first node in the list
  184.     found = false;   //set found to false
  185.  
  186.     while(current != NULL && !found)		//search the list
  187.         if(current->info == searchItem)     //the item is found
  188.            found = true;
  189.         else
  190.            current = current->link; //make current point 
  191.                                     //to the next node
  192.  
  193.      return found;
  194. }//end search
  195.  
  196. template<class Type>
  197. void linkedListType<Type>::insertFirst(const Type& newItem)
  198. {
  199. 	nodeType<Type> *newNode; //pointer to create the new node
  200.  
  201. 	newNode = new nodeType<Type>; //create the new node
  202.  
  203. 	assert(newNode != NULL);	//If unable to allocate memory, 
  204.  								//terminate the program
  205.  
  206. 	newNode->info = newItem; 	   //store the new item in the node
  207. 	newNode->link = first;        //insert newNode before first
  208. 	first = newNode;              //make first point to the 
  209.                                  //actual first node
  210. 	count++; 			   //increment count
  211.  
  212. 	if(last == NULL)   //if the list was empty, newNode is also 
  213.                       //the last node in the list
  214. 		last = newNode;
  215. }
  216.  
  217. template<class Type>
  218. void linkedListType<Type>::insertLast(const Type& newItem)
  219. {
  220. 	nodeType<Type> *newNode; //pointer to create the new node
  221.  
  222. 	newNode = new nodeType<Type>; //create the new node
  223.  
  224. 	assert(newNode != NULL);	//If unable to allocate memory, 
  225.  							    //terminate the program
  226.  
  227. 	newNode->info = newItem;      //store the new item in the node
  228. 	newNode->link = NULL;         //set the link field of newNode
  229.          						//to NULL
  230.  
  231. 	if(first == NULL)	//if the list is empty, newNode is 
  232.      					//both the first and last node
  233. 	{
  234. 		first = newNode;
  235. 		last = newNode;
  236. 		count++;		//increment count
  237. 	}
  238. 	else			//the list is not empty, insert newNode after last
  239. 	{
  240. 		last->link = newNode; //insert newNode after last
  241. 		last = newNode;   //make last point to the actual last node
  242. 		count++;		//increment count
  243. 	}
  244. }//end insertLast
  245.  
  246. template<class Type>
  247. void linkedListType<Type>::deleteNode(const Type& deleteItem)
  248. {
  249. 	nodeType<Type> *current; //pointer to traverse the list
  250. 	nodeType<Type> *trailCurrent; //pointer just before current
  251. 	bool found;
  252.  
  253. 	if(first == NULL)    //Case 1; list is empty. 
  254. 		cerr<<"Can not delete from an empty list.\n";
  255. 	else
  256. 	{
  257. 		if(first->info == deleteItem) //Case 2 
  258. 		{
  259. 			current = first;
  260. 			first = first->link;
  261. 			count--;
  262. 			if(first == NULL)    //list has only one node
  263. 				last = NULL;
  264. 			delete current;
  265. 		}
  266. 		else  //search the list for the node with the given info
  267. 		{
  268. 			found = false;
  269. 			trailCurrent = first;   //set trailCurrent to point to
  270.                                  //the first node
  271. 			current = first->link;  //set current to point to the 
  272.     			   //second node
  273.  
  274. 			while(current != NULL && !found)
  275. 			{
  276.   				if(current->info != deleteItem) 
  277. 				{
  278. 					trailCurrent = current;
  279. 					current = current->link;
  280. 				}
  281. 				else
  282. 					found = true;
  283. 			} // end while
  284.  
  285. 			if(found) //Case 3; if found, delete the node
  286. 			{
  287. 				trailCurrent->link = current->link;
  288. 				count--;
  289.  
  290. 				if(last == current)      //node to be deleted was 
  291.                                      //the last node
  292. 					last = trailCurrent;  //update the value of last
  293.  
  294. 				delete current;  //delete the node from the list
  295. 			}
  296. 			else
  297. 				cout<<"Item to be deleted is not in the list."<<endl;
  298. 		} //end else
  299. 	} //end else
  300. } //end deleteNode
  301.  
  302.  
  303. 	//Overloading the stream insertion operator
  304. template<class Type>
  305. ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
  306. {
  307. 	nodeType<Type> *current; //pointer to traverse the list
  308.  
  309. 	current = list.first;   //set current so that it points to 
  310. 					   //the first node
  311. 	while(current != NULL) //while more data to print
  312. 	{
  313. 	   osObject<<current->info<<" ";
  314. 	   current = current->link;
  315. 	}
  316.  
  317. 	return osObject;
  318. }
  319.  
  320. template<class Type>
  321. linkedListType<Type>::~linkedListType() // destructor
  322. {
  323. 	destroyList(); 
  324. }//end destructor
  325.  
  326.  
  327. template<class Type>
  328. void linkedListType<Type>::copyList
  329.             	      (const linkedListType<Type>& otherList) 
  330. {
  331.    nodeType<Type> *newNode; //pointer to create a node
  332.    nodeType<Type> *current; //pointer to traverse the list
  333.  
  334.    if(first != NULL)	//if the list is nonempty, make it empty
  335. 	  destroyList();
  336.  
  337.    if(otherList.first == NULL) //otherList is empty
  338.    {
  339. 		first = NULL;
  340. 		last = NULL;
  341.  		count = 0;
  342.    }
  343.    else
  344.    {
  345. 		current = otherList.first;  //current points to the 
  346. 									//list to be copied
  347. 		count = otherList.count;
  348.  
  349. 			//copy the first node
  350. 		first = new nodeType<Type>;  //create the node
  351.  
  352.  		assert(first != NULL);
  353.  
  354. 		first->info = current->info; //copy the info
  355. 		first->link = NULL;  	     //set the link field of 
  356. 									 //the node to NULL
  357. 		last = first;    		     //make last point to the 
  358.             						 //first node
  359. 		current = current->link;     //make current point to  
  360.            							 //the next node
  361.  
  362. 			//copy the remaining list
  363. 		while(current != NULL)
  364. 		{
  365. 			newNode = new nodeType<Type>;  //create a node
  366.  
  367. 			assert(newNode!= NULL);
  368.  
  369. 			newNode->info = current->info;	//copy the info
  370. 			newNode->link = NULL;   	    //set the link of 
  371.                                         //newNode to NULL
  372. 			last->link = newNode; 		//attach newNode after last
  373. 			last = newNode;   			//make last point to
  374. 										//the actual last node
  375. 			current = current->link;	//make current point to
  376.        									//the next node
  377. 		}//end while
  378. 	}//end else
  379. }//end copyList
  380.  
  381.  
  382. 	//copy constructor
  383. template<class Type>
  384. linkedListType<Type>::linkedListType
  385.             	      (const linkedListType<Type>& otherList) 
  386. {
  387. 	first = NULL;
  388.  
  389. 	copyList(otherList);
  390.  
  391. }//end copy constructor
  392.  
  393. 	//overload the assignment operator
  394. template<class Type>
  395. const linkedListType<Type>& linkedListType<Type>::operator=
  396.    	 	 		(const linkedListType<Type>& otherList)
  397. { 
  398. 	if(this != &otherList) //avoid self-copy
  399. 		copyList(otherList);
  400.  
  401. 	return *this; 
  402. }
  403.  
  404. #endif
<< moderator edit: fixed [code][/code] tags >>


•
•
•
•
Originally Posted by Narue
It's an ordered list, so all you need to do is break off the search when the node's value is not less than the new item. To test for a duplicate, check and see if the next node has the same value as the new item:
C++ Syntax (Toggle Plain Text) 
  1. // Empty list case
  2. if ( first == NULL )
  3.   first = newNode;
  4.  
  5. // First node case
  6. if ( newItem->info < first->info ) {
  7.   newNode->next = first;
  8.   first = newNode;
  9. }
  10.  
  11. // Find an insertion point
  12. while ( current->next != NULL && current->next->info < newItem )
  13.   current = current->next;
  14.  
  15. // Check for a duplicate
  16. if ( current->next->info == newItem )
  17.   return DUPLICATE;
  18. else {
  19.   newNode->next = current->next;
  20.   current->next = newItem;
  21. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2004
Posts: 8,132
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 800
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Checking for duplicates in a orderedered linked list

 
0
  #4
Jul 12th, 2005
>do i need another while loop to check for the duplicates
Why would you need to? Since presumably the list is already in order, you stop searching for an insertion point at the same place that there would be a duplicate. The code I gave you is the complete algorithm to do this (insert into an ordered list without duplicates), all you need to do is incorporate it into your code.
In case you were wondering, yes, I do hate you.
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2005
Posts: 2
Reputation: deadsea is an unknown quantity at this point 
Solved Threads: 0
deadsea deadsea is offline Offline
Newbie Poster

Re: Checking for duplicates in a orderedered linked list

 
0
  #5
Aug 4th, 2005
If you need to ensure uniqueness then a linked list is not an appropriate data structure. Inserting into a linked list is expected to be a constant time O(1) operation. Checking for duplicates during the insert is going to change that.

You might want to consider a LinkedHashMap. It is basically a LinkedList in which all the Nodes are also kept in a hash. The expected insert time is still constant and duplicate entries can be checked for upon insertion in the hash.

I initially thought you were asking how to check for duplicate node pointers in a linked list , but it appears that you really want to avoid inserting duplicate objects. Please correct me if I am wrong.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2005
Posts: 2,076
Reputation: Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice 
Solved Threads: 141
Team Colleague
Rashakil Fol's Avatar
Rashakil Fol Rashakil Fol is offline Offline
Banned

Re: Checking for duplicates in a orderedered linked list

 
0
  #6
Aug 4th, 2005
Here's one example where a linked list is the appropriate structure for this: hashing, with linked lists used to handle collisions. Or any other situation where the linked list is short.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2004
Posts: 8,132
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 800
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Checking for duplicates in a orderedered linked list

 
0
  #7
Aug 4th, 2005
>If you need to ensure uniqueness then a linked list is not an appropriate data structure.
How do you know? The OP never mentioned how this list is going to be used, so it could very well be an appropriate data structure.

>Inserting into a linked list is expected to be a constant time O(1) operation.
Only if you make certain assumptions, like that the insertion will only be at the head of the list, or at the tail and then only if there is a tail pointer. The average expected time complexity for inserting into a linked list in the general case is O(N/2).

>You might want to consider a LinkedHashMap.
This is not Java. In C++, he would have to implement the functionality of a LinkedHashMap.
In case you were wondering, yes, I do hate you.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2005
Posts: 2,076
Reputation: Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice 
Solved Threads: 141
Team Colleague
Rashakil Fol's Avatar
Rashakil Fol Rashakil Fol is offline Offline
Banned

Re: Checking for duplicates in a orderedered linked list

 
0
  #8
Aug 4th, 2005
•
•
•
•
Originally Posted by Narue
>Inserting into a linked list is expected to be a constant time O(1) operation.
Only if you make certain assumptions, like that the insertion will only be at the head of the list, or at the tail and then only if there is a tail pointer. The average expected time complexity for inserting into a linked list in the general case is O(N/2).
And the worst case time complexity is O(N/100000000).

Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2004
Posts: 8,132
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 800
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Checking for duplicates in a orderedered linked list

 
0
  #9
Aug 4th, 2005
•
•
•
•
Originally Posted by Rashakil Fol
And the worst case time complexity is O(N/100000000).

There are times when I can't tell if you're joking or not.
In case you were wondering, yes, I do hate you.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum


Views: 4075 | Replies: 8
Thread Tools Search this Thread



Tag cloud for C++
6 api array arrays assignment beginner binary borland c++ c/c++ calculator char class classes code compile compiler console constructor conversion convert count data delete desktop dll encryption error file forms fstream function functions game givemetehcodez graph homework http iamthwee ifstream input int java lazy link linker list loop looping loops map math matrix memory newbie news number objects output pointer pointers problem program programming project python qt random read recursion recursive reference return search sort sorting spoonfeeding string strings struct student studio system template templates text tree url variable vc++ vector video visual visualstudio win32 window windows winsock wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2010 DaniWeb® LLC