By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
434,728 Members | 2,462 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,728 IT Pros & Developers. It's quick & easy.

Linked List Program error

P: 33
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. }
Feb 14 '08 #1
Share this Question
Share on Google+
6 Replies


Banfa
Expert Mod 5K+
P: 8,916
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.  
Feb 14 '08 #2

P: 33
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
Feb 14 '08 #3

weaknessforcats
Expert Mod 5K+
P: 9,197
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.
Feb 14 '08 #4

P: 2
I think your pop_back(), pop_front(), push_front(), and push_back() function should be written using erase and insert commands.
Feb 14 '08 #5

P: 33
I fixed it, the push_back, find() reverse and push_front has small problems
thanks
Feb 15 '08 #6

Banfa
Expert Mod 5K+
P: 8,916
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.
Feb 15 '08 #7

Post your reply

Sign in to post your reply or Sign up for a free account.