Implement Doubly LinkedList and test the correctness of your program.

1. UML class diagram of class DNode

DNode

element: Object

prev: DNode

next: DNode

+ DNode(Object element, DNode prev, DNode next)

+ getElement(): Object

+ getPrev(): DNode

+ getNext(): DNode

+ setElement(Object element): void

+ setPrev(DNode prev): void

+ setNext(DNode next): void

2. UML class diagram of class DList

DList

header: DNode

trailer: DNode

+ DList()

+ getHeader(): DNode

+ getTrailer(): DNode

+ setHeader(DNode header): void

+ setTrailer(DNode trailer): void

+ print(): void // output all elements in DList

+ addFirst(DNode n): void // add the node n after header

+ addLast(DNode n): void // add the node n before trailer

+ remove(DNode n): void // remove the node n

+ reverse(): void // reverse the Doubly LinkedList

+ main(String[] args): void // test

3. Testing cases:

Create DNodes a (element = 1), b (element = 2), c (element = 3)

Create DList d

Print all elements in d // output nothing

Call addFirst to add b to d; Call addFirst to add a to d; Call addLast to add c to d; then print all elements in d // output 1, 2, 3

Remove b, and then print all elements in d // output 1, 3

Remove a, and then print all elements in d // output 3

Remove c, and then print all elements in d // output nothing

Call addFirst to add b to d; Call addFirst to add a to d; Call addLast to add c to d; then print all elements in d // output 1, 2, 3

Reverse d, and then print all elements in d // output 3, 2, 1

Embed your java files DNode.java and DList.java in the box below.

4. Add more features to class DList, and design testing cases to test them by yourself (you may need them for future project).

Add a method in DList to search whether it contains an element x

Add a method in DList to return the index i of element x

Add a method in DList to add a node at index i

Add a method in DList to remove the node at index i

View keyboard shortcuts

EditViewInsertFormatToolsTable

12pt

Paragraph