Modify the doubly linked list class presented in this chapter so it works with generic types. Add

Fantastic news! We've Found the answer you've been seeking!

Question:

Modify the doubly linked list class presented in this chapter so it works with generic types. Add the following methods drawn from the java.util.List interface:

- void clear(): remove all elements from the list.

- E get (int index): return the element at position index in the list.

- E set(int index, E element): replace the element at the specified position with the specified element and return the previous element.

Test your generic linked list class by processing a list of numbers of type double.

import java.util.Scanner;

/**
* Chapter 20, Programming Challenge 1
*/

// TODO make this class generic
public class GenericLinkedList {

private class Node {
Object value;
Node next;

Node(Object val, Node n) {
value = val;
next = n;
}

Node(Object val) {
this(val, null);
}
}

private Node first;
private Node last;

public void clear() {
// TODO implement
}

public Object get(int index) {
// TODO implement
return null;
}

public Object set(int index, Object element) {
// TODO implement
return null;
}

public boolean isEmpty() {
return first == null;
}

public int size() {
int count = 0;
Node p = first;
while (p != null) {
// There is an element at p
count++;
p = p.next;
}
return count;
}

public void add(Object e) {
if (isEmpty()) {
first = new Node(e);
last = first;
} else {
// Add to end of existing list
last.next = new Node(e);
last = last.next;
}
}

public void add(int index, Object e) {
if (index < 0 || index > size()) {
String message = String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}

// Index is at least 0
if (index == 0) {
// New element goes at beginning
first = new Node(e, first);
if (last == null)
last = first;
return;
}

// Set a reference pred to point to the node that
// will be the predecessor of the new node
Node pred = first;
for (int k = 1; k <= index - 1; k++) {
pred = pred.next;
}

// Splice in a node containing the new element
pred.next = new Node(e, pred.next);

// Is there a new last element ?
if (pred.next.next == null)
last = pred.next;
}

public String toString() {
StringBuilder strBuilder = new StringBuilder();

// Use p to walk down the linked list
Node p = first;
while (p != null) {
strBuilder.append(p.value + "\n");
p = p.next;
}
return strBuilder.toString();
}

public Object remove(int index) {
if (index < 0 || index >= size()) {
String message = String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}

Object element; // The element that will be returned

if (index == 0) {
// Removal of first item in the list
element = first.value;
first = first.next;
if (first == null)
last = null;
} else {
// To remove an element other than the first,
// find the predecessor of the element to
// be removed.
Node pred = first;

// Move pred forward index - 1 times
for (int k = 1; k <= index - 1; k++)
pred = pred.next;

// Store the value to return
element = pred.next.value;

// Route link around the node to be removed
pred.next = pred.next.next;

// Check if pred is now last
if (pred.next == null)
last = pred;
}

return element;
}

public boolean remove(Object element) {
if (isEmpty())
return false;

if (element.equals(first.value)) {
// Removal of first item in the list
first = first.next;
if (first == null)
last = null;
return true;
}

// Find the predecessor of the element to remove
Node pred = first;
while (pred.next != null &&
!pred.next.value.equals(element)) {
pred = pred.next;
}

// pred.next == null OR pred.next.value is element
if (pred.next == null)
return false;

// pred.next.value is element
pred.next = pred.next.next;

// Check if pred is now last
if (pred.next == null)
last = pred;

return true;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

// this will generate an error on first run: you must make the class generic first
GenericLinkedList<Double> ll = new GenericLinkedList<Double>();
ll.add(25.3);
ll.add(5.34);
ll.add(78.3);
ll.add(78.0);
ll.add(2, 23.6);
System.out.println("The members of the list are:");
System.out.print(ll);

// Test the set method
// Get a list position
int index = -1; // Position in the list
double number; // New element to set
do {
System.out.println("Set: Enter a position in the list.");
String indexString = sc.nextLine();
index = Integer.parseInt(indexString);
if (index < 0 || index >= ll.size())
System.err.println("The number you entered is not a legal position.");
} while (index < 0 || index >= ll.size());

// Get the new element to set
System.out.println("Enter a real number.");
String numberString = sc.nextLine();

number = Double.parseDouble(numberString);
Double oldNumber = ll.set(index, number);
System.out.println("Old number was " + oldNumber);

// Display the new list
System.out.println("The members of the list are:");
System.out.print(ll);

// Test the get method
index = -1;
do {
System.out.println("Enter a position in the list.");
String indexString = sc.nextLine();
index = Integer.parseInt(indexString);
if (index < 0 || index >= ll.size())
System.err.println("The number you entered is not a legal position.");
}
while (index < 0 || index >= ll.size());

System.out.println("Get: The element at that position is " + ll.get(index));
}
}