Advertisement
bwukki

Simple Linked list (first try by an amateur)

May 26th, 2018
202
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdexcept>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. class Node {
  8. public:
  9.     Node(int _data)
  10.     : data{_data}, prev{this}, next{this}
  11.     {}
  12.  
  13.     Node* getNext() const {
  14.         return next;
  15.     }
  16.  
  17.     Node* getPrev() const {
  18.         return prev;
  19.     }
  20.  
  21.     void setNext(Node* ptr) {
  22.         next = ptr;
  23.     }
  24.  
  25.     void setPrev(Node* ptr) {
  26.         prev = ptr;
  27.     }
  28.  
  29.     int getData() const {
  30.         return data;
  31.     }
  32.     Node* prev;
  33.     Node* next;
  34. private:
  35.     int data;
  36. };
  37.  
  38. class DLinkedCircList {
  39. public:
  40.     string toString() const {
  41.         string out{"["};
  42.         if (head != nullptr) {
  43.             int data{};
  44.             Node* currentNode{head};
  45.             do {
  46.                 data = currentNode->getData();
  47.                 out += to_string(data);
  48.                 if (currentNode->getNext() != head) {
  49.                     out += ", ";
  50.                 }
  51.                 currentNode = currentNode->getNext();
  52.             } while (currentNode != head);
  53.         }
  54.         out += "]";
  55.         return out;
  56.     }
  57.  
  58.     DLinkedCircList()
  59.     : head{nullptr}, size{0} {
  60.  
  61.     }
  62.  
  63.     ~DLinkedCircList() {
  64.         Node* lastNode = head->getPrev();
  65.         Node* currentNode = head;
  66.         Node* nextNode{};
  67.         while (currentNode != lastNode) {
  68.             nextNode = currentNode->getNext();
  69.             delete currentNode;
  70.             currentNode = nextNode;
  71.         }
  72.         delete lastNode;
  73.     }
  74.  
  75.     void push_back(int input) {
  76.         Node* newNode{new Node{input}};
  77.         //did the memory get allocated???
  78.         if (head == nullptr) {
  79.             head = newNode;
  80.         }
  81.         else { //add to end
  82.             Node* last{head->getPrev()};
  83.             last->setNext(newNode);
  84.             newNode->setPrev(last);
  85.             newNode->setNext(head);
  86.             head->setPrev(newNode);
  87.         }
  88.         size +=1;
  89.     }
  90.  
  91.     int getSize() {
  92.         return size;
  93.     }
  94.  
  95.     void insert(int data, int location) {
  96.         if (head == nullptr) {
  97.             push_back(data);
  98.         }
  99.         else {
  100.             Node* newNode{new Node{data}};
  101.             if (location == 0) {
  102.                 newNode->setPrev(head->getPrev());
  103.                 newNode->setNext(head);
  104.                 (head->getPrev())->setNext(newNode);
  105.                 head->setPrev(newNode);
  106.                 head = newNode;
  107.                 size +=1;
  108.             }
  109.             else {
  110.                 if (location <= size) {
  111.                     Node* currentNode = at(location);
  112.                     newNode->setPrev(currentNode->getPrev());
  113.                     newNode->setNext(currentNode);
  114.                     (currentNode->getPrev())->setNext(newNode);
  115.                     currentNode->setPrev(newNode);
  116.                     size+=1;
  117.                 }
  118.                 else {
  119.                     cout << "LOCATION INVALID IDIOT" << endl; //throw an exception or something instead of calling the user an idiot
  120.                 }
  121.             }
  122.         }
  123.     }
  124.  
  125.     int pop_back() {
  126.         int result{00};
  127.         if (head != nullptr) {
  128.             result = (head->getPrev())->getData();
  129.             Node* newLast = (head->getPrev())->getPrev();
  130.             newLast->setNext(head);
  131.             delete head->getPrev();
  132.             head->setPrev(newLast);
  133.             size = size-1;
  134.         }
  135.         else {
  136.             cout << "you have no items in this list, idiot" << endl; //throw an exception or something instead of calling the user an idiot
  137.         }
  138.         return result;
  139.     }
  140.  
  141.      erase(int location) {
  142.         if (location >= 0 && location < size) {
  143.             if (head != nullptr) {
  144.                 Node* currentNode = at(location);
  145.                 (currentNode->getPrev())->setNext(currentNode->getNext());
  146.                 (currentNode->getNext())->setPrev(currentNode->getPrev());
  147.                 if (location == 0) { head = currentNode->getNext(); }
  148.                 delete currentNode;
  149.                 currentNode = nullptr;
  150.                 size = size-1;
  151.             }
  152.             else {
  153.                 cout << "you have no items in this list, idiot" << endl; //throw an exception or something instead of calling the user an idiot
  154.             }
  155.         }
  156.         else {
  157.             cout << "invalid location dumbass" << endl;
  158.         }
  159.     }
  160.  
  161.     int cut(int location) {
  162.         int result;
  163.         if (location >= 0 && location < size) {
  164.             if (head != nullptr) {
  165.                 result = (at(location))->getData();
  166.                 erase(location);
  167.             }
  168.             else {
  169.                 cout << "you have no items in this list, idiot" << endl; //throw an exception or something instead of calling the user an idiot
  170.             }
  171.         }
  172.         return result;
  173.     }
  174.  
  175.     Node* at(int location) const {
  176.         if (head != nullptr) {
  177.             Node* currentNode = head;
  178.             if (location <= size) {
  179.                     for (int i = 0; i < location; i++) {
  180.                     currentNode = currentNode->getNext();
  181.                 }
  182.             }
  183.             return currentNode;
  184.         }
  185.     }
  186.  
  187.     int front() const {
  188.         if (head != nullptr) {
  189.             return head->getData();
  190.         }
  191.         else { cout << "no items in list idiot" << endl;}
  192.     }
  193.  
  194.     int back() const {
  195.         if (head != nullptr) {
  196.             return head->getPrev()->getData();
  197.         }
  198.         else { cout << "no items in list idiot" << endl;}
  199.     }
  200.  
  201.     void clear() {
  202.         int originalSize = size;
  203.         for (int i = 0; i < originalSize; i++) {
  204.             erase(0);
  205.          }
  206.          head = nullptr;
  207.     }
  208.  
  209.     DLinkedCircList reverse() {
  210.         DLinkedCircList result{};
  211.         if (head != nullptr) {
  212.             Node* currentNode = head->getPrev();
  213.             Node* nextNode{};
  214.             Node* lastNode = head;
  215.             while (currentNode != lastNode) {
  216.                 result.push_back(currentNode->getData());
  217.                 nextNode = currentNode->getPrev();
  218.                 currentNode = nextNode;
  219.             }
  220.             result.push_back(head->getData());
  221.         }
  222.         else {
  223.             throw invalid_argument("You cannot reverse a list with no elements.");
  224.         }
  225.         return result;
  226.     }
  227.  
  228. private:
  229.     Node* head;
  230.     int size;
  231.  
  232. };
  233.  
  234. void test1() {
  235.     DLinkedCircList test{};
  236.     for (int i{0}; i < 10; i++) {
  237.         test.push_back(i);
  238.     }
  239.     cout << test.toString() << endl;
  240.     cout << test.pop_back() << endl;
  241. }
  242.  
  243. int main()
  244. {
  245.     test1();
  246.     DLinkedCircList testList{};
  247.     testList.push_back(99);
  248.     cout << testList.toString() << endl;
  249.     testList.push_back(105);
  250.     cout << testList.toString() << endl;
  251.     testList.insert(5,0);
  252.     cout << testList.toString() << endl;
  253.     testList.insert(69,0);
  254.     testList.insert(0,0);
  255.     cout << testList.toString() << endl;
  256.     testList.insert(699999,3);
  257.     cout << testList.toString() << endl;
  258.     testList.insert(6999999,6);
  259.     cout << "dividing line..." << endl;
  260.     cout << testList.toString() << endl;
  261.     testList.insert(1111111111,8);
  262.     cout << testList.toString() << endl;
  263.     //cout << testList.pop_back() << endl;
  264.     cout << testList.toString() << endl;
  265.     //cout << testList.cut(5) << endl;
  266.     cout << testList.toString() << endl;
  267.     cout << "trying to erase item zero..." << endl;
  268.     cout << testList.at(0)->getPrev()->getData() << "  :  " << testList.at(0)->getNext()->getData() <<  endl;
  269.     //testList.erase(0);
  270.     cout << testList.toString() << endl;
  271.     cout << "success" << endl;
  272.     cout << testList.toString() << endl;
  273.     //testList.erase(4);
  274.     cout << testList.toString() << endl;
  275.     cout << testList.front() << endl;
  276.     cout << testList.back() << endl;
  277.     testList.clear();
  278.     testList.push_back(1);
  279.     testList.push_back(2);
  280.     testList.push_back(3);
  281.     testList.push_back(4);
  282.     testList.push_back(5);
  283.     cout << testList.toString() << endl;
  284.     cout << "reversed: " << testList.reverse().toString() << endl;
  285.    DLinkedCircList x{};
  286.    x.push_back(1);
  287.    x.push_back(2);
  288.    x.push_back(3);
  289.    cout << "x = " << x.toString() << endl;
  290.    cout << "x reverse: " << x.reverse().toString() << endl;
  291.  
  292.     DLinkedCircList test2{};
  293.     test2.push_back(1);
  294.     cout << test2.toString() << endl;
  295.     cout << "reversed: " << test2.reverse().toString() << endl;
  296.     DLinkedCircList test3{};
  297.     cout << "test3 = " << test3.toString() << endl;
  298.     test3.push_back(1);
  299.     cout << test3.reverse().toString() << endl;;
  300.  
  301.     return 0;
  302. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement