1. The following code is the start of the LinkedList class public class LinkedLi
ID: 3828458 • Letter: 1
Question
1. The following code is the start of the LinkedList class
public class LinkedList<E> implements List<E> {
private LinkedNode<E> head;
private LinkedNode<E> tail;
private int size;
public LinkedList() {
head = null;
tail = null;
size = 0;
} }
Add stubbed versions of all of the methods required by the List interface and implement the add method to add an element to the end of the list.
describe the best, average, and worst case time complexity of the method using Big O notation. What would the complexity be without a tail?
2. Implement the get(int index) method. describe the best, average, and worst case time complexity of the method using Big O notation.
3. Implement the size() method. This should be simple provided that you use the size field appropriately. describe the time complexity of the size() method. What would the complexity be without a size field, and why?
4. Add a toString() method that uses size and get to print the contents of your list. Use this method to print “before” and “after” versions of your list for each of your test cases, e.g. before and after adding a few elements. Use it for the remaining parts of the homework as well.
5. Implement the remove(int index) method. describe the best, average, and worst case time complexity of the method using Big O notation.
6. Implement the insert(int index, E element) method. describe the best, average, and worst case time complexity of the method using Big O notation.
Explanation / Answer
LinkedList.java:
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Spliterator;
import java.util.function.UnaryOperator;
public class LinkedList<E> implements List<E> {
private LinkedNode<E> head;
private LinkedNode<E> tail;
private int size;
public LinkedList() {
head = null;
tail = null;
size = 0;
}
/*
* The complexity with tail pointer will always be O(1), as we just need to
* insert at the last, and don't need to iterate over the list to find the
* position however, if tail pointer would not have been there, It would
* have been O(N) as we would have to traverse the list from start to end to
* find the last element to insert the new node
*/
@Override
public boolean add(E data) {
LinkedNode<E> node = new LinkedNode<E>(data);
if (size == 0) {
head = tail = node;
} else {
tail.next = node;
tail = node;
}
size++;
return true;
}
/*
* The complexity for below will be O(N) in average and worst case..
* But if we try to insert at start or end, it will be O(1) the best case
*/
@Override
public void add(int index, E data) {
// invalid index
if (index < 0 || index > size)
return;
LinkedNode<E> node = new LinkedNode<E>(data);
if (index == 0 && size == 0) {
add(data);
} else if (index == 0) {
node.next = head;
head = node;
size++;
} else if (index == size) {
tail.next = node;
size++;
tail = node;
} else {
int count = 0;
LinkedNode<E> current = head;
while (current != null) {
if (count == index)
break;
current = current.next;
count++;
}
node.next = current.next;
current.next = node;
size++;
}
}
@Override
public boolean addAll(Collection<? extends E> arg0) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean addAll(int arg0, Collection<? extends E> arg1) {
// TODO Auto-generated method stub
return false;
}
@Override
public void clear() {
// TODO Auto-generated method stub
}
@Override
public boolean contains(Object arg0) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean containsAll(Collection<?> arg0) {
// TODO Auto-generated method stub
return false;
}
// The best case for below method would occur when we are asked to get the
// nearest element from the start
// i.e the header node.. The worst case would be O(N) when we are asked to
// fetch the last node of the list.. in average it is O(N)
@Override
public E get(int index) {
if (index < 0 || index > size - 1)
return null;
int count = 0;
LinkedNode<E> p = head;
while (p != tail) {
if (count == index) {
break;
}
p = p.next;
count++;
}
return p.data;
}
@Override
public int indexOf(Object arg0) {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
@Override
public Iterator<E> iterator() {
// TODO Auto-generated method stub
return null;
}
@Override
public int lastIndexOf(Object arg0) {
// TODO Auto-generated method stub
return 0;
}
@Override
public ListIterator<E> listIterator() {
// TODO Auto-generated method stub
return null;
}
@Override
public ListIterator<E> listIterator(int arg0) {
// TODO Auto-generated method stub
return null;
}
@Override
public boolean remove(Object arg0) {
// TODO Auto-generated method stub
return false;
}
/*
* The complexity is O(1) if we need to delete the first node, i.e. head
* node.. For all other cases its O(N), as we need to traverse complete list
* to delete a element
*/
@Override
public E remove(int index) {
if (index < 0 || index > size - 1) {
return null;
} else {
LinkedNode<E> retNode = null;
if (size == 1) {
retNode = head;
head = tail = null;
size = 0;
} else if (index == 0) {
retNode = head;
head = head.next;
size--;
} else if (index == size - 1) {
// remove last node
retNode = tail;
LinkedNode<E> current = head;
while (current.next != tail) {
current = current.next;
}
tail = current;
size--;
} else {
LinkedNode<E> prev = null;
LinkedNode<E> current = head;
int count = 0;
while (current != null) {
if (count == index) {
break;
}
count++;
prev = current;
current = current.next;
}
prev.next = current.next;
retNode = current;
size--;
}
return retNode.data;
}
}
@Override
public boolean removeAll(Collection<?> arg0) {
// TODO Auto-generated method stub
return false;
}
@Override
public void replaceAll(UnaryOperator<E> arg0) {
// TODO Auto-generated method stub
}
@Override
public boolean retainAll(Collection<?> arg0) {
// TODO Auto-generated method stub
return false;
}
@Override
public E set(int arg0, E arg1) {
// TODO Auto-generated method stub
return null;
}
/*
* As we have a size field, the complexity is a O(1) operation.. However in
* absence of that field, We would have to traverse the list from start to
* end, and then complexisty would have been O(N)
*/
@Override
public int size() {
return size;
}
@Override
public void sort(Comparator<? super E> arg0) {
// TODO Auto-generated method stub
}
@Override
public Spliterator<E> spliterator() {
// TODO Auto-generated method stub
return null;
}
@Override
public List<E> subList(int arg0, int arg1) {
// TODO Auto-generated method stub
return null;
}
@Override
public Object[] toArray() {
// TODO Auto-generated method stub
return null;
}
@Override
public <T> T[] toArray(T[] arg0) {
// TODO Auto-generated method stub
return null;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (size == 0) {
sb.append("The List is Empty. ");
} else {
sb.append("List is: ");
LinkedNode<E> p = head;
while (p.next != null) {
sb.append(p.toString() + " ");
p = p.next;
}
}
return sb.toString();
}
}
class LinkedNode<E> {
E data;
LinkedNode<E> next;
public LinkedNode(E data) {
this.data = data;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.