Data Structure and Algorithm Design CSCI 3000 Name: Assignment 3-Linked List For
ID: 3699407 • Letter: D
Question
Data Structure and Algorithm Design CSCI 3000 Name: Assignment 3-Linked List For this assignment, you will be completing several methods in a class named LinkedList.java file. You Date: in the implementation of the following methods using Nodes (you may use as a reference the LinkedList exercise we completed in class using java or C++): getFirst0 addFirst(item) contains(item) set( int n, item) removeNthNode( int n) addNode(int n, item) removeLast) getLast0 It is your task to implement each of the missing methods. The main) method in the LinkedList java file instantiates a linked list that can hold Strings, but your code should work with any objects stored within the list.Explanation / Answer
import java.util.NoSuchElementException;
public class LinkedList<T> {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
int size = 0;
Node<T> first;
Node<T> last;
public LinkedList() {
}
public T getFirst() {
final Node<T> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public void addFirst(T e) {
final Node<T> f = first;
final Node<T> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}
public boolean contains(T o) {
return indexOf(o) != -1;
}
public T set(int index, T element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
Node<T> x = node(index);
T oldVal = x.item;
x.item = element;
return oldVal;
}
public T removeNthNode(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
return delete(node(index));
}
public void addNode(int index, T element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == size)
addNodeToLast(element);
else
addNodeBefore(element, node(index));
}
public T removeLast() {
final Node<T> l = last;
if (l == null)
throw new NoSuchElementException();
final T element = l.item;
final Node<T> prev = l.prev;
l.item = null;
l.prev = null;
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
return element;
}
public T getLast() {
final Node<T> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
/*
* Return node which present at index
*/
Node<T> node(int index) {
Node<T> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
}
public int indexOf(T o) {
int index = 0;
if (o == null) {
for (Node<T> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<T> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
T delete(Node<T> x) {
final T element = x.item;
final Node<T> next = x.next;
final Node<T> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
return element;
}
void addNodeToLast(T e) {
final Node<T> l = last;
final Node<T> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
void addNodeBefore(T e, Node<T> succ) {
final Node<T> pred = succ.prev;
final Node<T> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
}
private static class Node<T> {
T item;
Node<T> next;
Node<T> prev;
Node(Node<T> prev, T element, Node<T> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.