Implement the dictionary ADT of Figure 4.27 using an unsorted linked list as defined by class LList in Figure 4.8.

Make the implementation as efficient as you can, given the restriction that your implementation must use the unsorted linked list and its access operations to implement the dictionary.

State the asymptotic time requirements for each function member of the dictionary ADT under your implementation.

Transcribed Image Text:

// Linked list implementation class LList implements List { private Link head; private Link tail; protected Link curr; int cnt; //Constructors LList (int size) { this(); } LList() { // Constructor -- Ignore size curr = tail = head = new Link (null); // Create header cnt = 0; } public void clear() { // Remove all elements. // Drop access to links. head.setNext (null); curr = tail = head = new Link (null); // Create header cnt = 0; // Pointer to list header // Pointer to last element // Access to current element // Size of list. } // Insert "it" at current position public void insert (E it) ( curr.setNext (new Link (it, curr.next())); if (tail == curr) tail = curr.next(); // New tail cnt++; } public void append (E it) { // Append "it" to list tail = tail.setNext (new Link (it, null)); cnt++; } public void moveToStart() {curr = head; } } // Set curr at list start // Remove and return current element public E remove() { if (curr.next() == null) return null; E it = curr.next().element (); if (tail == curr.next()) tail = curr; curr.setNext (curr.next() .next()); cnt--; return it; // Nothing to remove // Remember value // Removed last // Remove from list // Decrement count // Return value. Figure 4.8 A linked list implementation.