-------------------------------------------------------------------------------

A1SimpleDriver.java

// File: A1SimpleDriver.java // Author: (your name here) // Rita Ester // Date: January 2019 // Description: Testing for the doubly-linked list class of Ass. 1 //

import java.util.ArrayList;

public class A1SimpleDriver { public static void main(String[] args) { System.out.println("Entering DLinkedList test ..."); listTest(); System.out.println("DLinkedList test (in-complete) ended!!!");

}

public static void listTest() { DLinkedList listA = new DLinkedList(); listA.insertFront(5); listA.insertBack(10); System.out.print("listA: "); printList(listA); DLinkedList listB = new DLinkedList(listA); System.out.print("listB: "); printList(listB); if (listA.equals(listB)) System.out.println("Both lists are equal"); else System.out.println("Both lists are different"); listB.insertAt(7, 1); System.out.print("listB: "); printList(listB); if (listA.equals(listB)) System.out.println("Both lists are equal"); else System.out.println("Both lists are different"); System.out.println("listA contains 7: " + listA.contains(7)); System.out.println("listB contains 7: " + listB.contains(7)); System.out.println("listB element at index 1: " + listB.elementAt(1)); boolean done = listA.removeAll(5); if (done) System.out.print("listA, " + 5 + " removed:"); printList(listA); done = listA.removeAll(10); if (done) System.out.print("listA, " + 10 + " removed: "); printList(listA);

listB.insertBack(7); listB.insertBack(12); listB.insertBack(7); listA = new DLinkedList(listB); System.out.print("listB: "); printList(listB); listB.removeAll(7); System.out.print(" listB 7 removed: "); printList(listB); System.out.print(" listA: "); printList(listA); } public static void printList(DLinkedList ls){ ArrayList arrayList = ls.insertForward(); for (int i = 0; i

-----------------------------------------------------------------------------------------------

DLinkedList.java

// File: DLinkedList.java // Author: (your name here) // Rita Ester // Date: January 2019 // Description: Implementation of a generic 0-indexed doubly-linked list class // and list node

import java.util.ArrayList;

public class DLinkedList { private class DListNode { // one node for a doubly linked list public PT data; public DListNode prev; public DListNode next; public DListNode(PT value){ data = value; prev = null; next = null; } } private DListNode front; // reference to the beginning of the list private DListNode back; // reference to the end of the list // public methods // default constructor public DLinkedList(){ front = null; back = null; } // copy constructor public DLinkedList(DLinkedList other) { // to be completed // copies all data, in the same sequence as in the other list } // returns true if item exists // PARAM: item to be searched for. public boolean contains(T item) { DListNode nd = front; while (nd != null) { if (nd.data.equals(item)) return true; nd = nd.next; } // exited while loop, nd == null, item not found return false; } // returns the size of the list. // this list implementation does not store the size of the list as a private member field. public int size() { // to be completed return -1; } // returns whether the list is empty public boolean isEmpty() { return (front == null); } // Inserts an item at the front of the list // POST: List contains item at front // PARAM: item = item to be inserted public void insertFront(T item) { // to be completed // special case: the list is empty } // Inserts an item at the back of the list // POST: List contains item at back // PARAM: item = item to be inserted public void insertBack(T item) { // to be completed // special case: the list is empty } // Inserts an item in position pos (0-indexed) // Throws exception for invalid index (IndexOutOfBoundsException) // PRE: 0

// tests if two lists have the same size and if they contain the same elements // returns false if the otherList is different from this list. public boolean equals(DLinkedList other) { // to be completed // compare the size and the data. Use the equals method to compare data. return true; } // Returns the item at pos from the list. // Throws an appropriate exception if the index is out of bounds or if the list is empty // PRE: 0

// For testing purposes // inserts list contents to an ArrayList, iterates from front public ArrayList insertForward() { ArrayList al = new ArrayList(); DListNode nd = front; while (nd != null ) { al.add(nd.data); nd = nd.next; } return al; } // For testing purposes // inserts list contents to an ArrayList, iterates from back public ArrayList insertBackward() { ArrayList al = new ArrayList(); DListNode nd = back; while (nd != null) { al.add(nd.data); nd = nd.prev; } return al; } }

CSCI 225 Assignment 1 A Doubly-Linked List Implementation with Generics Due: Monday, January 28, 2019, 10pm In this assignment, you will implement a generic doubly-linked list class. This class can be used in several ways, e.g. to support a generic queue or a generic stack class What is a Doubly-Linked List? Doubly-linked lists are like the singly-linked lists in your lecture notes. Individual data elements are stored within a node structure. Nodes in doubly-linked lists, however, contain both, a reference to the next list element, as well as a reference to the previous list element. The previous reference at the front of the list and the next reference at the back of the list are null. With such a doubly-linked structure, the list can easily be traversed from the front to the back by following the next references, and from the back to the front by following the previous references One node with prev(ious) reference(a), data(b) and next reference (c) A doubly linked list: front back O-indexed access: Consider the following linked list elementAt(1) returns 76 insertAt(81, 2) will result in the following list (81 at index 2) front - 16-76-21-53back front- 16-76-81-21-53 back removeAt(0) returns 16 and results in the list: front-> 76-81-21-53