1) To class DoublyLinkedList , add method reverse which reverse the order of the
ID: 3740617 • Letter: 1
Question
1) To class DoublyLinkedList, add method reverse which reverse the order of the elements in the list.
2) Our implementation of a doubly list relies on two sentinel nodes, header and trailer. Reemployment
the DoublyLinkedList without using these nodes.
public class DoublyLinkedList <E>{
private Node<E> header;
private Node<E>trailer;
private int size=0;
public DoublyLinkedList()
{
header=new Node<>(null,null,null);
trailer=new Node<>(null,header, null);
header.setNext(trailer);
}
public int size() { return size;}
public boolean isEmpty(){ return size==0;}
public E first()
{
if (isEmpty()) return null;
return header.getNext().getElement();
}
public E last()
{
if (isEmpty()) return null;
return trailer.getPrev().getElement();
}
private void addBetween(E e, Node<E> predecessor,Node<E>successor)
{
Node<E> newest=new Node<>(e,predecessor, successor);
predecessor.setNext(newest);
successor.setPrev(newest);
size++;
}
private E remove(Node<E> e)
{
Node<E> predecessor=e.getPrev();
Node<E> successor=e.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return e.getElement();
}
public void addFirst(E e)
{
addBetween(e,header,header.getNext());
}
public void addLast(E e)
{
addBetween(e,trailer.getPrev(),trailer);
}
public E removeFirst()
{
if(isEmpty()) return null;
return remove(header.getNext());
}
public E removeLast()
{
if(isEmpty()) return null;
return remove(trailer.getPrev());
}
private static class Node<E>{
private E element;
private Node<E> next;
private Node<E> prev;
public Node(E e,Node<E> p, Node<E> n)
{
element=e;
prev=p;
next=n;
}
public E getElement(){ return element; }
public Node<E> getPrev() { return prev;}
public Node<E> getNext() { return next;}
public void setPrev(Node<E> n) {prev=n;}
public void setNext(Node<E> n) {next=n;}
}
}
Explanation / Answer
public class DoublyLinkedList <E>{
private Node<E> header;
private Node<E>trailer;
private int size=0;
public DoublyLinkedList()
{
header=new Node<>(null,null,null);
trailer=new Node<>(null,header, null);
header.setNext(trailer);
}
public int size() { return size;}
public boolean isEmpty(){ return size==0;}
public E first()
{
if (isEmpty()) return null;
return header.getNext().getElement();
}
public E last()
{
if (isEmpty()) return null;
return trailer.getPrev().getElement();
}
private void addBetween(E e, Node<E> predecessor,Node<E>successor)
{
Node<E> newest=new Node<>(e,predecessor, successor);
predecessor.setNext(newest);
successor.setPrev(newest);
size++;
}
private E remove(Node<E> e)
{
Node<E> predecessor=e.getPrev();
Node<E> successor=e.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return e.getElement();
}
public void addFirst(E e)
{
addBetween(e,header,header.getNext());
}
public void addLast(E e)
{
addBetween(e,trailer.getPrev(),trailer);
}
public E removeFirst()
{
if(isEmpty()) return null;
return remove(header.getNext());
}
public E removeLast()
{
if(isEmpty()) return null;
return remove(trailer.getPrev());
}
public void reverse()
{
// if list is not empty
if( this.header != null )
// update the trailer pointer
this.trailer = this.header;
// point trav to head of list
Node<E> trav = this.header;
Node<E> temp = null;
// traverse through the list
while( trav != null )
{
// point temp to previous node of trav
temp = trav.getPrev();
// update the previous pointer
trav.setPrev( trav.getNext() );
// update the next pointer
trav.setNext( temp );
trav = trav.getPrev();
}
// if temp is not null, means the list is empty
if( temp != null )
// update the header node
this.header = temp.getPrev();
}
private static class Node<E>{
private E element;
private Node<E> next;
private Node<E> prev;
public Node(E e,Node<E> p, Node<E> n)
{
element=e;
prev=p;
next=n;
}
public E getElement(){ return element; }
public Node<E> getPrev() { return prev;}
public Node<E> getNext() { return next;}
public void setPrev(Node<E> n) {prev=n;}
public void setNext(Node<E> n) {next=n;}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.