//**************************** DLL.java ******************************* // generic doubly linked list class public class DLL { private DLLNode head, tail; public DLL() { head = tail = null; } public boolean isEmpty() { return head == null; } public void clear() { head = tail = null; } public T getFirst() { if (head != null) return head.info; else return null; } public void addToHead(T el) { if (head != null) { head = new DLLNode(el,head,null); head.next.prev = head; } else head = tail = new DLLNode(el); } public void addToTail(T el) { if (tail != null) { tail = new DLLNode(el,null,tail); tail.prev.next = tail; } else head = tail = new DLLNode(el); } public T deleteFromHead() { if (isEmpty()) return null; T el = head.info; if (head == tail) // if only one node on the list; head = tail = null; else { // if more than one node in the list; head = head.next; head.prev = null; } return el; } public T deleteFromTail() { if (isEmpty()) return null; T el = tail.info; if (head == tail) // if only one node on the list; head = tail = null; else { // if more than one node in the list; tail = tail.prev; tail.next = null; } return el; } public void delete(T el) { // delete the node with an element el; DLLNode tmp; for (tmp = head; tmp != null && !el.equals(tmp.info); tmp = tmp.next); //locate the item if (tmp != null) { // item found if (head == tail) //the found item was the only one head = tail = null; else if (head == tmp) { //the found item is the first head = head.next; head.prev = null; } else if (tail == tmp) { // the found item is the last tail = tail.prev; tail.next = null; } else { // the found item is in the middle tmp.prev.next = tmp.next; tmp.next.prev = tmp.prev; } } } public void printAll() { for (DLLNode tmp = head; tmp != null; tmp = tmp.next) System.out.print(tmp.info + " "); } public T find(T el) { DLLNode tmp; for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next); if (tmp == null) return null; else return tmp.info; } // node of generic doubly linked list class class DLLNode { public T info; public DLLNode next, prev; public DLLNode() { next = null; prev = null; } public DLLNode(T el) { info = el; next = null; prev = null; } public DLLNode(T el, DLLNode n, DLLNode p) { info = el; next = n; prev = p; } } } --------------------------------------------------------------------------------------------------------------------------------------------------------------------
TestIntegerDLL
import java.util.Scanner; public class TestIntegerDLL { public static void main (String[] args){ DLL list = new DLL(); int option, target; Scanner stdin = new Scanner(System.in); do { System.out.println(" ***************************"); System.out.println(" Testing Integer DLL "); System.out.println("***************************"); System.out.println("1. Add Node at Head"); System.out.println("2. Add Node at Tail"); System.out.println("3. Print All Nodes"); System.out.println("4. Delete Node from Head"); System.out.println("5. Delete Node from Tail"); System.out.println("6. Delete a Given Node"); System.out.println("7. Search for a Node"); System.out.println("8. Quit"); System.out.print(" Select an Option [1...8] : "); option = stdin.nextInt(); switch (option) { case 1 : System.out.print("Enter the element to add at Head: "); list.addToHead(stdin.nextInt()); break; case 2 : System.out.print("Enter the element to add at Tail: "); list.addToTail(stdin.nextInt()); break; case 3 : list.printAll(); break; case 4 : list.deleteFromHead(); break; case 5 : list.deleteFromTail(); break; case 6 : System.out.print("Enter node to delete: "); target = stdin.nextInt(); if (list.find(target) != null) { list.delete(target); System.out.println("The element "+ target+ " has been deleted"); } else System.out.println("Sorry, element "+ target+ " is not in the list"); break; case 7 : System.out.print("Enter node to search for: "); target = stdin.nextInt(); if (list.find(target) != null) System.out.println("The element "+ target+ " is in the list"); else System.out.println("Sorry, element "+ target+ " is not in the list"); break; } //end of switch } while (option != 8); } //end of main }
CS 205- Data Structures Assignment-1 Submit by :Wednesday, February 14, 2017 (In the Lab) ID: Name: Instructions: Write each of the following methods at the end of the DLL.java given in Labo3. Test your methods by adding the corresponding menu options to the TestintegerDLL.java To submit this assignment, you need to do the following: a) Submit Soft copy by creating a folder D:YourlD_Assign1 and copy the two files (b) Submit a Printed copy containing only the five methods with your ID and Name. Note: You may use your length(0 method (which you did as lab task) to check for the validity of index. . file. . T. public T get(int index) [1 Mark] Returns the element at the given index. Returns null if the index is not valid. Note: index starts at 0. So valid index is in the range Returns the index of the given el if it exists in the list, Returns -1 otherwise. [O length()-11 2. public int indexoffT el) Mark] Returns the index of the given el if it exists in the list., [1 Mark] public void replace(int index, Tel)Replaces the element at the given index with the given el. [1 Mark] Do nothing if the index is not valid. Inserts e/at po 4. public void insertAt(int index, T el) [1.5 Marks] If index is outside the range [o lengthO], your method should ignore the insertion. Deletes and returns the element at the given index if the index is invalid or returns null otherwise. 5. public T deleteAt(int index) [1.5 Marks]
