Given the following incomplete implementation of a doubly linked list, fill in t
ID: 3585308 • Letter: G
Question
Given the following incomplete implementation of a doubly linked list, fill in the implementation for the add(), remove(), and clear() methods
import java.lang.IndexOutOfBoundsException;
public class LinkedList <AnyType> {
private Node head;
private Node tail;
private int size;
public LinkedList(){
// NOTE: head and tail are “dummy” nodes that simplify the code, but do not
// actually contain elements.
tail = new Node(null, null, null);
head = new Node(null, null, tail);
tail.setPrev(head);
size = 0;
}
// add the element to the end of the list
public void add(Anytype element){
}
//remove the node of the given index from the list
public void remove(int index) {
}
// clear the list
public void clear() {
}
public AnyType getElement(int index) {
Node current;
If ( index >= size ) {
throw new IndexOutOfBoundsException();
}
If ( index < size / 2 ) {
Current = head.next;
For ( int I = 0; I < index, i++) {
Current = current.next;
}
}
else { // the element is in the second half of the list
current = tail.prev;
for( int I = size – 1; I > index; i++) {
current = current.prev;
}
}
return current.element;
private class Node{ //nexted class within our LinkedList implementation
private AnyType element;
private Node prev;
private Node next;
public Node(Anytype e, Node previousNode, Node nextNode) {
element = e;
prev = previousNode;
next = nextNode;
}
public void setPrev(Node previousNode) {
prev = previousNode;
}
public void setNext(Node nextNode) {
next = nextNode; }
Explanation / Answer
Given below is the completed implementation. Also given is a test program to test the implementation. Please don't forget to rate the answer if it helped. Thank you.
To indent code in eclipse, press Ctrl + A and then Ctrl + I
import java.lang.IndexOutOfBoundsException;
public class LinkedList<AnyType> {
private Node head;
private Node tail;
private int size;
public LinkedList() {
// NOTE: head and tail are “dummy” nodes that simplify the code, but do
// not
// actually contain elements.
tail = new Node(null, null, null);
head = new Node(null, null, tail);
tail.setPrev(head);
size = 0;
}
// add the element to the end of the list
public void add(AnyType element) {
Node n = new Node(element, tail.prev, tail);
n.prev.setNext(n);
n.next.setPrev(n);
size++;
}
// remove the node of the given index from the list
public void remove(int index) {
Node current;
if ( index >= size ) {
throw new IndexOutOfBoundsException();
}
//get the node to be deleted
if ( index < size / 2 ) {
current = head.next;
for ( int i = 0; i < index; i++) {
current = current.next;
}
}
else { // the element is in the second half of the list
current = tail.prev;
for( int i = size - 1; i > index; i--) {
current = current.prev;
}
}
//update the links in previous and next nodes
current.prev.setNext(current.next);
current.next.setPrev(current.prev);
size--;
}
// clear the list
public void clear() {
head.setNext(tail);
tail.setPrev(head);
size = 0;
}
public AnyType getElement(int index) {
Node current;
if ( index >= size ) {
throw new IndexOutOfBoundsException();
}
if ( index < size / 2 ) {
current = head.next;
for ( int i = 0; i < index; i++) {
current = current.next;
}
}
else { // the element is in the second half of the list
current = tail.prev;
for( int i = size - 1; i > index; i--) {
current = current.prev;
}
}
return current.element;
}
public int size()
{
return size;
}
private class Node{ //nested class within our LinkedList implementation
private AnyType element;
private Node prev;
private Node next;
public Node(AnyType e, Node previousNode, Node nextNode) {
element = e;
prev = previousNode;
next = nextNode;
}
public void setPrev(Node previousNode) {
prev = previousNode;
}
public void setNext(Node nextNode) {
next = nextNode;
}
}
}
===============
public class TestLL {
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<Integer>();
for(int i = 0; i < 5; i ++)
numbers.add(2*i);
System.out.println("Displaying the list using getElement");
for(int i = 0; i < 5; i++)
System.out.println("element at index " + i + " = " + numbers.getElement(i));
System.out.println(" removing elements at index 3");
numbers.remove(3);
System.out.println(" Displaying the list using getElement");
for(int i = 0; i < 4; i++) //will have only 4 elements
System.out.println("element at index " + i + " = " + numbers.getElement(i));
}
}
output
Displaying the list using getElement
element at index 0 = 0
element at index 1 = 2
element at index 2 = 4
element at index 3 = 6
element at index 4 = 8
removing elements at index 3
Displaying the list using getElement
element at index 0 = 0
element at index 1 = 2
element at index 2 = 4
element at index 3 = 8
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.