// File: DLinkedList.java

// Author: (your name here)

// Geoffrey Tien/ Rita Ester

// Date: January 2018

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

// and list node

import java.util.ArrayList;

public class DLinkedList

{

private class DListNode

{

public PT data;

public DListNode prev;

public DListNode next;

public DListNode(PT value)

{

data = value;

prev = null;

next = null;

}

}

private DListNode front;

private DListNode back;

private int n;

// public methods

// default constructor

public DLinkedList()

{

n = 0;

front = null;

back = null;

}

// copy constructor

public DLinkedList(DLinkedList ll)

{

// to be completed

}

// 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

}

// 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

}

// Inserts an item in position pos (0-indexed)

// Throws exception for invalid index (IndexOutOfBoundsException)

// PRE: 0

// POST: List contains item at position p

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

public void insertAt(T item, int pos)

{

// to be completed

}

// 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

return true;

}

// returns the last index of item in the list, starting with index 0.

// returns -1 if item is not found, or if the list is empty.

public int lastIndexOf(T item){

// to be completed

return -1;

}

// returns the first index of item in the list, starting with index 0.

// returns -1 if item is not found, or if the list is empty.

public int firstIndexOf(T item){

// to be completed

return -1;

}

// Removes the first occurrence of item from the list

// POST: Item is removed from list,

// PARAM: item to be removed

// returns true if successfully removed the item.

public boolean remove(T item)

{

// to be completed

return true;

}

// Removes all occurrences of item from the list

// POST: all items are removed from list,

// PARAM: item to be removed

// returns true if successfully removed all items.

public boolean removeAll(T item)

{

// to be completed

return true;

}

// 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

// two node pointers

// ptrA iterates from front to back

// ptrB iterates from ptrA.next to back

DListNode ptrA = front;

DListNode ptrB;

}

// returns the size of the list

public int size()

{

return n;

}

// returns whether the list is empty

public boolean isEmpty()

{

return (front == null);

}

// returns true if item exists

// PARAM: item to be searched for.

public boolean contains(T item)

{

// to be completed

return true;

}

// For testing purposes

// inserts list contents to an ArrayList, iterates from front

public ArrayList insertForward()

{

ArrayList al = new ArrayList(n);

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, iterates from back

public ArrayList insertBackward()

{

ArrayList al = new ArrayList(n);

DListNode nd = back;

int count = 0;

while (nd != null && count

{

al.add(nd.data);

nd = nd.prev;

count++;

}

return al;

}

}

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

import java.util.ArrayList;

public class A2SimpleDriver2

{

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.println("listA: ");

printList(listA);

DLinkedList listB = new DLinkedList(listA);

listB.insertAt(7, 1);

System.out.println("listA contains 7: " + listA.contains(7));

System.out.println("listB contains 7: " + listB.contains(7));

boolean done = listA.remove(5);

if (done)

System.out.println("listA " + 5 + " removed:");

printList(listA);

done = listA.remove(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 contains " + listB.size() + " items: ");

printList(listB);

listB.removeAll(7);

System.out.print(" listB contains " + listB.size() + " items: ");

printList(listB);

System.out.print(" listA contains " + listA.size() + " items: ");

printList(listA);

listA.removeDuplicates();

System.out.print(" listA contains " + listA.size() + " items: ");

printList(listA);

}

public static void printList(DLinkedList ls){

ArrayList arrayList = ls.insertForward();

for (int i = 0; i

{

System.out.print(arrayList.get(i) + " ");

}

System.out.println();

}

}

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 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 as a reference to the previous element in the list 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 generie 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 remova Demonstrating 0-indexed access: Consider the following a linked list storing integers: front-16-76-21-53 16-76- 81-21-53 76-81 - 21-53 back