fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. /*
  5.     ============================================================
  6.     DELETE IN C++ AND DATA STRUCTURES - COMPLETE EXAMPLES
  7.     ============================================================
  8.  
  9.     This file covers:
  10.  
  11.     1) delete for one dynamically allocated variable
  12.     2) delete[] for dynamically allocated arrays
  13.     3) Deleting from a static array using shifting
  14.     4) Deleting from a dynamic array by creating a smaller array
  15.     5) Dangling pointer
  16.     6) nullptr and delete
  17.     7) Double delete problem
  18.     8) Memory leak problem
  19.     9) Array of pointers
  20.     10) 2D dynamic array
  21.     11) Linked list deletion
  22.     12) Destructor and delete
  23.     13) Shallow copy problem with delete
  24.     14) Deep copy solution with delete
  25.     15) Object deletion
  26.     16) Array of objects deletion
  27.     17) Hash table deletion using open addressing
  28.     18) Hash table deletion using chaining
  29.  
  30.     Main rule:
  31.  
  32.         new      -> delete
  33.         new[]    -> delete[]
  34. */
  35.  
  36. /*
  37.     ============================================================
  38.     1) DELETE ONE DYNAMIC VARIABLE
  39.     ============================================================
  40. */
  41.  
  42. void exampleDeleteSingleVariable() {
  43.     cout << "\n================ Example 1: delete single variable ================\n";
  44.  
  45.     int* p = new int;
  46.  
  47.     *p = 50;
  48.  
  49.     cout << "Value before delete: " << *p << endl;
  50.  
  51.     delete p;
  52.  
  53.     p = nullptr;
  54.  
  55.     cout << "Pointer deleted and set to nullptr\n";
  56. }
  57.  
  58. /*
  59.     ============================================================
  60.     2) DELETE DYNAMIC ARRAY
  61.     ============================================================
  62. */
  63.  
  64. void exampleDeleteDynamicArray() {
  65.     cout << "\n================ Example 2: delete[] dynamic array ================\n";
  66.  
  67.     int size = 5;
  68.  
  69.     int* arr = new int[size];
  70.  
  71.     for (int i = 0; i < size; i++) {
  72.         arr[i] = (i + 1) * 10;
  73.     }
  74.  
  75.     cout << "Array values: ";
  76.  
  77.     for (int i = 0; i < size; i++) {
  78.         cout << arr[i] << " ";
  79.     }
  80.  
  81.     cout << endl;
  82.  
  83.     delete[] arr;
  84.  
  85.     arr = nullptr;
  86.  
  87.     cout << "Dynamic array deleted and set to nullptr\n";
  88. }
  89.  
  90. /*
  91.     ============================================================
  92.     3) DELETE ELEMENT FROM STATIC ARRAY USING SHIFTING
  93.     ============================================================
  94.  
  95.     Important:
  96.     - We cannot use delete with a static array.
  97.     - We only shift elements and reduce the logical size.
  98. */
  99.  
  100. void exampleDeleteFromStaticArray() {
  101.     cout << "\n================ Example 3: delete from static array ================\n";
  102.  
  103.     int arr[5] = {10, 20, 30, 40, 50};
  104.  
  105.     int size = 5;
  106.  
  107.     int deleteIndex = 2;
  108.  
  109.     cout << "Before deletion: ";
  110.  
  111.     for (int i = 0; i < size; i++) {
  112.         cout << arr[i] << " ";
  113.     }
  114.  
  115.     cout << endl;
  116.  
  117.     for (int i = deleteIndex; i < size - 1; i++) {
  118.         arr[i] = arr[i + 1];
  119.     }
  120.  
  121.     size--;
  122.  
  123.     cout << "After deleting index 2: ";
  124.  
  125.     for (int i = 0; i < size; i++) {
  126.         cout << arr[i] << " ";
  127.     }
  128.  
  129.     cout << endl;
  130. }
  131.  
  132. /*
  133.     ============================================================
  134.     4) DELETE ELEMENT FROM DYNAMIC ARRAY
  135.     ============================================================
  136.  
  137.     Important:
  138.     - A dynamic array cannot shrink by itself.
  139.     - To delete one element, create a new smaller array.
  140.     - Copy all elements except the deleted one.
  141.     - Delete the old array.
  142. */
  143.  
  144. void exampleDeleteFromDynamicArray() {
  145.     cout << "\n================ Example 4: delete from dynamic array ================\n";
  146.  
  147.     int size = 5;
  148.  
  149.     int* arr = new int[size];
  150.  
  151.     arr[0] = 10;
  152.     arr[1] = 20;
  153.     arr[2] = 30;
  154.     arr[3] = 40;
  155.     arr[4] = 50;
  156.  
  157.     int deleteIndex = 2;
  158.  
  159.     cout << "Before deletion: ";
  160.  
  161.     for (int i = 0; i < size; i++) {
  162.         cout << arr[i] << " ";
  163.     }
  164.  
  165.     cout << endl;
  166.  
  167.     int* newArr = new int[size - 1];
  168.  
  169.     for (int i = 0; i < deleteIndex; i++) {
  170.         newArr[i] = arr[i];
  171.     }
  172.  
  173.     for (int i = deleteIndex + 1; i < size; i++) {
  174.         newArr[i - 1] = arr[i];
  175.     }
  176.  
  177.     delete[] arr;
  178.  
  179.     arr = newArr;
  180.  
  181.     size--;
  182.  
  183.     cout << "After deleting index 2: ";
  184.  
  185.     for (int i = 0; i < size; i++) {
  186.         cout << arr[i] << " ";
  187.     }
  188.  
  189.     cout << endl;
  190.  
  191.     delete[] arr;
  192.  
  193.     arr = nullptr;
  194. }
  195.  
  196. /*
  197.     ============================================================
  198.     5) DANGLING POINTER
  199.     ============================================================
  200.  
  201.     A dangling pointer is a pointer that still stores an old address
  202.     after the memory was deleted.
  203.  
  204.     Accessing a dangling pointer is dangerous.
  205. */
  206.  
  207. void exampleDanglingPointer() {
  208.     cout << "\n================ Example 5: dangling pointer ================\n";
  209.  
  210.     int* p = new int;
  211.  
  212.     *p = 100;
  213.  
  214.     cout << "Value before delete: " << *p << endl;
  215.  
  216.     delete p;
  217.  
  218.     /*
  219.         Wrong:
  220.             cout << *p << endl;
  221.  
  222.         The pointer points to deleted memory.
  223.     */
  224.  
  225.     p = nullptr;
  226.  
  227.     cout << "After delete, pointer is set to nullptr\n";
  228. }
  229.  
  230. /*
  231.     ============================================================
  232.     6) DELETE NULLPTR
  233.     ============================================================
  234.  
  235.     Deleting nullptr is safe.
  236. */
  237.  
  238. void exampleDeleteNullptr() {
  239.     cout << "\n================ Example 6: delete nullptr ================\n";
  240.  
  241.     int* p = nullptr;
  242.  
  243.     delete p;
  244.  
  245.     int* arr = nullptr;
  246.  
  247.     delete[] arr;
  248.  
  249.     cout << "delete nullptr and delete[] nullptr are safe\n";
  250. }
  251.  
  252. /*
  253.     ============================================================
  254.     7) DOUBLE DELETE PROBLEM
  255.     ============================================================
  256.  
  257.     Double delete means deleting the same memory twice.
  258.  
  259.     This is dangerous and causes undefined behavior.
  260.  
  261.     The safe way is:
  262.         delete p;
  263.         p = nullptr;
  264.         delete p;   // safe because p is nullptr
  265. */
  266.  
  267. void exampleDoubleDeleteSafeVersion() {
  268.     cout << "\n================ Example 7: double delete safe version ================\n";
  269.  
  270.     int* p = new int;
  271.  
  272.     *p = 77;
  273.  
  274.     cout << "Value before delete: " << *p << endl;
  275.  
  276.     delete p;
  277.  
  278.     p = nullptr;
  279.  
  280.     delete p;
  281.  
  282.     cout << "Second delete is safe because pointer is nullptr\n";
  283. }
  284.  
  285. /*
  286.     ============================================================
  287.     8) MEMORY LEAK PROBLEM
  288.     ============================================================
  289.  
  290.     A memory leak happens when we allocate memory using new
  291.     and forget to delete it.
  292.  
  293.     The wrong example is shown in comments.
  294. */
  295.  
  296. void exampleMemoryLeakFixed() {
  297.     cout << "\n================ Example 8: memory leak fixed ================\n";
  298.  
  299.     /*
  300.         Wrong:
  301.             int* p = new int;
  302.             *p = 10;
  303.             return;
  304.  
  305.         The memory is never deleted.
  306.     */
  307.  
  308.     int* p = new int;
  309.  
  310.     *p = 10;
  311.  
  312.     cout << "Value: " << *p << endl;
  313.  
  314.     delete p;
  315.  
  316.     p = nullptr;
  317.  
  318.     cout << "Memory was deleted correctly\n";
  319. }
  320.  
  321. /*
  322.     ============================================================
  323.     9) ARRAY OF POINTERS
  324.     ============================================================
  325.  
  326.     There are two allocation levels:
  327.  
  328.     1) The array of pointers:
  329.             int** arr = new int*[3];
  330.  
  331.     2) Each integer:
  332.             arr[i] = new int(value);
  333.  
  334.     So deletion must also happen in two levels:
  335.  
  336.     1) delete each arr[i]
  337.     2) delete[] arr
  338. */
  339.  
  340. void exampleArrayOfPointers() {
  341.     cout << "\n================ Example 9: array of pointers ================\n";
  342.  
  343.     int size = 3;
  344.  
  345.     int** arr = new int*[size];
  346.  
  347.     arr[0] = new int(10);
  348.     arr[1] = new int(20);
  349.     arr[2] = new int(30);
  350.  
  351.     cout << "Values: ";
  352.  
  353.     for (int i = 0; i < size; i++) {
  354.         cout << *arr[i] << " ";
  355.     }
  356.  
  357.     cout << endl;
  358.  
  359.     for (int i = 0; i < size; i++) {
  360.         delete arr[i];
  361.         arr[i] = nullptr;
  362.     }
  363.  
  364.     delete[] arr;
  365.  
  366.     arr = nullptr;
  367.  
  368.     cout << "Array of pointers deleted correctly\n";
  369. }
  370.  
  371. /*
  372.     ============================================================
  373.     10) 2D DYNAMIC ARRAY
  374.     ============================================================
  375.  
  376.     Allocation:
  377.         int** matrix = new int*[rows];
  378.  
  379.         for each row:
  380.             matrix[i] = new int[cols];
  381.  
  382.     Deletion must be in reverse order:
  383.  
  384.         delete[] matrix[i];
  385.         delete[] matrix;
  386. */
  387.  
  388. void example2DDynamicArray() {
  389.     cout << "\n================ Example 10: 2D dynamic array ================\n";
  390.  
  391.     int rows = 3;
  392.     int cols = 4;
  393.  
  394.     int** matrix = new int*[rows];
  395.  
  396.     for (int i = 0; i < rows; i++) {
  397.         matrix[i] = new int[cols];
  398.     }
  399.  
  400.     for (int i = 0; i < rows; i++) {
  401.         for (int j = 0; j < cols; j++) {
  402.             matrix[i][j] = i + j;
  403.         }
  404.     }
  405.  
  406.     cout << "Matrix:\n";
  407.  
  408.     for (int i = 0; i < rows; i++) {
  409.         for (int j = 0; j < cols; j++) {
  410.             cout << matrix[i][j] << " ";
  411.         }
  412.  
  413.         cout << endl;
  414.     }
  415.  
  416.     for (int i = 0; i < rows; i++) {
  417.         delete[] matrix[i];
  418.         matrix[i] = nullptr;
  419.     }
  420.  
  421.     delete[] matrix;
  422.  
  423.     matrix = nullptr;
  424.  
  425.     cout << "2D dynamic array deleted correctly\n";
  426. }
  427.  
  428. /*
  429.     ============================================================
  430.     11) LINKED LIST DELETE EXAMPLES
  431.     ============================================================
  432. */
  433.  
  434. struct ListNode {
  435.     int data;
  436.     ListNode* next;
  437. };
  438.  
  439. void insertFront(ListNode*& head, int value) {
  440.     ListNode* newNode = new ListNode;
  441.  
  442.     newNode->data = value;
  443.     newNode->next = head;
  444.  
  445.     head = newNode;
  446. }
  447.  
  448. void printList(ListNode* head) {
  449.     ListNode* current = head;
  450.  
  451.     while (current != nullptr) {
  452.         cout << current->data << " ";
  453.         current = current->next;
  454.     }
  455.  
  456.     cout << endl;
  457. }
  458.  
  459. void deleteFirst(ListNode*& head) {
  460.     if (head == nullptr) {
  461.         return;
  462.     }
  463.  
  464.     ListNode* temp = head;
  465.  
  466.     head = head->next;
  467.  
  468.     delete temp;
  469. }
  470.  
  471. bool deleteValue(ListNode*& head, int value) {
  472.     ListNode* current = head;
  473.     ListNode* previous = nullptr;
  474.  
  475.     while (current != nullptr) {
  476.         if (current->data == value) {
  477.             if (previous == nullptr) {
  478.                 head = current->next;
  479.             } else {
  480.                 previous->next = current->next;
  481.             }
  482.  
  483.             delete current;
  484.  
  485.             return true;
  486.         }
  487.  
  488.         previous = current;
  489.         current = current->next;
  490.     }
  491.  
  492.     return false;
  493. }
  494.  
  495. void deleteWholeList(ListNode*& head) {
  496.     while (head != nullptr) {
  497.         deleteFirst(head);
  498.     }
  499. }
  500.  
  501. void exampleLinkedListDelete() {
  502.     cout << "\n================ Example 11: linked list delete ================\n";
  503.  
  504.     ListNode* head = nullptr;
  505.  
  506.     insertFront(head, 30);
  507.     insertFront(head, 20);
  508.     insertFront(head, 10);
  509.  
  510.     cout << "Original list: ";
  511.     printList(head);
  512.  
  513.     deleteFirst(head);
  514.  
  515.     cout << "After deleting first node: ";
  516.     printList(head);
  517.  
  518.     deleteValue(head, 30);
  519.  
  520.     cout << "After deleting value 30: ";
  521.     printList(head);
  522.  
  523.     deleteWholeList(head);
  524.  
  525.     cout << "After deleting whole list: ";
  526.     printList(head);
  527. }
  528.  
  529. /*
  530.     ============================================================
  531.     12) DELETE INSIDE DESTRUCTOR
  532.     ============================================================
  533.  
  534.     If a class owns dynamic memory, the destructor should release it.
  535. */
  536.  
  537. class ArrayWithDestructor {
  538. private:
  539.     int* data;
  540.     int size;
  541.  
  542. public:
  543.     ArrayWithDestructor(int s) {
  544.         size = s;
  545.         data = new int[size];
  546.  
  547.         for (int i = 0; i < size; i++) {
  548.             data[i] = 0;
  549.         }
  550.  
  551.         cout << "ArrayWithDestructor constructor called\n";
  552.     }
  553.  
  554.     ~ArrayWithDestructor() {
  555.         delete[] data;
  556.  
  557.         cout << "ArrayWithDestructor destructor called\n";
  558.     }
  559.  
  560.     void set(int index, int value) {
  561.         data[index] = value;
  562.     }
  563.  
  564.     void print() const {
  565.         for (int i = 0; i < size; i++) {
  566.             cout << data[i] << " ";
  567.         }
  568.  
  569.         cout << endl;
  570.     }
  571. };
  572.  
  573. void exampleDestructorDelete() {
  574.     cout << "\n================ Example 12: destructor delete ================\n";
  575.  
  576.     ArrayWithDestructor arr(5);
  577.  
  578.     arr.set(0, 10);
  579.     arr.set(1, 20);
  580.  
  581.     arr.print();
  582.  
  583.     cout << "Destructor will be called automatically at the end of this function\n";
  584. }
  585.  
  586. /*
  587.     ============================================================
  588.     13) SHALLOW COPY PROBLEM WITH DELETE
  589.     ============================================================
  590.  
  591.     This class demonstrates the problem but avoids crashing the program.
  592.  
  593.     In a real dangerous version:
  594.         - The shallow copy constructor copies the pointer address.
  595.         - The destructor deletes the pointer.
  596.         - Two objects may delete the same memory.
  597.  
  598.     To keep this file safe to run, we do not write a destructor here.
  599. */
  600.  
  601. class ShallowCopyArray {
  602. private:
  603.     int* data;
  604.     int size;
  605.  
  606. public:
  607.     ShallowCopyArray(int s) {
  608.         size = s;
  609.         data = new int[size];
  610.  
  611.         for (int i = 0; i < size; i++) {
  612.             data[i] = 0;
  613.         }
  614.     }
  615.  
  616.     ShallowCopyArray(const ShallowCopyArray& other) {
  617.         size = other.size;
  618.         data = other.data;
  619.     }
  620.  
  621.     void set(int index, int value) {
  622.         data[index] = value;
  623.     }
  624.  
  625.     void print() const {
  626.         for (int i = 0; i < size; i++) {
  627.             cout << data[i] << " ";
  628.         }
  629.  
  630.         cout << endl;
  631.     }
  632.  
  633.     /*
  634.         No destructor here on purpose.
  635.  
  636.         If we delete data here, shallow copies may cause double delete.
  637.     */
  638. };
  639.  
  640. void exampleShallowCopyProblem() {
  641.     cout << "\n================ Example 13: shallow copy problem ================\n";
  642.  
  643.     ShallowCopyArray a1(3);
  644.  
  645.     a1.set(0, 10);
  646.     a1.set(1, 20);
  647.     a1.set(2, 30);
  648.  
  649.     ShallowCopyArray a2 = a1;
  650.  
  651.     cout << "a1 before changing a2: ";
  652.     a1.print();
  653.  
  654.     cout << "a2 before changing a2: ";
  655.     a2.print();
  656.  
  657.     a2.set(0, 999);
  658.  
  659.     cout << "a1 after changing a2: ";
  660.     a1.print();
  661.  
  662.     cout << "a2 after changing a2: ";
  663.     a2.print();
  664.  
  665.     cout << "Both objects share the same memory because this is shallow copy\n";
  666. }
  667.  
  668. /*
  669.     ============================================================
  670.     14) DEEP COPY SOLUTION WITH DELETE
  671.     ============================================================
  672.  
  673.     Deep copy allocates new memory for the copied object.
  674.  
  675.     Each object owns its own memory, so the destructor is safe.
  676. */
  677.  
  678. class DeepCopyArray {
  679. private:
  680.     int* data;
  681.     int size;
  682.  
  683. public:
  684.     DeepCopyArray(int s) {
  685.         size = s;
  686.         data = new int[size];
  687.  
  688.         for (int i = 0; i < size; i++) {
  689.             data[i] = 0;
  690.         }
  691.     }
  692.  
  693.     DeepCopyArray(const DeepCopyArray& other) {
  694.         size = other.size;
  695.         data = new int[size];
  696.  
  697.         for (int i = 0; i < size; i++) {
  698.             data[i] = other.data[i];
  699.         }
  700.     }
  701.  
  702.     DeepCopyArray& operator=(const DeepCopyArray& other) {
  703.         if (this == &other) {
  704.             return *this;
  705.         }
  706.  
  707.         delete[] data;
  708.  
  709.         size = other.size;
  710.         data = new int[size];
  711.  
  712.         for (int i = 0; i < size; i++) {
  713.             data[i] = other.data[i];
  714.         }
  715.  
  716.         return *this;
  717.     }
  718.  
  719.     ~DeepCopyArray() {
  720.         delete[] data;
  721.     }
  722.  
  723.     void set(int index, int value) {
  724.         data[index] = value;
  725.     }
  726.  
  727.     void print() const {
  728.         for (int i = 0; i < size; i++) {
  729.             cout << data[i] << " ";
  730.         }
  731.  
  732.         cout << endl;
  733.     }
  734. };
  735.  
  736. void exampleDeepCopySolution() {
  737.     cout << "\n================ Example 14: deep copy solution ================\n";
  738.  
  739.     DeepCopyArray a1(3);
  740.  
  741.     a1.set(0, 10);
  742.     a1.set(1, 20);
  743.     a1.set(2, 30);
  744.  
  745.     DeepCopyArray a2 = a1;
  746.  
  747.     cout << "a1 before changing a2: ";
  748.     a1.print();
  749.  
  750.     cout << "a2 before changing a2: ";
  751.     a2.print();
  752.  
  753.     a2.set(0, 999);
  754.  
  755.     cout << "a1 after changing a2: ";
  756.     a1.print();
  757.  
  758.     cout << "a2 after changing a2: ";
  759.     a2.print();
  760.  
  761.     cout << "Each object has its own memory because this is deep copy\n";
  762. }
  763.  
  764. /*
  765.     ============================================================
  766.     15) DELETE OBJECT
  767.     ============================================================
  768.  
  769.     delete on an object pointer:
  770.     - Calls the destructor.
  771.     - Frees the memory.
  772. */
  773.  
  774. class Student {
  775. private:
  776.     string name;
  777.  
  778. public:
  779.     Student() {
  780.         name = "Unknown";
  781.         cout << "Student constructor called\n";
  782.     }
  783.  
  784.     Student(string n) {
  785.         name = n;
  786.         cout << "Student constructor called for " << name << endl;
  787.     }
  788.  
  789.     ~Student() {
  790.         cout << "Student destructor called for " << name << endl;
  791.     }
  792.  
  793.     void print() const {
  794.         cout << "Student name: " << name << endl;
  795.     }
  796. };
  797.  
  798. void exampleDeleteObject() {
  799.     cout << "\n================ Example 15: delete object ================\n";
  800.  
  801.     Student* s = new Student("Ali");
  802.  
  803.     s->print();
  804.  
  805.     delete s;
  806.  
  807.     s = nullptr;
  808. }
  809.  
  810. /*
  811.     ============================================================
  812.     16) DELETE ARRAY OF OBJECTS
  813.     ============================================================
  814.  
  815.     delete[] on an array of objects:
  816.     - Calls the destructor for each object.
  817.     - Frees the whole array memory.
  818. */
  819.  
  820. void exampleDeleteArrayOfObjects() {
  821.     cout << "\n================ Example 16: delete array of objects ================\n";
  822.  
  823.     Student* students = new Student[3];
  824.  
  825.     delete[] students;
  826.  
  827.     students = nullptr;
  828. }
  829.  
  830. /*
  831.     ============================================================
  832.     17) HASH TABLE DELETE USING OPEN ADDRESSING
  833.     ============================================================
  834.  
  835.     Important problem:
  836.     - In open addressing, we must not simply make a deleted cell EMPTY.
  837.     - Search may stop too early if it sees EMPTY.
  838.     - Instead, we use a DELETED marker, also called a tombstone.
  839.  
  840.     Slot states:
  841.     - EMPTY
  842.     - OCCUPIED
  843.     - DELETED
  844. */
  845.  
  846. class OpenAddressingHashTable {
  847. private:
  848.     enum State {
  849.         EMPTY,
  850.         OCCUPIED,
  851.         DELETED
  852.     };
  853.  
  854.     struct Slot {
  855.         int key;
  856.         State state;
  857.     };
  858.  
  859.     Slot* table;
  860.     int tableSize;
  861.     int count;
  862.  
  863.     int hashFunction(int key) {
  864.         return key % tableSize;
  865.     }
  866.  
  867. public:
  868.     OpenAddressingHashTable(int size) {
  869.         tableSize = size;
  870.         count = 0;
  871.  
  872.         table = new Slot[tableSize];
  873.  
  874.         for (int i = 0; i < tableSize; i++) {
  875.             table[i].key = -1;
  876.             table[i].state = EMPTY;
  877.         }
  878.     }
  879.  
  880.     ~OpenAddressingHashTable() {
  881.         delete[] table;
  882.     }
  883.  
  884.     bool insert(int key) {
  885.         if (count == tableSize) {
  886.             return false;
  887.         }
  888.  
  889.         int h = hashFunction(key);
  890.         int start = h;
  891.         int firstDeleted = -1;
  892.  
  893.         while (true) {
  894.             if (table[h].state == OCCUPIED && table[h].key == key) {
  895.                 return false;
  896.             }
  897.  
  898.             if (table[h].state == DELETED && firstDeleted == -1) {
  899.                 firstDeleted = h;
  900.             }
  901.  
  902.             if (table[h].state == EMPTY) {
  903.                 if (firstDeleted != -1) {
  904.                     table[firstDeleted].key = key;
  905.                     table[firstDeleted].state = OCCUPIED;
  906.                 } else {
  907.                     table[h].key = key;
  908.                     table[h].state = OCCUPIED;
  909.                 }
  910.  
  911.                 count++;
  912.  
  913.                 return true;
  914.             }
  915.  
  916.             h = (h + 1) % tableSize;
  917.  
  918.             if (h == start) {
  919.                 if (firstDeleted != -1) {
  920.                     table[firstDeleted].key = key;
  921.                     table[firstDeleted].state = OCCUPIED;
  922.                     count++;
  923.                     return true;
  924.                 }
  925.  
  926.                 return false;
  927.             }
  928.         }
  929.     }
  930.  
  931.     bool search(int key) {
  932.         int h = hashFunction(key);
  933.         int start = h;
  934.  
  935.         while (true) {
  936.             if (table[h].state == EMPTY) {
  937.                 return false;
  938.             }
  939.  
  940.             if (table[h].state == OCCUPIED && table[h].key == key) {
  941.                 return true;
  942.             }
  943.  
  944.             h = (h + 1) % tableSize;
  945.  
  946.             if (h == start) {
  947.                 return false;
  948.             }
  949.         }
  950.     }
  951.  
  952.     bool remove(int key) {
  953.         int h = hashFunction(key);
  954.         int start = h;
  955.  
  956.         while (true) {
  957.             if (table[h].state == EMPTY) {
  958.                 return false;
  959.             }
  960.  
  961.             if (table[h].state == OCCUPIED && table[h].key == key) {
  962.                 table[h].state = DELETED;
  963.                 count--;
  964.                 return true;
  965.             }
  966.  
  967.             h = (h + 1) % tableSize;
  968.  
  969.             if (h == start) {
  970.                 return false;
  971.             }
  972.         }
  973.     }
  974.  
  975.     void print() const {
  976.         for (int i = 0; i < tableSize; i++) {
  977.             cout << "[" << i << "] ";
  978.  
  979.             if (table[i].state == EMPTY) {
  980.                 cout << "EMPTY";
  981.             } else if (table[i].state == DELETED) {
  982.                 cout << "DELETED";
  983.             } else {
  984.                 cout << table[i].key;
  985.             }
  986.  
  987.             cout << endl;
  988.         }
  989.     }
  990. };
  991.  
  992. void exampleHashTableOpenAddressingDelete() {
  993.     cout << "\n================ Example 17: hash table open addressing delete ================\n";
  994.  
  995.     OpenAddressingHashTable table(10);
  996.  
  997.     table.insert(10);
  998.     table.insert(20);
  999.     table.insert(30);
  1000.  
  1001.     cout << "Before delete:\n";
  1002.     table.print();
  1003.  
  1004.     cout << endl;
  1005.  
  1006.     table.remove(20);
  1007.  
  1008.     cout << "After deleting 20:\n";
  1009.     table.print();
  1010.  
  1011.     cout << endl;
  1012.  
  1013.     cout << "Search 30: " << (table.search(30) ? "Found" : "Not Found") << endl;
  1014.  
  1015.     table.insert(40);
  1016.  
  1017.     cout << "\nAfter inserting 40:\n";
  1018.     table.print();
  1019. }
  1020.  
  1021. /*
  1022.     ============================================================
  1023.     18) HASH TABLE DELETE USING CHAINING
  1024.     ============================================================
  1025.  
  1026.     In chaining:
  1027.     - Each table cell points to a linked list.
  1028.     - Deleting means deleting a node from the linked list.
  1029.     - There is no need for a DELETED marker.
  1030. */
  1031.  
  1032. class ChainingHashTable {
  1033. private:
  1034.     struct Node {
  1035.         int key;
  1036.         Node* next;
  1037.     };
  1038.  
  1039.     Node** table;
  1040.     int tableSize;
  1041.  
  1042.     int hashFunction(int key) {
  1043.         return key % tableSize;
  1044.     }
  1045.  
  1046. public:
  1047.     ChainingHashTable(int size) {
  1048.         tableSize = size;
  1049.  
  1050.         table = new Node*[tableSize];
  1051.  
  1052.         for (int i = 0; i < tableSize; i++) {
  1053.             table[i] = nullptr;
  1054.         }
  1055.     }
  1056.  
  1057.     ~ChainingHashTable() {
  1058.         for (int i = 0; i < tableSize; i++) {
  1059.             Node* current = table[i];
  1060.  
  1061.             while (current != nullptr) {
  1062.                 Node* temp = current;
  1063.                 current = current->next;
  1064.                 delete temp;
  1065.             }
  1066.         }
  1067.  
  1068.         delete[] table;
  1069.     }
  1070.  
  1071.     void insert(int key) {
  1072.         int index = hashFunction(key);
  1073.  
  1074.         Node* newNode = new Node;
  1075.  
  1076.         newNode->key = key;
  1077.         newNode->next = table[index];
  1078.  
  1079.         table[index] = newNode;
  1080.     }
  1081.  
  1082.     bool search(int key) {
  1083.         int index = hashFunction(key);
  1084.  
  1085.         Node* current = table[index];
  1086.  
  1087.         while (current != nullptr) {
  1088.             if (current->key == key) {
  1089.                 return true;
  1090.             }
  1091.  
  1092.             current = current->next;
  1093.         }
  1094.  
  1095.         return false;
  1096.     }
  1097.  
  1098.     bool remove(int key) {
  1099.         int index = hashFunction(key);
  1100.  
  1101.         Node* current = table[index];
  1102.         Node* previous = nullptr;
  1103.  
  1104.         while (current != nullptr) {
  1105.             if (current->key == key) {
  1106.                 if (previous == nullptr) {
  1107.                     table[index] = current->next;
  1108.                 } else {
  1109.                     previous->next = current->next;
  1110.                 }
  1111.  
  1112.                 delete current;
  1113.  
  1114.                 return true;
  1115.             }
  1116.  
  1117.             previous = current;
  1118.             current = current->next;
  1119.         }
  1120.  
  1121.         return false;
  1122.     }
  1123.  
  1124.     void print() const {
  1125.         for (int i = 0; i < tableSize; i++) {
  1126.             cout << "[" << i << "]";
  1127.  
  1128.             Node* current = table[i];
  1129.  
  1130.             while (current != nullptr) {
  1131.                 cout << " -> " << current->key;
  1132.                 current = current->next;
  1133.             }
  1134.  
  1135.             cout << endl;
  1136.         }
  1137.     }
  1138. };
  1139.  
  1140. void exampleHashTableChainingDelete() {
  1141.     cout << "\n================ Example 18: hash table chaining delete ================\n";
  1142.  
  1143.     ChainingHashTable table(10);
  1144.  
  1145.     table.insert(10);
  1146.     table.insert(20);
  1147.     table.insert(30);
  1148.     table.insert(15);
  1149.     table.insert(25);
  1150.  
  1151.     cout << "Before delete:\n";
  1152.     table.print();
  1153.  
  1154.     cout << endl;
  1155.  
  1156.     table.remove(20);
  1157.  
  1158.     cout << "After deleting 20:\n";
  1159.     table.print();
  1160.  
  1161.     cout << endl;
  1162.  
  1163.     cout << "Search 20: " << (table.search(20) ? "Found" : "Not Found") << endl;
  1164.     cout << "Search 30: " << (table.search(30) ? "Found" : "Not Found") << endl;
  1165. }
  1166.  
  1167. /*
  1168.     ============================================================
  1169.     MAIN FUNCTION
  1170.     ============================================================
  1171. */
  1172.  
  1173. int main() {
  1174.     exampleDeleteSingleVariable();
  1175.  
  1176.     exampleDeleteDynamicArray();
  1177.  
  1178.     exampleDeleteFromStaticArray();
  1179.  
  1180.     exampleDeleteFromDynamicArray();
  1181.  
  1182.     exampleDanglingPointer();
  1183.  
  1184.     exampleDeleteNullptr();
  1185.  
  1186.     exampleDoubleDeleteSafeVersion();
  1187.  
  1188.     exampleMemoryLeakFixed();
  1189.  
  1190.     exampleArrayOfPointers();
  1191.  
  1192.     example2DDynamicArray();
  1193.  
  1194.     exampleLinkedListDelete();
  1195.  
  1196.     exampleDestructorDelete();
  1197.  
  1198.     exampleShallowCopyProblem();
  1199.  
  1200.     exampleDeepCopySolution();
  1201.  
  1202.     exampleDeleteObject();
  1203.  
  1204.     exampleDeleteArrayOfObjects();
  1205.  
  1206.     exampleHashTableOpenAddressingDelete();
  1207.  
  1208.     exampleHashTableChainingDelete();
  1209.  
  1210.     cout << "\n================ End of all delete examples ================\n";
  1211.  
  1212.     return 0;
  1213. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
================ Example 1: delete single variable ================
Value before delete: 50
Pointer deleted and set to nullptr

================ Example 2: delete[] dynamic array ================
Array values: 10 20 30 40 50 
Dynamic array deleted and set to nullptr

================ Example 3: delete from static array ================
Before deletion: 10 20 30 40 50 
After deleting index 2: 10 20 40 50 

================ Example 4: delete from dynamic array ================
Before deletion: 10 20 30 40 50 
After deleting index 2: 10 20 40 50 

================ Example 5: dangling pointer ================
Value before delete: 100
After delete, pointer is set to nullptr

================ Example 6: delete nullptr ================
delete nullptr and delete[] nullptr are safe

================ Example 7: double delete safe version ================
Value before delete: 77
Second delete is safe because pointer is nullptr

================ Example 8: memory leak fixed ================
Value: 10
Memory was deleted correctly

================ Example 9: array of pointers ================
Values: 10 20 30 
Array of pointers deleted correctly

================ Example 10: 2D dynamic array ================
Matrix:
0 1 2 3 
1 2 3 4 
2 3 4 5 
2D dynamic array deleted correctly

================ Example 11: linked list delete ================
Original list: 10 20 30 
After deleting first node: 20 30 
After deleting value 30: 20 
After deleting whole list: 

================ Example 12: destructor delete ================
ArrayWithDestructor constructor called
10 20 0 0 0 
Destructor will be called automatically at the end of this function
ArrayWithDestructor destructor called

================ Example 13: shallow copy problem ================
a1 before changing a2: 10 20 30 
a2 before changing a2: 10 20 30 
a1 after changing a2: 999 20 30 
a2 after changing a2: 999 20 30 
Both objects share the same memory because this is shallow copy

================ Example 14: deep copy solution ================
a1 before changing a2: 10 20 30 
a2 before changing a2: 10 20 30 
a1 after changing a2: 10 20 30 
a2 after changing a2: 999 20 30 
Each object has its own memory because this is deep copy

================ Example 15: delete object ================
Student constructor called for Ali
Student name: Ali
Student destructor called for Ali

================ Example 16: delete array of objects ================
Student constructor called
Student constructor called
Student constructor called
Student destructor called for Unknown
Student destructor called for Unknown
Student destructor called for Unknown

================ Example 17: hash table open addressing delete ================
Before delete:
[0] 10
[1] 20
[2] 30
[3] EMPTY
[4] EMPTY
[5] EMPTY
[6] EMPTY
[7] EMPTY
[8] EMPTY
[9] EMPTY

After deleting 20:
[0] 10
[1] DELETED
[2] 30
[3] EMPTY
[4] EMPTY
[5] EMPTY
[6] EMPTY
[7] EMPTY
[8] EMPTY
[9] EMPTY

Search 30: Found

After inserting 40:
[0] 10
[1] 40
[2] 30
[3] EMPTY
[4] EMPTY
[5] EMPTY
[6] EMPTY
[7] EMPTY
[8] EMPTY
[9] EMPTY

================ Example 18: hash table chaining delete ================
Before delete:
[0] -> 30 -> 20 -> 10
[1]
[2]
[3]
[4]
[5] -> 25 -> 15
[6]
[7]
[8]
[9]

After deleting 20:
[0] -> 30 -> 10
[1]
[2]
[3]
[4]
[5] -> 25 -> 15
[6]
[7]
[8]
[9]

Search 20: Not Found
Search 30: Found

================ End of all delete examples ================
https://ideone.com/BmXStG
language:
C++ (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!