(Implement a doubly linked list) The MyLinkedList class used in Listing 24.6 is
ID: 3858774 • Letter: #
Question
(Implement a doubly linked list) The MyLinkedList class used in Listing 24.6 is a one-way directional linked list that enables one-way traversal of the list. Modify the Node class to add the new data field name previous to refer to the previous node in the list, as follows:
public class Node<E> {
E element;
Node<E> next;
Node<E> previous;
public Node(E e) {
element = e;
}
}
Implement a new class named TwoWayLinkedList that uses a doubly linked list to store elements. The MyLinkedList class in the text extends MyAbstractList. Define TwoWayLinkedList to extend the java.util.AbstractSequentialList class. You need to implement all the methods defined in MyLinkedList as well as the methods listIterator() and listIterator(int index). Both return an instance of java.util. ListIterator<E>. The former sets the cursor to the head of the list and the latter to the element at the specified index.
Explanation / Answer
import java.util.AbstractSequentialList;
import java.util.ListIterator;
public class TwoWayLinkedList<E> extends AbstractSequentialList<E> {
class Node<E> {
E element;
Node<E> next;
Node<E> previous;
public Node(E element) {
this.element = element;
next = null;
previous = null;
}
}
Node<E> head;
Node<E> tail;
int size;
public TwoWayLinkedList() {
head = null;
tail = null;
size = 0;
}
@Override
public E get(int index) {
// TODO Auto-generated method stub
return super.get(index);
}
@Override
public void add(int index, E element) {
if (index > size || index < 0)
throw new IllegalArgumentException();
Node<E> newNode = new Node<>(element);
if (head == null)
head = tail = newNode;
else if (index == 0) {
newNode.next=head;
head.previous = newNode;
head = newNode;
}
else if (index == size){
newNode.previous = tail;
tail.next = newNode;
tail = newNode;
}
else {
Node<E> current = head;
for (int pos = 1; pos < index; pos++)
current = current.next;
newNode.previous = current;
newNode.next = current.next;
current.next.previous = newNode;
current.next = newNode;
}
size++;
}
@Override
public E remove(int index) {
if (index < 0 || index>=size)
throw new IllegalArgumentException();
Node<E> victim;
if (index == 0 && size == 1) {
victim = head;
head = tail = null;
}
else if (index == 0) {
victim = head;
head = head.next;
head.previous = null;
}
else if (index == size - 1) {
victim = tail;
tail = tail.previous;
tail.next = null;
}
else {
victim = head;
for (int pos = 0; pos < index; pos++)
victim = victim.next;
victim.previous.next = victim.next;
victim.next.previous = victim.previous;
}
size --;
return victim.element;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
Node<E> current = head;
for (int pos = 0; pos < size; pos++) {
if (current.element.equals(o))
return true;
current = current.next;
}
return false;
}
@Override
public ListIterator<E> listIterator() {
ListIterator<E> iterator = new ListIterator<E>() {
int flag = 0;
boolean noNext = true;
int index = 0;
Node<E> current = head;
Node<E> returned = null;
@Override
public boolean hasNext() {
return index<size || current!=null;
}
@Override
public E next() {
if (!hasNext())
throw new UnsupportedOperationException();
returned = current;
current = current.next;
index++;
return returned.element;
}
@Override
public boolean hasPrevious() {
return index > 0;
}
@Override
public E previous() {
if (!hasPrevious())
throw new UnsupportedOperationException();
returned = current = current.previous;
index --;
return returned.element;
}
@Override
public int nextIndex() {
return index;
}
@Override
public int previousIndex() {
return index - 1;
}
@Override
public void remove() {
if (returned.next!=null)
returned.next.previous=returned.previous;
if (returned.previous!=null)
returned.previous.next=returned.next;
if (returned == current)
if (hasNext())
next();
else if (hasPrevious())
previous();
returned = null;
}
@Override
public void set(E e) {
current.element = e;
}
@Override
public void add(E e) {
Node<E> newNode = new Node(e);
newNode.next = current;
newNode.previous = current.previous;
flag = 0;
}
};
return iterator;
}
@Override
public ListIterator<E> listIterator(int index) {
ListIterator<E> iterator= listIterator();
for (int i = 0; i<index; i++)
iterator.next();
return iterator;
}
@Override
public int size() {
return size;
}
}
I didn't have myLinkList class, so I coded it the generic way. I hope you understand. If you want me to personalize your code, please send me the myLinkList class
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.