Linked List

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|612\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Snippet Home -> Misc

shroom_monk	Created : 23 August 2009 Edited : 25 August 2009 Language : Monkey Linked List C++ Linked List V1.0
After Phoenix's feedback, I'm probably not going to update this. I made this because I was unaware of std::list, so wanted to make a Linked List include for myself. Feel free to use it if you want, but it sounds like std::list is better! Here's a Doubly-Linked List in C++ I've been working on. I designed it to try to emulate the features of Types in Blitz Basic, since I always found those to be rather useful. /* Linked List V1.0 Written by James Wallis --Free for use by anyone. Credit would be appreciated if you use this, although it is not compulsory.-- Classes required for a linked list of Data objects. All nodes know their next and previous nodes. The LinkedList remembers the currently selected node. To create a new linked list, create a pointer to a new LinkedList, with the type of object to store in <> brackets after it. For example: LinkedList<Data> * ListOfData = new LinkedList<Data>; Deleting the LinkedList will automatically clean up all allocated memory: delete ListOfData; All methods are called through LinkedList: Insert() - Insert a new node after the currently selected node. New node is selected. InsertStart() - Insert a new node at the start of the list. New node is selected. Remove() - Remove the currently selected node. Previous node is selected (unless first node was removed, in which case the next node is selected). First() - Select the first DataNode. (If no DataNodes exist, then the TailNode is selected). Last() - Select the last DataNode. (If no DataNodes exist, then the HeadNode is selected). Next() - Select the next DataNode. (If the last DataNode is already selected, it remains selected. If no DataNodes exist, the HeadNode is selected.) Prev() - Select the previous DataNode. (If the first DataNode is already selected, it remains selected. If no DataNodes exist, the TailNode is selected.) GetTotalDataNotes() - Returns as an int the total number of DataNodes in the LinkedList. myObject - Pointer to currently selected DataNode's object. Modify object through here. --WARNING--: When GetTotalDataNodes() returns 0, myObject will be NULL. Attempting to call methods or access member data will crash the program. For example, to Insert a new node: ListOfData->Insert(); To then call a function 'ExampleFunction()' of the currently selected node: ListOfData->myObject->ExampleFunction(); See driver program example for a full example of using the LinkedList. / // Inclusion guard. #ifndef LINKEDLIST_CPP #define LINKEDLIST_CPP // Node Abstract Data Type. // All nodes in the LinkedList derive from this, although there are no actualy 'Node's in the list. // DataNode, HeadNode and TailNode derive from this. template <typename T> class Node { public: Node() {} // constructor virtual ~Node() {} // destructor virtual Node<T> Insert() = 0; // insert function (must be overridden) void SetNext(Node<T> * newNext) {myNext = newNext;} // Set pointer to next node in list. void SetPrev(Node<T> * newPrev) {myPrev = newPrev;} // Set pointer to previous node in list. virtual void Remove() = 0; // remove function (must be overridden) Node<T> * GetNext() {return myNext;} // Get pointer to next node in list. Node<T> * GetPrev() {return myPrev;} // Get pointer to previous node in list. T * myObject; // Pointer to object represented by this node. protected: Node<T> * myNext; // Pointer to next node in list. Node<T> * myPrev; // Pointer to previous node in list. }; // DataNode. // The actual objects are represented by this type of node. They are always in the middle of the list. // Derives from Node. template <typename T> class DataNode : public Node<T> { public: DataNode(Node<T> * creatorNode, Node<T> * nextNode); // constructor ~DataNode(); // destructor Node<T> * Insert(); // insert function void Remove(); // remove function }; // DataNode constructor. // Always called by the node before this node in the list. template <typename T> DataNode<T>::DataNode(Node<T> * creatorNode, Node<T> * nextNode) { Node<T>::myPrev = creatorNode; // The creating node must be before this node in the list. Node<T>::myNext = nextNode; // The provided node must be after this node in the list. Node<T>::myNext->SetPrev(this); // Tell the next node in the list that this node is before it. Node<T>::myObject = new T; // Create a new object to be represented by this node. } // DataNode destructor. // Called by deleting the LinkedList or by calling Remove(), however, if called // from Remove(), this function will do nothing except delete the object, since // Remove() will have set the next node to be NULL. template <typename T> DataNode<T>::~DataNode() { delete Node<T>::myNext; // Tell the next node in the list to destroy itself (only if deleting whole list - // if function is called by Remove() then this will do nothing as pointer will be NULL). delete Node<T>::myObject; // Delete the object represented by this list. } // DataNode Insert() function. // Inserts a new DataNode into the LinkedList, directly after this node. // Only called by Insert() function of LinkedList. template <typename T> Node<T> * DataNode<T>::Insert() { Node<T> * temp = Node<T>::myNext; // Store pointer to current next node in list. Node<T>::myNext = new DataNode<T>(this,temp); // Create a new DataNode, and store it as the next node in the list. // Tell new DataNode that the old next node in the list is to be it's // next node, and that this node is the node before this new node. return Node<T>::myNext; // Return a pointer to the newly inserted DataNode (as a Node pointer) to the calling function. } // DataNode Remove() function. // Removes this DataNode from the LinkedList, while 'healing' the gap it leaves by telling // adjacent Nodes to make themselves adjacent. // Calling this function will also invoke the object's destrutor. However, the destructor will not // delete the whole list (see destructor for more info). // Only called by Remove() function of LinkedList. template <typename T> void DataNode<T>::Remove() { Node<T>::myPrev->SetNext(Node<T>::myNext); // Tell the previous node that it's next node is now the node after this node. Node<T>::myNext->SetPrev(Node<T>::myPrev); // Tell the next node that it's previous node is now the node before this node. Node<T>::myPrev = 0; // Set this node's previous pointer to NULL. Node<T>::myNext = 0; // Set this node's next pointer to NULL. delete this; // Delete this node, calling the destructor. } // TailNode. // The last node in any LinkedList. Only 1 per LinkedList. Acts as a sentinel - no node can come after this one. // Derives from Node. template <typename T> class TailNode : public Node<T> { public: TailNode() {Node<T>::myObject = 0;} // constructor - Sets this node's object to be NULL, since the TailNode // cannot represent an object. ~TailNode() {} // destructor - Since the only member variable is myObject, and this is NULL, there is nothing to destroy. void init(Node<T> * initPtr); // init function Node<T> * Insert() {return Node<T>::myPrev->Insert();} // insert function - Passes this call to the previous // node, since no node can come after the TailNode. void Remove() {} // remove function - Does nothing, since the TailNode cannot be removed. }; // TailNode init() function. // Called by the LinkedList constructor on creation of the list, just after the HeadNode and TailNode have been made, // in order to initialise the myNext and myPrev pointers with the location of the HeadNode. This cannot be done in // the constructor as the TailNode does not exist when the HeadNode is made, although the function is retained in the // TailNode for simplicity and uniformity. template <typename T> void TailNode<T>::init(Node<T> * initPtr) { // initPtr will be a pointer to the HeadNode. Node<T>::myNext = initPtr; // Make the next node in the list the HeadNode. // Note: Although in normal use the node after the last node should never be // called, this is simply a fail-safe to stop functions being called on a // NULL pointer. Node<T>::myPrev = initPtr; // Make the previous pointer in the list the HeadNode. } // HeadNode. // The first node in any LinkedList. Only 1 per LinkedList. Denotes the start of the list - no node can come before this one. // Derives from Node. template <typename T> class HeadNode : public Node<T> { public: HeadNode() {Node<T>::myObject = 0;} // constructor - Sets this node's object to be NULL, since the HeadNode // cannot represent an object. ~HeadNode() {delete Node<T>::myNext;} // destructor - The LinkedList's destructor only deletes the HeadNode, // so the HeadNode must initiate the destruction of the next node, // which will destroy the node after that, etc, until the TailNode is reached. void init(Node<T> * initPtr); // init function Node<T> * Insert(); // insert function void Remove() {} // remove function - Does nothing, since HeadNode cannot be removed. }; // HeadNode init() function. // Called by the LinkedList constructor on creation of the list, just after the HeadNode and TailNode have been made, // in order to initialise the myNext and myPrev pointers with the location of the TailNode. This cannot be done in // the constructor as the TailNode does not exist when the HeadNode is made. template <typename T> void HeadNode<T>::init(Node<T> * initPtr) { Node<T>::myNext = initPtr; Node<T>::myPrev = initPtr; } // HeadNode Insert() function. // Inserts a new DataNode into the LinkedList, directly after this node. // Only called by Insert() function of LinkedList if no nodes exist, or the InsertStart() function // of LinkedList if nodes already exist. template <typename T> Node<T> * HeadNode<T>::Insert() { Node<T> * temp = Node<T>::myNext; // Store pointer to current next node in list. Node<T>::myNext = new DataNode<T>(this,temp); // Create a new DataNode, and store it as the next node in the list. // Tell new DataNode that the old next node in the list is to be it's // next node, and that this node is the node before this new node. return Node<T>::myNext; // Return a pointer to the newly inserted DataNode (as a Node pointer) to the calling function. } // LinkedList. // The actual LinkedList class. All actions performed on the list are executed through the functions here. // For operating instructions, see the comments at the top of this file. template <typename T> class LinkedList { public: LinkedList(); // constructor ~LinkedList() {delete myHead;} // destructor - Deletes the HeadNode, causing all nodes in list to be deleted. void Insert(); // insert function void InsertStart(); // insert at start function void Remove(); // remove function void First() {SetMyCurrent(myHead->GetNext());} // Select the first node in the list. void Last() {SetMyCurrent(myTail->GetPrev());} // Select the last node in the list. void Next(); // next function void Prev(); // previous function int GetTotalDataNodes() {return myTotalDataNodes;} // Return the number of DataNodes in the list. T * myObject; // Pointer to currently selected object. private: void SetMyCurrent(Node<T> * target); // Set pointer to currently selected Node in list. Can only be called by // member functions of this list. HeadNode<T> * myHead; // Pointer to the HeadNode of this list. TailNode<T> * myTail; // Pointer to the TailNode of this list. Node<T> * myCurrent; // Pointer to the currently selected Node in this list. int myTotalDataNodes; // Total number of DataNodes in this list. }; // LinkedList constructor. // Prepares the LinkedList upon its creation. template <typename T> LinkedList<T>::LinkedList() { myHead = new HeadNode<T>; // Create the HeadNode for the list. myTail = new TailNode<T>; // Create the TailNode for the list. myHead->init(myTail); // Initialise the HeadNode's next and previous nodes as the TailNode. myTail->init(myHead); // Initialise the TailNode's next and previous nodes as the HeadNode. SetMyCurrent(myHead); // Set the currently selected node to be the HeadNode. myTotalDataNodes = 0; // Initialise total number of DataNodes to 0 (since there are none). } // LinkedList Insert() function. // Manages inserting a new DataNode into the LinkedList after the currently selected Node. template <typename T> void LinkedList<T>::Insert() { myTotalDataNodes++; // Increment the DataNode counter. SetMyCurrent(myCurrent->Insert()); // Tell the currently selected Node (either a HeadNode or DataNode) to insert a new // DataNode after it, then set this new DataNode to be the currently selected Node. } // LinkedList InsertStart() function. // Manages inserting a new DataNode into the LinkedList after the HeadNode; i.e. at the start of the list. // This cannot be done with LinkedList::Insert() because the HeadNode can only be selected when there are no DataNodes in the // list. template <typename T> void LinkedList<T>::InsertStart() { myTotalDataNodes++; // Increment the DataNode counter. SetMyCurrent(myHead); // Set the currently selected Node to the HeadNode. SetMyCurrent(myCurrent->Insert()); // Tell the currently selected Node (the HeadNode) to insert a new DataNode after it, // then set this new DataNode to be the currently selected Node. } // LinkedList Remove() function. // Manages the removal of the currently selected DataNode from the LinkedList, and the administrative clean-up after the // removal. template <typename T> void LinkedList<T>::Remove() { if(!GetTotalDataNodes()==0) // Can only remove a DataNode if there are any DataNodes to remove! { Node<T> * myCurrentPrev = myCurrent->GetPrev(); // Create a temporary copy of the pointer to the node before // the currently selected Node (which will be deleted). myTotalDataNodes--; // Decrememnt the DataNode counter. myCurrent->Remove(); // Call the currently selected Node's Remove() function. This will deal with cleaning // up and 'healing' the gap left by the deleted DataNode. SetMyCurrent(myCurrentPrev); // Set the currently selected Node to now be the Node before the DataNode that was // deleted. if(myCurrent==myHead) SetMyCurrent(myHead->GetNext()); // If the newly selected Node is the HeadNode, then set the // currently selected Node to be the Node after it. } } // LinkedList Next() function. // Sets the currently selected Node to be the Node after the currently selected Node. // This will always be a DataNode, unless there are no DataNodes in the list, in which case it will be the HeadNode. template <typename T> void LinkedList<T>::Next() { SetMyCurrent(myCurrent->GetNext()); // Set the currently selected Node to be the next Node in the list. if(myCurrent==myTail) SetMyCurrent(myTail->GetPrev()); // If the currently selected Node is now the TailNode, then // selected the Node before the TailNode. } // LinkedList Prev() function. // Sets the currently selected Node to be the Node before the currently selected Node. // This will always be a DataNode, unless there are no DataNodes in the list, in which case it will be the TailNode. template <typename T> void LinkedList<T>::Prev() { SetMyCurrent(myCurrent->GetPrev()); // Set the currently selected Node to be the previous Node in the list. if(myCurrent==myHead) SetMyCurrent(myHead->GetNext()); // If the currently selected Node is now the HeadNode, then // selected the Node after the HeadNode. } // LinkedList SetMyCurrent() function. // Sets the currently selected node pointer to the Node provided, and sets the currently selected object (myObject), which // actions are performed on, to be a pointer to the object of the currently selected DataNode, or if it is not a DataNode, // then the pointer is set to NULL for safety. // This function is private, and can only be called by member functions of the LinkedList of which it is a part. template <typename T> void LinkedList<T>::SetMyCurrent(Node<T> * target) { myCurrent = target; // Set the currently selected Node to be the provided Node. // Set the currently selected object: if(myTotalDataNodes==0) { myObject = 0; // If there are no DataNodes in the list, then set this pointer to NULL for safety. } else { myObject = myCurrent->myObject; // If there are DataNodes in the list, then set the currently selected object // to be the object represented by the currently selected Node. This should // always be a DataNode, however in the case that it is the HeadNode or // TailNodew, their myObject pointers should always be NULL anyway. } } // End of inclusion guard. #endif --v Instructions are in the comments in the top of the file. This is V1.0. If anyone has any suggestions for additional features, ways of improving the actual code, or any other suggestions, please post them, so I can make this better. Finally, here's a simple driver program, demonstrating all the features of the Linked List. It seems a little bit convoluted to use, but it allows you to call all the functions of the class, for demonstration purposes. /* Linked List V1.0 - Example Driver Program James Wallis Example Driver Program for Linked List V1.0. Gives options to execute all possible functions of a LinkedList of 'Data'. / #include <iostream> // linked list #include "linkedlist.cpp" // Data class to make list of class Data { public: Data() {myValue=0;} // constructor - Initialises value to 0. ~Data() {} // destructor void SetValue(int value) {myValue = value;} // Set value to supplied integer value. int GetValue() {return myValue;} // Return the integer value held by this object. private: int myValue; // The integer value held by this object. }; // driver int main() { LinkedList<Data> DataList = new LinkedList<Data>; // Create a LinkedList of Data objects. int opt, val; // Variables to hold user input. while(1) // Keep going forever until the loop is broken out of... { // Give the user the option to call any function of the LinkedList, the accessor functions of the currently selected // Data object, or the option to quit the program, destroying the LinkedList. std::cout << "Choose a function: (1) Insert() (2) InsertStart() (3) Remove()\n"; std::cout << "\t\t(4) First() (5) Last() (6) Next() (7) Prev()\n"; std::cout << "\t\t(8) GetTotalDataNodes() (9) Set (10) Get (11) Exit\n"; std::cin >> opt; switch(opt) // Based upon the user choice... { case 1: // Insert a new node after the currently selected node. std::cout << "Insert\n\n"; DataList->Insert(); // Call the Insert() function of the LinkedList. break; case 2: // Insert a new node at the start of the LinkedList. std::cout << "InsertStart\n\n"; DataList->InsertStart(); // Call the InsertStart() function of the LinkedList. break; case 3: // Remove the currently selected node of the LinkedList. std::cout << "Remove\n\n"; DataList->Remove(); // Call the Remove() function of the LinkedList. break; case 4: // Select the first DataNode in the LinkedList. std::cout << "First\n\n"; DataList->First(); // Call the First() function of the LinkedList. break; case 5: // Select the last DataNode in the LinkedList. std::cout << "Last\n\n"; DataList->Last(); // Call the Last() function of the LinkedList. break; case 6: // Select the next DataNode in the LinkedList. std::cout << "Next\n\n"; DataList->Next(); // Call the Next() function of the LinkedList. break; case 7: // Select the previous DataNode in the LinkedList. std::cout << "Prev\n\n"; DataList->Prev(); // Call the Prev() function of the LinkedList. break; case 8: // Return the total number of DataNodes in the LinkedList. std::cout << "GetTotalDataNodes\n" << DataList->GetTotalDataNodes() << "\n\n"; // Print the returned value. break; case 9: // Set the value held by the currently selected node's Data object. std::cout << "Set\n"; if(DataList->GetTotalDataNodes() == 0){ std::cout << "No nodes to set!\n"; // Can't set a value if there are no DataNodes! }else{ // But if there are DataNodes... std::cin >> val; // Take a value (must be an integer). std::cout << "\n"; DataList->myObject->SetValue(val); // Call the SetValue() function of the currently selected node's object. } break; case 10: // Get the value held by the currently selected node's Data object. std::cout << "Get\n"; if(DataList->GetTotalDataNodes() == 0){ std::cout << "There are no nodes!\n"; // Can't get a value if there are no DataNodes! }else{ // But if there are DataNodes... std::cout << DataList->myObject->GetValue(); // Return the value of the GetValue() function of the currently // selected node's object. std::cout << "\n"; } break; case 11: // Exit the program. std::cout << "Exit\n\n"; break; default: break; } if(opt==11) break; // If Exit (option 11) was selected, then break the infinite loop. } delete DataList; // Delete the LinkedList, automatically clearing up all of its Nodes and Data objects. system("pause"); // Pause, so output can be read. return 0; } --v

Comments
Monday, 24 August 2009, 09:30
Phoenix	First off, being the standard library aficionado I am, I'd always opt for the std::list unless I needed something very specific. But I'll throw in some thoughts on what I noticed in the code, since I assume that this was a learning experience. File organization Conventionally, the .cpp extension is used for files containing only implementations, whereas .h files generally contain declarations (but sometimes also implementations, in the case of inline functions). In other words, you should never use #include with a file ending with the .cpp extension. I also personally find the old style of inclusion guards to be a bit tedious to type up all the time. I expect all modern compilers to support the "#pragma once" directive, which you can place at the top instead, to save yourself some typing. Dynamic memory Dynamic memory is usually avoided using raw pointers. Look up smart pointers (here's a popular one), since they handle it much more elegantly. Basically, if you forget to add a "delete xyz" statement somewhere, you have a leak. If a memory allocation fails, and you try to delete it in the destructor, the program will break. Smart pointers do that work for you. I also noticed that you used it in the example ("new LinkedList<Data>"), where automatic memory could have been used just as easily. I might be picky, but when doing other stuff you want to make sure to have leak-free habits. Design The SetNext and SetPrev should probably not be exposed in the public interface, since they allow the user to break the list quite easily. I don't see the point of the Data class, as the list could just as well have been used with a regular integer as template argument. And don't forget const-correctness; members functions which don't mutate the class should have a const after the parameter list and before the function body, and pointers should always be returned as const if possible. Personal moaning I'm not very fond of the "my" prefix added to members. Prefix-less names work fine for me, at least. The commenting on top is good, but I feel that the comments in the source are excessive. For instance: DataList->Next(); // Call the Next() function of the LinkedList. --v It's pretty obvious even without the comments what the code is about. There's also no need to prefix inherited members by the base class's name, as in "Node<T>::myNext". Overall, it might've sounded like I think the code is crap, but that's not the message I intended to give. In the end, the code works, and that's what counts If you want some more features to add, you could try adding iterator support, as found in the standard library.
Monday, 24 August 2009, 12:45
shroom_monk	Actually, that's all really helpful Phoenix! This was something of a learning experience for me, and constructive criticism is the best criticism. In response to your points: -I was unaware of std::list existing, so I'll probably use that instead! -Regarding .cpp and .h, I always found it rather annoying having the declaration in one file, and the implementation in another. But if that's convention, I guess I better get used to it. -#pragma once is another thing I was unaware of. So, if I just put #pragma once at the top of the file, will that ensure it is only included once? -I'll look into smart pointers. Is the only advantage that you don't have to worry about manual deletion, or are there others? -All those public functions in Node seems to have been an oversight on my part, as was omitting the const stuff. Oops... -Regarding prefixing stuff with Node<T>::... I found that this was necessary, because templates and inheriting from base classes don't get along very well (at least not in Dev-C++, which I am now dropping in favour of Code::Blocks, which the internet says is better). The templates refused to acknowledge that the inherited functions existed, and the only way to make it see them was to add Node<T>:: to the front. -As for 'my', I prefer it for things like this, because it reminds me that the function returns the next node for that object, rather than setting it. But that's just a personal preference. So yeah, thanks for the feedback. Since std::list exists, I'm probably not going to update this, and just use that instead. But thanks for taking the time to look through my code - it's a real help to me.
Monday, 24 August 2009, 13:21
Phoenix	You don't have to separate the declaration and implementation. But even then, the file should be named .h, instead of .cpp. #pragma once does exactly what you think it does, i.e. it ensures that the file is only included once. Smart pointers "only" take care of deleting the memory. I think that it's just Dev-C++'s template support which is lacking, since the code builds over here without the base class prefix.
Monday, 24 August 2009, 13:53
JL235	Knowing data structures is important, even if you use the standard library.
Monday, 24 August 2009, 14:35
Afr0	O_O I had no idea you could just put #pragma once to avoid multiple inclusion! Noted!
Tuesday, 25 August 2009, 01:33
shroom_monk	OK, thanks for that Phoenix. @JL: I still plan on looking into how std::list works, to make sure I fully understand it, although I think I have a pretty good idea having learnt about linked lists to make this.
Tuesday, 25 August 2009, 01:51
JL235	It also says that this is implemented in Ruby, not C++! I suspect Jay hasn't fixed that bug yet.
Tuesday, 25 August 2009, 03:41
shroom_monk	Nope, my bad! When I went to edit this, it must have changed while I wasn't looking! When I went to change it back to C++, the drop-down list said HTML/CSS! I think it's not remembering correctly...

Comments