Linked List functions

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

Join Date: Apr 2007
Posts: 84
Reputation: phalaris_trip is an unknown quantity at this point 
Solved Threads: 5
phalaris_trip's Avatar
phalaris_trip phalaris_trip is offline Offline
Junior Poster in Training

Linked List functions

 
0
  #1
Dec 28th, 2007
Just trying to get my head around linked lists and I'm trying to all the standard container functions..

For a singly-linked list are these algorithms correct?

  1. void pop_front(const T& t)
  2. {
  3. // Deallocate memory pointed to by head
  4. node<T>* tempNode = head;
  5. delete head;
  6.  
  7. // Get new head
  8. head = tempNode->next;
  9. }
  10.  
  11. void pop_back(const T& t)
  12. {
  13. // Deallocate memory pointed to by tail
  14. delete tail;
  15.  
  16. // Get new tail
  17. node<T>* currentNode = head;
  18. for (size_t i=0; i<sizet-2; i++)
  19. {
  20. currentNode = currentNode->next;
  21. }
  22. tail = currentNode;
  23. tail->next = NULL;
  24. }

Cheers!
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 15,477
Reputation: Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute 
Solved Threads: 1478
Team Colleague
Featured Poster
Ancient Dragon's Avatar
Ancient Dragon Ancient Dragon is offline Offline
Still Learning

Re: Linked List functions

 
0
  #2
Dec 28th, 2007
pop_front is wrong. First you make a copy of head then delete it. When you delete head that also invalidates the copy tempNode. What you want to do is set head then delete tempNode

What are you going to use that parameter for ?
  1. void pop_front(const T& t)
  2. {
  3. if( head != NULL)
  4. {
  5. node<T>* tempNode = head;
  6.  
  7. // Get new head
  8. head = tempNode->next;
  9. // OR just this
  10. head = head->next;
  11.  
  12. // Deallocate memory pointed to by head
  13. delete tempNode;
  14. }
  15. }
Last edited by Ancient Dragon; Dec 28th, 2007 at 12:38 am.
Don't PM me with questions -- you might get a nasty PM in response. If you have a question then post it in one of the forums.
Reply With Quote Quick reply to this message  
Join Date: Apr 2007
Posts: 84
Reputation: phalaris_trip is an unknown quantity at this point 
Solved Threads: 5
phalaris_trip's Avatar
phalaris_trip phalaris_trip is offline Offline
Junior Poster in Training

Re: Linked List functions

 
0
  #3
Dec 28th, 2007
Yeah that makes sense, cheers!

(The parameters were just a careless copy+paste job from push_front() and push_back().)

I'm still not sure about pop_back though.. "size-2" doesn't seem very elegant. I was trying to look through the std::vector header file for some inspiration but it's hard to make sense of it..
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 15,477
Reputation: Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute Ancient Dragon has a reputation beyond repute 
Solved Threads: 1478
Team Colleague
Featured Poster
Ancient Dragon's Avatar
Ancient Dragon Ancient Dragon is offline Offline
Still Learning

Re: Linked List functions

 
0
  #4
Dec 28th, 2007
you could just use a while statement
  1. void pop_back(const T& t)
  2. {
  3. // Deallocate memory pointed to by tail
  4. delete tail;
  5. tail = NULL;
  6. // Get new tail
  7. node<T>* currentNode = head;
  8. while(currentNode->next != NULL)
  9. {
  10. tail = currentNode;
  11. currentNode = currentNove->next;
  12. }
  13. if( currentNode == head)
  14. {
  15. head = tail = NULL;
  16. }
  17. }
Don't PM me with questions -- you might get a nasty PM in response. If you have a question then post it in one of the forums.
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC