2Linked-list Implementation To accomplish a linked-list implementation, we need

Question

2Linked-list Implementation To accomplish a linked-list implementation, we need to extend how linked list nodes work. A normal linked list only allows for one direction of iteration. We're going to make it possible to iterate througlh a inked list in both directions by using a doubly-linked list (not to be confused with DoubleLinkedList, the singly-linked list of double-precision floating-point numbers that we implemented in lecture). A doubly-linked list has both a pointer to the next node as well as a pointer to the previous node, which is what allows for traversal of the linked list in either direction. Because of this, a doubly-linked list is considerably more powerful than a singly-linked list. To get you started, code for a doubly-linked ListNode is provided on the next page

Explanation / Answer

Given below are the implementations for the incomplete methods. Please copy-paste these in your LinkedDeque<T> class

public void addFirst(T element)
{
ListNode<T> newNode = new ListNode<T>();
newNode.setValue(element);

//link the new node to previous first node after header
newNode.setNext(header.getNext());
newNode.getNext().setPrevious(newNode);

//link header to new node
newNode.setPrevious(header);
header.setNext(newNode);
  
}

public T peekLast()
{
if(header.getNext() == footer) //no nodes
{
throw new EmptyQueueException();
}
  
ListNode<T> last = footer.getPrevious();
return last.getValue();
}

public T removeLast()
{
if(header.getNext() == footer) //no nodes
{
throw new EmptyQueueException();
}

ListNode<T> last = footer.getPrevious();
last.getPrevious().setNext(footer);
footer.setPrevious(last.getPrevious());
return last.getValue();
}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.