jaberwacky Posted October 31, 2010 Share Posted October 31, 2010 (edited) Yes, I'm a masochist. I finally got around to doing something I've wanted to do for a long time now. I finally just focused my attention and 'got 'r' done!' Simple to you they may be but the concept behind linked lists has eluded me for a long time. I'd like to know what could have been done better or just any advice you could give me. Ultimately I'm just proud of my self because I stopped putting this off for so long. OK, plans:1) Improve the exception handling .2) Implement iterators.3) Improve operator overloading.4) More methods such as: push_front, insert, erase, etc.Main.cppexpandcollapse popup#include <iostream> #include "Linked List.h" using namespace std; template <typename T> void display_list ( LinkedList<T>& ); void display_list_size ( unsigned int ); int main() { const int Length = 10; LinkedList<int> MyList; cout << "Initialize list:\n"; for ( int i = 1; i <= Length; i++ ) { /// MyList.push_back ( i ) MyList = i; cout << "push_back: " << MyList.at ( i - 1 ) << '\n'; } display_list_size ( MyList.size() ); display_list ( MyList ); cout << "\npop_back:" << endl; MyList.pop_back(); display_list_size ( MyList.size() ); display_list ( MyList ); cout << "\nClear: " << endl; MyList.clear(); display_list_size ( MyList.size() ); cin.get(); return 0; } /// --------------------------------------------------------------------------- template <typename T> void display_list ( LinkedList<T> &MyList ) { const unsigned int Size = MyList.size(); cout << "\nDisplay list:\n"; for ( unsigned int i = 1; i <= Size; i++ ) { cout << "MyList.at(" << i - 1 << "): " << MyList.at ( i - 1 ) << '\n'; } } /// --------------------------------------------------------------------------- void display_list_size ( unsigned int Size ) { cout << "\nSize: " << Size << '\n'; } /// ---------------------------------------------------------------------------Node.hexpandcollapse popup#ifndef Node_h #define Node_h using namespace std; template <class T> class Node { public: Node ( const T &Data ) : Cargo ( Data ), Next ( NULL ), Prev ( NULL ) {}; Node ( T &Data ) : Cargo ( Data ), Next ( NULL ), Prev ( NULL ) {}; ~Node(); Node<T> operator ++ (); Node<T> &operator == ( const Node<T> &rhs ) const; T Cargo; Node<T> *Next; Node<T> *Prev; } ; /// --------------------------------------------------------------------------- template <class T> Node<T>::~Node() { Cargo = NULL; Next = NULL; Prev = NULL; } /// --------------------------------------------------------------------------- template <class T> Node<T> Node<T>::operator ++ () { cout << "Paging Dr.++\n"; return ( *this ); } /// --------------------------------------------------------------------------- template <class T> Node<T> &Node<T>::operator == ( const Node<T> &rhs ) const { cout << "Paging Dr.==\n"; if ( this.Cargo == rhs.Cargo ) { cout << "Equal\n"; } return ( *this ); } /// --------------------------------------------------------------------------- #endifLinkedList.hexpandcollapse popup#include <stdexcept> #include <exception> #include "Node.h" using namespace std; template <class T> class LinkedList { public: LinkedList(); ~LinkedList(); Node<T> * Back; Node<T> * Front; unsigned int Length; LinkedList<T> &operator = ( const Node<T> & ); LinkedList<T> &operator == ( const Node<T> & ); T at ( const unsigned int ); Node<T> begin(); void clear(); Node<T> end(); bool isempty(); void pop_back(); void pop_front(); void push_back ( const T ); unsigned int size(); } ; /// --------------------------------------------------------------------------- template <class T> LinkedList<T>::LinkedList() : Back ( NULL ), Front ( NULL ), Length ( 0 ) {} /// --------------------------------------------------------------------------- template <class T> LinkedList<T>::~LinkedList() { clear(); } /// --------------------------------------------------------------------------- template <class T> LinkedList<T> &LinkedList<T>::operator = ( const Node<T> &rhs ) { try { push_back ( rhs.Cargo ); } catch ( ... ) { cerr << "Exception unknown.\n"; } return ( *this ); } /// --------------------------------------------------------------------------- template <class T> LinkedList<T> &LinkedList<T>::operator == ( const Node<T> &rhs ) { cout << "Paging Dr.==\n"; return ( *this ); } /// --------------------------------------------------------------------------- template <class T> T LinkedList<T>::at ( const unsigned int Index ) { T Cargo = 0; try { if ( isempty() ) throw 1; if ( Index > Length ) throw 2; Node<T> * MyNode = Front; for ( unsigned int i = 1; ( i <= Index ) && ( MyNode != NULL ); i++ ) { MyNode = MyNode->Next; } Cargo = MyNode->Cargo; MyNode = NULL; } catch ( int e ) { switch ( e ) { case 1: cerr << "\nIndex is out of bounds.\n"; break; case 2: cerr << "\nList is Empty.\n"; break; } } return Cargo; } /// --------------------------------------------------------------------------- template <class T> Node<T> LinkedList<T>::begin() { return Front; } /// --------------------------------------------------------------------------- template <class T> void LinkedList<T>::clear() { while ( !isempty() ) { pop_back(); } } /// --------------------------------------------------------------------------- template <class T> Node<T> LinkedList<T>::end() { return Back; } /// --------------------------------------------------------------------------- template <class T> bool LinkedList<T>::isempty() { if ( Back == NULL ) { return true; } else { return false; } } /// --------------------------------------------------------------------------- template <class T> void LinkedList<T>::pop_back() { if ( !isempty() ) { if ( Length != 1 ) { Node<T> *TailNode = Back->Prev; TailNode->Next = NULL; delete Back; Back = TailNode; } else { Back = NULL; Front = NULL; } --Length; } } /// --------------------------------------------------------------------------- template <class T> void LinkedList<T>::pop_front() { if ( !isempty() ) { if ( Length != 1 ) { Node<T> * NextNode = Front->Next; delete Front; Front = NextNode; } else { Back = NULL; Front = NULL; } --Length; } } /// --------------------------------------------------------------------------- template <class T> void LinkedList<T>::push_back ( const T Data ) { try { Node<T> * NewNode = new Node<T> ( Data ); if ( isempty() ) { Front = NewNode; Back = NewNode; } else { Back->Next = NewNode; NewNode->Prev = Back; Back = NewNode; } ++Length; NewNode = NULL; } catch ( bad_alloc &e ) { cerr << "Error: Out of memory. =(\n"; } } /// --------------------------------------------------------------------------- template <class T> unsigned int LinkedList<T>::size() { return Length; } /// --------------------------------------------------------------------------- } Edited November 10, 2010 by jaberwocky6669 Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Richard Robertson Posted October 31, 2010 Share Posted October 31, 2010 (edited) I'd have done it with templates. Then the "cargo" could be defined as whatever you wanted. You also don't have an insert function. Edited October 31, 2010 by Richard Robertson Link to comment Share on other sites More sharing options...
jaberwacky Posted October 31, 2010 Author Share Posted October 31, 2010 Ah, I've attempted to use templates before. That's all I have to say about that. I'll definately look into it again though. Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Richard Robertson Posted October 31, 2010 Share Posted October 31, 2010 (edited) Templates are very useful when used correctly. They are worth knowing. Also, don't blindly assume that the index provided to a function is between 0 and length. Add an explicit check. Edited October 31, 2010 by Richard Robertson Link to comment Share on other sites More sharing options...
bo8ster Posted November 1, 2010 Share Posted November 1, 2010 I would add functions like empty (clear the list) and isEmpty(). Otherwise good effort. Also have a looke that the Vector class in the STL for standard function names. You should be able to get the source then see how the templates where used. Post your code because code says more then your words can. SciTe Debug mode - it's magic: #AutoIt3Wrapper_run_debug_mode=Y. Use Opt("MustDeclareVars", 1)[topic="84960"]Brett F's Learning To Script with AutoIt V3[/topic][topic="21048"]Valuater's AutoIt 1-2-3, Class... is now in Session[/topic]Contribution: [topic="87994"]Get SVN Rev Number[/topic], [topic="93527"]Control Handle under mouse[/topic], [topic="91966"]A Presentation using AutoIt[/topic], [topic="112756"]Log ConsoleWrite output in Scite[/topic] Link to comment Share on other sites More sharing options...
jaberwacky Posted November 1, 2010 Author Share Posted November 1, 2010 I actually had some success with templates back when I was a 100% c++ noob. Now that I've gained some ground I'll read up on them. Thanks for the input tip. Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
jaberwacky Posted November 1, 2010 Author Share Posted November 1, 2010 Thanks bo8ster! Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Valik Posted November 1, 2010 Share Posted November 1, 2010 (edited) I see these just quickly glancing over the code.Not const-correct.Does not provide a standard API (push_back(), push_front(), insert() methods among others).Does not have a destructor so memory is leaked or explicitly node destruction must be performed (don't make the user do what a destructor should do).Not a template. Templates are easy, there's no reason not to learn how to write them.Remove() does not set Head->Prev to NULL when Index == 0 (will crash the program).Remove() does not update Tail if the Tail element is deleted (will crash the program).At() returns a valid value on failure. It should throw an exception or signal an error in some other fashion.The return value from Remove() makes no sense. Maybe it should be a bool instead? Or just return the size, I can't recall off the top of my head what is common in this case. Edited November 1, 2010 by Valik Typos. Link to comment Share on other sites More sharing options...
jaberwacky Posted November 1, 2010 Author Share Posted November 1, 2010 Wow, that's tremendous. It'll take me a while to digest all of that. I just got started on the const correctness stuff. Thanks! Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Richard Robertson Posted November 1, 2010 Share Posted November 1, 2010 Specifically, your change to At is still no good. You will still make invalid reads for bad indices. Link to comment Share on other sites More sharing options...
jaberwacky Posted November 1, 2010 Author Share Posted November 1, 2010 (edited) OK, the main changes I've made are trying to make it const correct and I changed Node from a struct to an object. More to come.Hah, I just realized that in my destructor when I evaluate Size in my for loop Size will be decremjented by my Remove() method! So it only deletes half of the list! OK, I fixed that. Edited November 1, 2010 by jaberwocky6669 Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
jaberwacky Posted November 2, 2010 Author Share Posted November 2, 2010 (edited) Ok, my compiler (MinGW) goes nuts when I add the template stuff! Class LinkedList has two members of type Node. This runs fine until I add the template stuff. After that then it says: "error: ISO C++ forbids declaration of 'Node' with no type". Any clues? I tried making class LinkedList a friend of class Node. No joy. I have to admit that this template stuff has made me into a feces flinging code monkey. Edited November 2, 2010 by jaberwocky6669 Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
jaberwacky Posted November 2, 2010 Author Share Posted November 2, 2010 (edited) AHA! I got it!!!!!!!!!!!!!! Okies, so I hope it's const correct now and I hope that templates were implemented correctly. If so then I'm off to implement the rest of everybody's suggestions. Edited November 2, 2010 by jaberwocky6669 Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Richard Robertson Posted November 3, 2010 Share Posted November 3, 2010 Your constructor should take const parameters too. Link to comment Share on other sites More sharing options...
jaberwacky Posted November 3, 2010 Author Share Posted November 3, 2010 Constructor for LinkedList or for Node? Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Richard Robertson Posted November 3, 2010 Share Posted November 3, 2010 (edited) Node. Obviously because it's the only one that even takes a parameter. Also, you can't go returning values for failure. If T = std::string and you return -1, you have a compile time error. You'll need to use a signal or structured exception. Edited November 3, 2010 by Richard Robertson Link to comment Share on other sites More sharing options...
bo8ster Posted November 3, 2010 Share Posted November 3, 2010 (edited) You will have to find an example somewhere however I the last time created a linked list in C++ I made Node a friendly inner class of LinkList. Personal choice I guess ... Edited November 3, 2010 by bo8ster Post your code because code says more then your words can. SciTe Debug mode - it's magic: #AutoIt3Wrapper_run_debug_mode=Y. Use Opt("MustDeclareVars", 1)[topic="84960"]Brett F's Learning To Script with AutoIt V3[/topic][topic="21048"]Valuater's AutoIt 1-2-3, Class... is now in Session[/topic]Contribution: [topic="87994"]Get SVN Rev Number[/topic], [topic="93527"]Control Handle under mouse[/topic], [topic="91966"]A Presentation using AutoIt[/topic], [topic="112756"]Log ConsoleWrite output in Scite[/topic] Link to comment Share on other sites More sharing options...
jaberwacky Posted November 3, 2010 Author Share Posted November 3, 2010 I'm about to wrap up for the night. What I have planned for tommorrow is to read up on exceptions and a crap load of other things like iterators. I really appreciate everybody's insights! Keep 'em coming. Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
jaberwacky Posted November 4, 2010 Author Share Posted November 4, 2010 Ok, Node constructor takes a const param. Also, I tried to implement exceptions to the best of my current understanding. This concludes another productive learning day. I bid you peace. Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
jaberwacky Posted November 4, 2010 Author Share Posted November 4, 2010 (edited) In my push_back method the compiler says that this line will never be executed: "Node<T> * const NewNode = new Node<T> ( Data );". Why should this be? And it seems as though it is executed. The compiler also gives me the same warning everywhere I have a throw statement. Edited November 4, 2010 by jaberwocky6669 Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum? Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now