Data Structures and Algorithms (CS506)

Lab Assignment 6

1. You need to implement a hash table where collisions are resolved via chaining with doubly linked lists. Your program should first ask the user for the hash table size m. Use h(k) = k mod m as the hash function. Your program should support the insert, delete, search and display operations.

   For insertion, your program should ask user to enter a data k to insert, find the slot h(k) and insert the key k into the head of the doubly linked list corresponding to the slot h(k). The delete operation should first ask user to enter a data k you want to delete. Then the delete operation delete k from the doubly linked list corresponding to the slot h(k), if k is present. Othewise,do nothing.

   Search operation ask user to enter a data k to search, and then search k. If k is not present, print: not present, else print present in slot number h(k). Display operation displays the entire data stored in the hash table. Print the data nicely: a newline for each doubly linked lists (corresponding to each slot). Refer some test cases below:

   Test cases:

   Enter hash table size m: 10

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 1
   Enter value to insert: 10
   

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 1
   Enter value to insert: 120
   

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 1
   Enter value to insert: 19
   

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 1
   Enter value to insert: 5
   

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 1
   Enter value to insert: 20
   

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 1
   Enter value to insert: 30
   

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 1
   Enter value to insert: 40
   

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 4
   

   index 0: 40 30 20 120 10
   index 1: NULL
   index 2: NULL
   index 3: NULL
   index 4: NULL
   index 5: 5
   index 6: NULL
   index 7: NULL
   index 8: NULL
   index 9: 19
   

   1. Insert
   2. Delete
   3. Search
   4. Display
   5. Quit

   Enter your choice: 5
   

Sol. Download the Solution file. Open terminal and execute it by running ./solution.o command. Give inputs to get outputs