Connecting Tech Pros Worldwide Forums | Help | Site Map
bytes > topic > c > answers

Linked List Program error

Member
  
Join Date: Feb 2008
Posts: 33
#1: Feb 14 '08
I know what I'm posting here is wired, but it's been 3 days I'm workin g on these codes, but I have no result

I post the code here

I dont wanne bother you, but if any one of you have time to read my program I appriciate it.

the program suppose to print a message on the screen
Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. template <typename T>
  6. class Node {
  7. public:
  8.     Node(T newData);
  9.     template <typename T>
  10.     friend class LinkedList;
  11.     template <typename T>
  12.     friend class Iterator;
  13. private:
  14.     T data;
  15.     Node* prev;   //Pointer to previous node in list.
  16.     Node* next;   //Pointer to next node in list.
  17. };
  18.  
  19. template <typename T>
  20. class Iterator {
  21. public:
  22.     Iterator();
  23.     T get() const;
  24.     void forward();
  25.     void backward();
  26.     template <typename T>
  27.     friend class LinkedList;
  28. private:
  29.     Node<T>* position;
  30. };
  31.  
  32. template <typename T>
  33. class LinkedList {
  34. public:
  35.     LinkedList();
  36.     LinkedList(int numNodes, T defaultValue);
  37.     LinkedList(const LinkedList<T>& right);
  38.     ~LinkedList();
  39.     LinkedList<T>& operator= (const LinkedList<T>& right);
  40.     LinkedList<T> operator+ (const LinkedList<T>& right); //operator+, concatenates two linked lists
  41.     Iterator<T> begin() const;
  42.     Iterator<T> end() const;
  43.     void insert(Iterator<T> iter, T value);
  44.     void erase(Iterator<T>& iter);
  45.     T& operator[] (int index);
  46.     T operator[] (int index) const;
  47.     int size() const;
  48.  
  49.     void find(T value);
  50.     void pop_back();
  51.     void pop_front();
  52.     void push_front(T value);
  53.     void print();
  54.     void reverse();
  55.  
  56. private:
  57.     Node<T>* first;  //Pointer to first node in list.
  58.     Node<T>* last;   //Pointer to last node in list.
  59. };
  60.  
  61. template <typename T>
  62. Node<T>::Node(T newData) {
  63.     data = newData;
  64.     prev = NULL;
  65.     next = NULL;
  66. }
  67.  
  68. template <typename T>
  69. Iterator<T>::Iterator() {
  70.     position = NULL;
  71. }
  72.  
  73. template <typename T>
  74. T Iterator<T>::get() const {
  75.     return position->data;
  76. }
  77.  
  78. template <typename T>
  79. void Iterator<T>::forward() {
  80.     position = position->next;
  81. }
  82.  
  83. //moves position backward one node
  84. template <typename T>
  85. void Iterator<T>::backward() {
  86.     position = position->prev;
  87. }
  88.  
  89.  
  90.  
  91. //Linked LIst constructor
  92. template <typename T>
  93. LinkedList<T>::LinkedList() {
  94.     first = NULL;
  95.     last = NULL;
  96. }
  97.  
  98.  
  99. template <typename T>
  100. LinkedList<T>::LinkedList(int numNodes, T defaultValue) {
  101.     first=NULL;   last=NULL;  
  102.     for (int i=1; i<=numNodes; i++)
  103.         insert(begin(),defaultValue);
  104. }
  105.  
  106. template <typename T>
  107. LinkedList<T>::LinkedList(const LinkedList<T>& right) {
  108.     first = NULL;  
  109.     last = NULL;
  110.     Iterator<T> iter_right = right.end();
  111.     while (iter_right.position != NULL) {
  112.         insert(begin(), iter_right.get());
  113.         iter_right.backward();
  114.     }
  115. }
  116.  
  117. //Linked list Destructor
  118. template <typename T>
  119. LinkedList<T>::~LinkedList() {
  120.     while (first != NULL) 
  121.         erase(begin());
  122. }
  123.  
  124. //Assignment Operator
  125. template <typename T>
  126. LinkedList<T>& LinkedList<T>::operator= (const LinkedList<T>& right) {
  127.     if (this != &right) {
  128.         Iterator<T> iter_left = begin();
  129.         while (iter_left.position != NULL) {
  130.             erase(iter_left);
  131.             iter_left = begin();
  132.         }
  133.         Iterator<T> iter_right = right.end();
  134.         while (iter_right.position != NULL) {
  135.             insert(begin(), iter_right.get());
  136.             iter_right.backward();
  137.         }
  138.     }
  139.     return *this;
  140. }
  141.  
  142.  
  143.  
  144. //Operator + , concatenates two linked lists
  145. template <typename T>
  146. LinkedList<T> LinkedList<T>::operator+ (const LinkedList<T>& right)
  147. {
  148. LinkedList result(*this);
  149. for (int i=0 ; i<right.size() ; i++)
  150. result.push_back(right[i]);
  151. return result;
  152. }
  153.  
  154. template <typename T>
  155. Iterator<T> LinkedList<T>::begin() const {
  156.     Iterator<T> iter;
  157.     iter.position = first;
  158.     return iter;
  159. }
  160.  
  161. //To  initialize the iteratore, this function set iterator at end
  162. template <typename T>
  163. Iterator<T> LinkedList<T>::end() const {
  164.     Iterator<T> iter;
  165.     iter.position = last;
  166.     return iter;
  167. }
  168.  
  169. //Accessors, lookuo how many nodes we have in the current list
  170. template <typename T>
  171. int LinkedList<T>::size() const {
  172.     Iterator<T> iter = begin();
  173.     int length = 0;
  174.     while (iter.position != NULL) {
  175.         iter.forward();
  176.         length++;
  177.     }
  178.     return length;
  179. }
  180.  
  181. //erasing a node
  182. template <typename T>
  183. void LinkedList<T>::erase(Iterator<T>& iter) {
  184.     Node<T>* pos = iter.position;
  185.     iter.forward();
  186.     //Set pointer from node before.
  187.     if (pos == first)  //Check if first node.
  188.         first = pos->next;
  189.     else
  190.         (pos->prev)->next = pos->next;
  191.     //Set pointer from node after.
  192.     if (pos == last)   //Check if last node.
  193.         last = pos->prev;
  194.     else 
  195.         (pos->next)->prev = pos->prev;
  196.     delete pos;  //Remove the node from memory.
  197.     return;
  198. }
  199.  
  200. template <typename T> 
  201. void LinkedList<T>::insert(Iterator<T> iter, T value) {
  202.     Node<T>* pos = iter.position;
  203.     Node<T>* newNode = new Node<T>(value);
  204.     //Check if list is empty.
  205.     if (first == NULL) {
  206.         first = newNode;
  207.         last = newNode;
  208.         return;
  209.     }
  210.     newNode->prev = pos->prev;
  211.     newNode->next = pos;
  212.     if (newNode->prev == NULL)  //Check if inserting at first position.
  213.         first = newNode;
  214.     else
  215.         (newNode->prev)->next = newNode;
  216.     pos->prev = newNode;
  217.     return;
  218. }
  219.  
  220. template <typename T>
  221. void LinkedList<T>::pop_back()
  222. {
  223.     if(last==first)
  224.     {
  225.         delete first;
  226.         first=last=NULL;
  227.     }
  228.     else
  229.     {
  230.         last=last->prev;
  231.         delete last->next;
  232.         last->next=NULL;
  233.         }
  234.     last = NULL;
  235. }
  236.  
  237. //pop front function, remove the first element from the list
  238. template <typename T>
  239. void LinkedList<T>::pop_front()
  240. {
  241.     if(first==last)
  242.     {
  243.             delete first;
  244.             last=first=NULL;
  245.     }
  246.     else
  247.     {
  248.         first=first->next;
  249.         delete first->prev;
  250.         first->prev=NULL;
  251.     }
  252.  
  253. }
  254.  
  255.  
  256. //push back, adds the given value x to the end of the list
  257. template<typename T>
  258. void LinkedList<T>::push_back(T value)
  259. {
  260.  
  261.     Node<T>* newNode = new Node<T>(value);
  262.     newNode->prev=NULL;
  263.     newNode->next=NULL;
  264.  
  265.     if(first==NULL && last==NULL)
  266.     {
  267.         first=last=newNode;
  268.     }
  269.  
  270.     else
  271.     {
  272.         newNode->prev=last;
  273.         last->next=newNode;
  274.         last=newNode;
  275.     }
  276.  
  277.  
  278. }
  279. //find function
  280. template<typename T>
  281. void LinkedList<T>::find(T value)
  282. {
  283.     Node<T>* pos=first;
  284.     while(pos){
  285.         if (pos.get()==value){
  286.             return pos;
  287.         }
  288.         else{
  289.             pos=pos->next;
  290.         }
  291.     }
  292. return pos=NULL;
  293.  
  294. }
  295.  
  296. template<typename T>
  297. void LinkedList<T>::push_front(T value)
  298. {
  299.     Node<T>* newNode= new Node<T>(value);
  300.     newNode->prev=NULL;
  301.     newNode->next=NULL;
  302.  
  303.     if(first==NULL && last==NULL)
  304.     {
  305.         first=last=newNode;
  306.     }
  307.  
  308.     else
  309.     {
  310.         newNode->next=first;
  311.         first->prev=newNode;
  312.         first=newNode;
  313.  
  314.     }
  315. }
  316.  
  317. //print all the value of the list
  318. template<typename T>
  319. void LinkedList<T>::print()
  320. {
  321.     T value;
  322.     Node<T>* newNode=new Node<T>(value);
  323.         newNode = first;
  324.         while (newNode != NULL) {
  325.             cout<<newNode->data<<" ";
  326.             newNode = newNode->next;
  327.         }
  328.         cout<<endl;
  329.  
  330. }
  331.  
  332. template<typename T>
  333. void LinkedList<T>::reverse()
  334. {
  335.  
  336.  
  337.     Node<T>* i=first;
  338.     Node<T>* temp;
  339.  
  340.  
  341.     while(i){
  342.         temp=i->next;
  343.         i->next=i->prev;
  344.         i->prev=temp;
  345.         i=temp;
  346.     }
  347.  
  348. temp=last;
  349. first=last;
  350. last=temp;
  351.  
  352. }
  353.  
  354. template <typename T>
  355. T& LinkedList<T>::operator[] (int index) {
  356.     Node<T>* pos = first;
  357.     for (int i=1; i<= index; i++)
  358.         pos = pos->next;
  359.     return pos->data;
  360. }
  361.  
  362. //Accessor, look up elements in the list, for example cout<<myList[3]
  363. template <typename T>
  364. T LinkedList<T>::operator[] (int index) const {
  365.     Node<T>* pos = first;
  366.     for (int i=1; i<= index; i++)
  367.         pos = pos->next;
  368.     return pos->data;
  369. }
  370.  
  371. int main() {
  372.     LinkedList<string> rebelList1(4," ");
  373.     Iterator<string> iter1 = rebelList1.end();
  374.     iter1.backward();
  375.     rebelList1.erase(iter1);
  376.     iter1.backward();
  377.     rebelList1.insert(iter1,"Co");
  378.     iter1.forward();
  379.     rebelList1.insert(iter1,"it");
  380.     rebelList1.insert(iter1, rebelList1[2]);
  381.     rebelList1[0] = "ldth\nha";
  382.     rebelList1.pop_back();
  383.     rebelList1.push_back("all");
  384.     rebelList1.push_front("oth\nb");
  385.  
  386.     LinkedList<string> rebelList2;
  387.     rebelList2.push_back("Tatooine");
  388.     rebelList2.push_front("Lando");
  389.     rebelList2.push_back(" sh");
  390.     rebelList2.pop_front();
  391.     rebelList2.pop_front();
  392.     rebelList2.push_front("hey");
  393.     rebelList2.reverse();
  394.     Iterator<string> iter2 = rebelList2.find(" sh");
  395.     rebelList2.insert(iter2,"ou");
  396.     rebelList2.reverse();
  397.     iter2 = rebelList2.find("hey");
  398.     rebelList2.insert(iter2,"oth\nb");
  399.     iter2.backward();
  400.     rebelList2.insert(iter2,"n H");
  401.     rebelList2.reverse();
  402.     rebelList2.insert(iter2,"ut t");
  403.     rebelList2.push_front("ld c");
  404.  
  405.     LinkedList<string> rebelList3;
  406.     rebelList3.push_front("bel b");
  407.     rebelList3.push_back("e");
  408.     Iterator<string> iter3 = rebelList3.find("e");
  409.     rebelList3.insert(iter3, "re");
  410.     rebelList3.reverse();
  411.     rebelList3.insert(iter3, "th");
  412.     rebelList3.push_back("a");
  413.     iter3.forward();
  414.     rebelList3.insert(iter3, " ");
  415.  
  416.     LinkedList<string> rebelList4 = rebelList3;
  417.     rebelList4[0] = "y, Da";
  418.     rebelList4[3] = "nes";
  419.     rebelList4.reverse();
  420.     rebelList4[1] = "lenti";
  421.     rebelList4.push_back("rt");
  422.     rebelList4.push_front("y v");
  423.     rebelList4.reverse();
  424.     rebelList4[2] = "da";
  425.  
  426.     LinkedList<string> rebelList = rebelList1 + rebelList2;
  427.     rebelList = rebelList4 + rebelList;
  428.     rebelList.push_front("h!\n");
  429.     LinkedList<string> oneWord(1,"s o");
  430.     rebelList = rebelList + oneWord;
  431.     rebelList[9] = "pp";
  432.     rebelList.reverse();
  433.     rebelList.push_front("se i");
  434.     rebelList = rebelList3 + rebelList;
  435.  
  436.  
  437.     rebelList.print();
  438.  
  439.     return 0;
  440. }

