Implement a circular, doubly linked list with a hash table implementation. Don’t

Question

Implement a circular, doubly linked list with a hash table implementation. Don’t use header and trailer nodes in the list, as those nodes were supplied only for easy removal of the first and last nodes from a noncircular list; the first and last nodes didn’t need to be considered as special cases. In a circular list, there aren’t any first and last nodes, so this is not a problem. Be careful about the way you insert nodes, so that an exact physical copy of the hash table is made in the copy constructor and overloaded assignment operator.

Explanation / Answer

import java.util.Scanner; /* Node for doubly linked list */ class DLLNode { DLLNode next, prev; int data; /* Constructor */ public DLLNode(int x) { data = x; next = null; prev = null; } } /* Class HashTableChainingDoublyLinkedList */ class HashTableChainingDoublyLinkedList { private DLLNode[] table; private int size ; /* Constructor */ public HashTableChainingDoublyLinkedList(int tableSize) { table = new DLLNode[ nextPrime(tableSize) ]; size = 0; } /* Function to check if hash table is empty */ public boolean isEmpty() { return size == 0; } /* Function to clear hash table */ public void makeEmpty() { int l = table.length; table = new DLLNode[l]; size = 0; } /* Function to get size */ public int getSize() { return size; } /* Function to insert an element */ public void insert(int val) { size++; int pos = myhash(val); DLLNode nptr = new DLLNode(val); DLLNode start = table[pos]; if (table[pos] == null) table[pos] = nptr; else { nptr.next = start; start.prev = nptr; table[pos] = nptr; } } /* Function to remove an element */ public void remove(int val) { try { int pos = myhash(val); DLLNode start = table[pos]; DLLNode end = start; if (start.data == val) { size--; if (start.next == null) { table[pos] = null; return; } start = start.next; start.prev = null; table[pos] = start; return; } while (end.next != null && end.next.data != val) end = end.next; if (end.next == null) { System.out.println(" Element not found "); return; } size--; if (end.next.next == null) { end.next = null; return; } end.next.next.prev = end; end.next = end.next.next; table[pos] = start; } catch (Exception e) { System.out.println(" Element not found "); } } /* Function myhash */ private int myhash(Integer x ) { int hashVal = x.hashCode( ); hashVal %= table.length; if (hashVal < 0) hashVal += table.length; return hashVal; } /* Function to generate next prime number >= n */ private static int nextPrime( int n ) { if (n % 2 == 0) n++; for ( ; !isPrime( n ); n += 2); return n; } /* Function to check if given number is prime */ private static boolean isPrime( int n ) { if (n == 2 || n == 3) return true; if (n == 1 || n % 2 == 0) return false; for (int i = 3; i * i

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.