Asymptotic Analysis Part I: Reversing a List In this lab, you will adding a sing

Question

Asymptotic Analysis

Part I: Reversing a List

In this lab, you will adding a single method to DoublyLinkedList: reverse(). When called, reverse() should reverse the order of nodes in the list. You may use any methods we've implemented in class to accomplish this.

Note: You must reverse this list in-place. That means you may not change node.value; you may only change node.prev and node.next.

When you are finished, add a Driver class with a main method which tests this method.

Part II: Algorithm Analysis

Analyze your algorithm using Big-Oh notation. Assuming the list contains n elements, what is its worst-case running time? Answer in a comment in the main method of your Driver class.

Part III: Problem Analysis

Is your algorithm asymptotically optimal? That is, is it possible to write a function that does better in the worst case? Answer in a comment in the main method of your Driver class.

Code for Doubly Linked List:

public class DoublyLinkedList<E>
{
   private Node<E> header;
   private Node<E> trailer;
   private int size;
  
   public DoublyLinkedList()
   {
       header = new Node<>(null, null, null);
       trailer = new Node<>(null, null, header);
       header.next = trailer;
       size = 0;
   }
  

   private void insertBetween(E v, Node<E> first, Node<E> second)
   {
       Node<E> newNode = new Node<>(v, second, first);
       second.prev = newNode;
       first.next = newNode;
       size++;
   }

   private E removeBetween(Node<E> first, Node<E> second) throws IllegalStateException
   {
       if(header.next == trailer) //if(size == 0)
       {
           throw new IllegalStateException("Cannot delete from empty list");
       }
       E valueToReturn = first.next.value;
              
       first.next = second;
       second.prev = first;
       size--;
      
       return valueToReturn;
   }
   public void insertAtHead(E v)
   {
       insertBetween(v, header, header.next);
   }
  
   public void insertAtTail(E v)
   {
       insertBetween(v, trailer.prev, trailer);
   }
  
   public E removeHead() throws IllegalStateException
   {
       return removeBetween(header, header.next);
   }
  
   public E removeTail() throws IllegalStateException
   {
       return removeBetween(trailer.prev, trailer);
   }
  
   public String toString()
   {
       if(size == 0)
       {
           return "list is empty!";
       }
       String r = "";
       Node<E> temp = header.next;
       while(temp != trailer)
       {
           r += temp.toString() + " ";
           temp = temp.next;
       }
       return r;
   }
  
   public void printBackward()
   {
       if(size == 0)
       {
           System.out.println("list is empty!");
       }
      
       Node<E> temp = trailer.prev;
       while(temp != header)
       {
           System.out.print(temp + " ");
           temp = temp.prev;
       }
       System.out.println();

   }
  
   private static class Node<T>
   {
       private T value;
       private Node<T> next;
       private Node<T> prev;
      
       public Node(T v, Node<T> n, Node<T> p)
       {
           value = v;
           next = n;
           prev = p;
       }
      
       public String toString()
       {
           return value.toString();
       }
   }

}

Explanation / Answer

Hi Dear,

Please find my implementation.

############

Output:

11 10 9 8 7 6 5 4
4 5 6 7 8 9 10 11

Process finished with exit code 0

Time Complexity of reverse() method is O(N) because we are trversing linked list onece to reverse it

Please DONT forgot to rate my answer. We are working hard for you Guys!!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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