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

// File: A2SimpleDriver.java // Author: (your name here) / Rita Ester // Date: September 23, 2017 // Description: Basic test driver for CSCI 225 assignment #2 // This file tests some functions of the DLinkedList class of assignment #2. // Not all special cases have been tested; you will be responsible for adding // your own test code and function calls to this file in order to thoroughly // test all general and boundary cases for your functions. // In general, please ensure that you test: // 1. invalid parameter(s) // 2. valid parameter(s), boundary case // 3. valid parameter(s), general case

import java.util.ArrayList;

public class A2SimpleDriver { public static void main(String[] args) { System.out.println("Entering DLinkedList test method..."); listTest_0917(); System.out.println("DLinkedList test method complete!!!");

}

public static void listTest_0917() { DLinkedList listA = new DLinkedList(); listA.insertFront(15); listA.insertBack(105); System.out.println("listA contains " + listA.elementAt(0) + " at index 0."); DLinkedList listB = new DLinkedList(listA); listB.insertAt(17, 1); System.out.println("listA contains 17: " + listA.contains(17)); System.out.println("listB contains 17: " + listB.contains(17)); int val = listA.removeAt(0); System.out.println("listA " + val + " removed from index 0."); System.out.println("listB is empty: " + listB.isEmpty()); listB.insertBack(17); listB.insertBack(120); listB.insertBack(17); System.out.print("listB contains " + listB.size() + " items: "); ArrayList arrayListB = listB.insertForward(); for (int i = 0; i

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

// File: DLinkedList.java

// Author: (your name here)

// Geoffrey Tien/ Rita Ester

// Date: September 23, 2017

// Description: Implementation of a generic doubly-linked list class

// and list node

import java.util.ArrayList;

public class DLinkedList

{

private class DListNode

{

public IT data;

public DListNode prev;

public DListNode next;

public DListNode(IT value)

{

data = value;

prev = null;

next = null;

}

}

private DListNode front;

private DListNode back;

private int size;

// public methods

// default constructor

public DLinkedList(){

// to be completed

}

// copy constructor, clones the sourceList

public DLinkedList(DLinkedList sourceList){

// to be completed

}

// Inserts an item at the front of the list

// POST: List contains item at position 0

// PARAM: item = item to be inserted

public void insertFront(T item){

// to be completed

}

// Inserts an item at the back of the list

// Special case: The empty list

// POST: List contains item at back

// PARAM: item = item to be inserted

public void insertBack(T item){

// to be completed

}

// Inserts an item in position p (0-indexed).

// Throws exception for invalid index (IndexOutOfBoundsException).

// PRE: 0

// POST: List contains item at position p

// PARAM: item = item to be inserted, p = position where item will be inserted

public void insertAt(T item, int p){

// to be completed

}

// Removes and returns an item from position p (0-indexed).

// Throws exception if list is empty (IllegalStateException) or

// if index is invalid (IndexOutOfBoundsException).

// PRE: 0

// POST: Item is removed from list, size has been decreased by 1.

// PARAM: p = position from where item will be removed.

public T removeAt(int p){

// to be completed

}

// Removes duplicates from the list, preserving existing order of remaining items.

// The first occurrence of any duplicate (relative to the front of the list)

// is the one which remains.

// This method should be implemented to have O(n^2) running time or better

// PRE:

// POST: List contains no duplicates, front and back point to the appropriate nodes

// PARAM:

public void removeDuplicates(){

// to be completed

// use two node references

// ptrA iterates from front to back

// ptrB iterates from ptrA to back

// use the equals method to compare two data elements of type

DListNode ptrA = front;

DListNode ptrB; // uninitialized

}

// empties the list

public void clear(){

// to be completed

}

// ACCESSORS

// returns the size of the list

public int size(){

// to be completed

}

// returns whether the list is empty

public boolean isEmpty(){

// to be completed

}

// returns existence of item

public boolean contains(T item){

// to be completed

// use the equals method to compare two data items of type

}

// Returns item at index p (0-indexed)

// Throws exception for invalid index (IndexOutOfBoundsException)

public T elementAt(int p) {

if (p = size)

throw new IndexOutOfBoundsException("DLinkedList::elementAt - invalid position");

else{

// to be completed

}

}

// For testing purposes

// inserts list contents to an ArrayList, traverses from front to back

public ArrayList insertForward()

{

ArrayList al = new ArrayList(size);

DListNode nd = front;

int count = 0;

while (nd != null && count

{

al.add(nd.data);

nd = nd.next;

count++;

}

return al;

}

// For testing purposes

// inserts list contents to an ArrayList, traverses from back to front

public ArrayList insertBackward()

{

ArrayList al = new ArrayList(size);

DListNode nd = back;

int count = 0;

while (nd != null && count

{

al.add(nd.data);

nd = nd.prev;

count++;

}

return al;

}

}

CSCI 225 Assignment 2 A Doubly-Linked List Implementation with Generics Due 10:00 PM Tuesday, October 10,2017 In this assignment, you will design and 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 were mentioned in class and are very similar to the singly-linked lists in your lecture notes. Individual data elements are stored within a node structure, although nodes in doubly-linked lists contain both, a reference to the next list element, as well as a reference to the previous element in the list. The previous element reference at the front of the list and the next element reference at the back of the list are null. With such a doubly-linked structure, the list can be traversed from the front towards the back by following the chain of next element references, and traversed from the back towards the front by following the chain of previous element references. A doubly-linked list can be visualized as follows: front back You must implement the DLinkedList generic class to store data of any reference type (see chapter 18 of your textbook); this includes a generic DListNode template class implemented for you in the DLinkedList.java file. Refer to this file's comments for the class definition and functional requirements. Special attention has to be taken in case the front or the back of a list gets changed by an insertion or a removal. Demonstrating 0-indexed access Consider the following a linked list storing integers: front-16-76-21-53back elementAt (1) returns 76. insertAt(81, 2) will result in the list, where 81 now occupies index 2: front-> 16-76-81-21-53