Banfa's Avatar
AdministratorVoR
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,188
#2: Feb 14 '08

re: Linked List Program error

Is there a reason you have chosen not to use the STL (Standard Template Library) list class which implements a linked list on a type provided as a template parameter?

i.e.

Expand|Select|Wrap|Line Numbers
  1. #include <list>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     list<string> rebel_list;
  9. }
  10.  
Member
  
Join Date: Feb 2008
Posts: 33
#3: Feb 14 '08

re: Linked List Program error

I was trying to make it myself
and I actually did it
I fixed the errors in my prgram, but still I cant come up with a function for find()
here is what I have

Expand|Select|Wrap|Line Numbers
  1. //find function
  2. template<typename T>
  3. Iterator<T> LinkedList<T>::find(T value) 
  4. {
  5.  
  6.     bool Found;
  7.     Iterator<T> iter;
  8.     iter.position=first;
  9.  
  10.  
  11.    Found = false;
  12.  
  13.    while ((! Found) && (iter.position!=NULL)){
  14.        if (iter.position->data == value)
  15.          return iter;
  16.       else
  17.           iter.position->next;
  18.    }
  19.    iter.position=NULL;
  20.    return iter ;
  21.    }

would you please help me
Moderator
  
Join Date: Mar 2007
Location: North Bend Washington USA
Posts: 5,375
#4: Feb 14 '08

