Generic Linked Lists: Modify the doubly linked list class presented in this chap
ID: 3759022 • Letter: G
Question
Generic Linked Lists: Modify the doubly linked list class presented in this chapter so it works with generic types. Add the following methods drawn from teh java.util.List interface:
void clear(): remove all elements from the list
E get(int index): return the element at positon index in the list.
E set(int index, E element): replace the element at the specified position wit hthe 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;
// 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 + " ");
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<>();
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));
}
}
Explanation / Answer
package current;
import java.util.Scanner;
//TODO make this class generic
public class GenericLinkedList<E> {
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
int index = 0;
if(first != null) {
Node temp = first;
while( temp != null) {
temp = temp.next;
remove(index);
}
}
}
//index starts from 0
public Object get(int index) {
// TODO implement
int i = 0;
if(first != null) {
Node temp = first;
while( temp != null) {
if(i == index)
return temp.value;
i++;
temp = temp.next;
}
}
return null;
}
public Object set(int index, Object element) {
// TODO implement
int i = 0;
if(first != null) {
Node temp = first;
while( temp != null) {
if(i == index) {
Object prev = temp.value;
temp.value = element;
return prev;
}
i++;
temp = temp.next;
}
}
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 + " ");
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<>();
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 = (Double) 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));
//clear the list
ll.clear();
System.out.println("After clearing the list: size = "+ll.size());
}
}
----outpu----------------
The members of the list are:
25.3
5.34
23.6
78.3
78.0
Set: Enter a position in the list.
2
Enter a real number.
133.456
Old number was 23.6
The members of the list are:
25.3
5.34
133.456
78.3
78.0
Enter a position in the list.
2
Get: The element at that position is 133.456
After clearing the list: size = 0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.