/* * Author: 「ＨＡＰＰＹＴＯＨＥＬＰ」 * Date: 18 April 2018 * Purpose: Demonstrate the beauty that is nodes * License: License: CC BY-SA 4.0 * https://creativecommons.org/licenses/by-sa/4.0/ * */ /* brofarops TS#1524090693 */ /* * * ハッピー * Using templates gives me Compilation error. * I'm not used to putting everything in main... * CPP should be different files. data: draw data value [data value] * name->next: draw arrows to point to next node [head]->[next]->[next2]->etc->[tail] * Use h and t as head and tail respectively and change when necessary * */ /* * * The ERROR: Empty List at the end * is the destructor * since we cleared stackLL * */ // SYS_LIBS #include // IO stream buffer #include // IO manipulators [DOESNT WORK ON SL ????] // USER_LIBS //-Node.h // Node visual /******************************************* * * * * DATA * pointer to next node ********* * * * *******************************************/ struct Node{ // I like struct over class, okay? int data; // Data within our node Node *next; // Pointer to the next node // T data; Node *next; Node *prev; doubly linked list // T data; Node *root; Node *left; Node *right; Trees }; // -LinkedList.h LinkedList.cpp class LinkedList { public: // Initialize variables LinkedList(){ head = nullptr; tail = nullptr; size = 0; } // Deallocate memory ~LinkedList(){ clearList(); } /** * Insert a node to the top of the list * A.K.A Push * * @param typename data for the node to hold * * */ void insertTop(int d){ // If the head is empty if (isEmpty()){ // Create the head head = new Node; // [NULL | nullptr] head->data = d; // [d | nullptr] head->next = tail; // [d | tail ] // Our list is size 1 size++; } // If our tail is empty else if(tail == nullptr){ Node *temp = new Node;// Create a temporary node // [NULL | nullptr] temp // Create the tail tail = new Node; // [NULL | nullptr] tail temp->data = d; // [d | nullptr] temp temp->next = head; // [d | head ] temp // Since we are pushing to the top // The head got pushed right, and it is now the tail // The head is now our temporary node tail = head; // [d | tail ] head is now tail head = temp; // [d | head ] temp is now head // End result // head -> tail -> nullptr // Size is now 2 size++; } // If the head and tail exist else { // Create a temporary node Node *temp = new Node; temp->data = d; temp->next = head; // Link to the head // [d | head ] temp // Our head is now the temporary node // Since it got pushed -by happy- head = temp; // [d | previous head ]-> [d | tail] -> [d | nullptr] // head -> previous head -> nullptr // Increment size size++; } } // End method insert topハッピー /** * Insert a node to the end of the list * A.K.A Queue * * @param typename data for the node to hold * * */ void insertEnd(int d){ // If the head is empty if (isEmpty()){ // Create the head head = new Node; // [NULL | nullptr] head->data = d; // [d | nullptr] head->next = tail; // [d | tail ] size++; // increment size } // If tail is empty ハッピー // see @insertTop for detailed explanation else if(tail == nullptr){ // Create new node tail = new Node; tail->data = d; tail->next = nullptr; head->next = tail; // Link head to the tail size++; // Increment size } // If we have head and tail else { // Create a new Node -happy- Node *temp = new Node; // [ NULL | nullptr] temp temp->data = d; // [d | nullptr] temp temp->next = nullptr; // [d | nullptr] temp tail->next = temp; // tail -> temp TS#1524090693 tail = temp; // Our new tail (end) is the // temp node we created size++; // Increment size } } // End method insertEnd /** * Insert a node at given position * A.K.A Queue * * @param int pos position to place node * @param typename d data for node to hold * * */ void insertAt(int pos, int d){ // No negative position, no greater positions if (pos < 0 || pos >= size) std::cout << "No such index " << pos << std::endl; // if index = 0, just push else if (pos == 0){ insertTop(d); } else { // Create node holders Node *nxt = new Node; Node *prev = new Node; nxt=head->next; // Set at index 1 prev=head; // Keep at index 0 // Traverse for (int i = 0; i < pos-1; i++){ nxt = nxt->next; // 1 2 3 4 5 6 7 8 etc, prev = prev->next; // 0 1 2 3 4 5 6 7 etc. } // Create temporary node Node *temp = new Node; temp->data = d; temp->next = nullptr; prev->next = temp; // Link last node to temp temp->next = nxt; // Link temp node to nxt node holder // ---h4pPyVISUAL--- // [prev AKA last Node]->[next AKA next Node] // [new dangling node AKA temp]ハaッピiー // [prev]->[temp]->[next] -happi- size++; // Increment size } } // End method insertAt /** * Remove the node at the top of the list * A.K.A Pop * * */ void removeTop(){ // If all we have is a head, set to nullptr if (size == 1){ tail = nullptr; head = nullptr; } else if (!isEmpty()){ Node *temp = new Node; // [NULL | nullptr] temp temp = head; // temp is now our head head = temp->next; // head is now the next node in the list delete temp; // delete our old head // ---VISUAL--- // [head | next]->[next | next]->[next2 | next2]->ETC // [Dangling nullptr AKA temp] // temp = head so temp contains everything [reference] head has // head now equals [next | next] // delete temp. Reference to old head size--; // Decrement size } // If empty list, output error else std::cout << "Failed to remove top: EMPTY LIST" << std::endl; } // End method removeTop /** * Remove the node at the end of the list * For dequeue * * */ void removeEnd(){ // If all we have is a head, set to nullptr if (size == 1){ tail = nullptr; head = nullptr; } else if (!isEmpty() && size > 1){ Node *temp = new Node; // [NULL | nullptr] temp = tail; // [tail->data | nullptr] temp Node *previous = new Node; // [NULL | nullptr] previous = head; // [head->data | nullptr] previous // go to node before happy tail while (previous->next != tail){ previous = previous->next; } delete temp; // delete our old tail tail = previous; // New tail is the previous node tail->next = nullptr; // link to null since old tail is gone size--; // Decrement size } // If empty list, output error else std::cout << "Cant remove end: EMPTY LIST" << std::endl; } // End method removeEnd /** * Remove the node at given position * By happy * * @param int pos index number to delete at * * */ void removeAt(int pos){ // No high positions // Starts at index 0 and size is nIndex + 1 if (pos >= size){ std::cout << "No such position " << pos << std::endl; } // Remove 0? its the top! else if (pos == 0){ removeTop(); } // Remove end else if (pos == size-1){ removeEnd(); } else { Node *temp = new Node; // [NULL | nullptr] temp Node *prev = new Node; // [NULL | nullptr] prev temp = head; // Start at head T S# 15240 90693 prev = head; // Start at head // Travers for (int i = 0; i < pos; i++){ // Set temp one index greater/ahead if (i == 0){ // ~HAp_pY~ temp = temp->next; } else { // Go ahead indexes temp = temp->next; prev = prev->next; } } // When we get to pos, link previous to ahead, // delete the temp prev->next = temp->next; delete temp; size--; } }// End method remove at /** * Clear list * * @warn Not tested * * */ void clearList(){ // If already empty, output error if (isEmpty())std::cout << "ERROR: Empty List" << std::endl; else { // Set head node to next node // Delete previous/old head do { Node *temp = head->next; delete head; head = temp; size--; } while(head != nullptr); } }// End method clearList /** * Print list * * */ void print(){ Node *temp = new Node; // [NULL | nullptr] temp temp = head; // [head->data | head->next] temp // Traverse while (temp != nullptr){ // Output data of current Node std::cout << temp->data << "->"; // Go to next Node temp = temp->next; } // Output end of list std::cout << "nullptr" << std::endl; } /** * Is the list empty? * * @return true if head is null * @return false if head is not null * * */ bool isEmpty(){ if (head == nullptr)return true; return false; }// End method isEmpty /** * Get size of list * * @return size of list, NOT last index number * * */ int getSize(){ return size; } // End method getSize private: Node *head; // Head of list [Start] Node *tail; // Tail of list [End ]15 240 9 069 3 int size; // Total number of elements };// End class LinkedList // Start method main /** * * @param int argc argument counter * @param char *argv[] argument container * */ int main(int argc, char *argv[]) { /* * * PUSH/STACK-like Linked List * ハッピーtypeof: int * */ LinkedList stackLL; std::cout << "Creating stack list..." << std::endl; // Stacks just push/insert top stackLL.insertTop(7); stackLL.insertTop(23); stackLL.insertTop(65); stackLL.insertTop(420); stackLL.insertTop(935); stackLL.insertTop(3); stackLL.insertTop(57); stackLL.insertTop(88); std::cout << "======Initial Stack List======" << std::endl; stackLL.print(); std::cout << "Current Size: " << stackLL.getSize() << std::endl; std::cout << std::endl; std::cout << "======Push 12======" << std::endl; stackLL.insertTop(12); stackLL.print(); std::cout << "Current Size: " << stackLL.getSize() << std::endl; std::cout << std::endl; std::cout << "======Pop======" << std::endl; stackLL.removeTop(); stackLL.print(); std::cout << "Current Size: " << stackLL.getSize() << std::endl; std::cout << "======Pop======" << std::endl; stackLL.removeTop(); stackLL.print(); std::cout << "Current Size: " << stackLL.getSize() << std::endl; std::cout << "======Pop======" << std::endl; stackLL.removeTop(); stackLL.print(); std::cout << "Current Size: " << stackLL.getSize() << std::endl; std::cout << std::endl; std::cout << "======Clear List======" << std::endl; stackLL.clearList(); stackLL.print(); std::cout << "Current Size: " << stackLL.getSize() << std::endl; std::cout << std::endl; std::cout << "Ending stack list..." << std::endl; std::cout << std::endl; /* * * QUEUE-like Linked List * ハッピーtypeof: string * */ std::cout << "Creating queue dequeue/deque list..." << std::endl; LinkedList qdList; qdList.insertEnd(13); qdList.insertEnd(59); qdList.insertEnd(392); qdList.insertEnd(1784); qdList.insertEnd(2); qdList.insertEnd(67); qdList.insertEnd(924); qdList.insertEnd(204); std::cout << "======Initial Queue List======" << std::endl; qdList.print(); std::cout << "Current Size: " << qdList.getSize() << std::endl; std::cout << std::endl; std::cout << "======Insert 55 at index 4======" << std::endl; qdList.insertAt(4, 55); qdList.print(); std::cout << "Current Size: " << qdList.getSize() << std::endl; std::cout << std::endl; std::cout << "======Insert 33 at the end======" << std::endl; qdList.insertEnd(33); qdList.print(); std::cout << "Current Size: " << qdList.getSize() << std::endl; std::cout << std::endl; std::cout << "======Remove Top/POP======" << std::endl; qdList.removeTop(); qdList.print(); std::cout << "Current Size: " << qdList.getSize() << std::endl; std::cout << std::endl; std::cout << "======Remove End======" << std::endl; qdList.removeEnd(); qdList.print(); std::cout << "Current Size: " << qdList.getSize() << std::endl; std::cout << std::endl; std::cout << "======Remove At Index 5======" << std::endl; qdList.removeAt(5); qdList.print(); std::cout << "Current Size: " << qdList.getSize() << std::endl; return 0; } // End method main

Happy Linked List Stack Queue Dequeue Enqueue W/ Explanation