re: Linked List Program error

You are supposed to use the list template like Banfa suggested.

The reason for that template is to not have to debug the linked list over and over and over again.

Use the list template.
Newbie
  
Join Date: Feb 2008
Posts: 2
#5: Feb 14 '08

re: Linked List Program error

I think your pop_back(), pop_front(), push_front(), and push_back() function should be written using erase and insert commands.
Member
  
Join Date: Feb 2008
Posts: 33
#6: Feb 15 '08

re: Linked List Program error

I fixed it, the push_back, find() reverse and push_front has small problems
thanks
Banfa's Avatar
AdministratorVoR
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,188
#7: Feb 15 '08

re: Linked List Program error

Quote:

Originally Posted by APEJMAN

I was trying to make it myself
and I actually did it

Glad you got it all sorted, if you were implementing it as an academic exercise, that is either for course work or for your own practice at programming, then implementing it yourself is fine.

In a commercial project there is never a good reason not to use the STL list. Even, if, as happens occasionally, the compiler you are using has a poor or broken version of the STL you can always download and compile a different, working, version of the STL.


If this was a programming exercise what you should do now is devise some performance tests and compare the performance of you implementation to the STL implementation.
Reply

« previous question | next question »

Similar C / C++ bytes

/bytes/development

/bytes/it

Forums
Visit our community forums for general discussions and latest on Bytes

Our staff and community areas have moved to bytes.com/forums/

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 226,471 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved