package dataStructures; /** * Class OrderedLinkedList. * * This class functions

Question

package dataStructures;

/**
* Class OrderedLinkedList.
*
* This class functions as a linked list, but ensures items are stored in ascending order.
*
*/
public class OrderedLinkedList
{

/**************************************************************************
* Constants
*************************************************************************/

/** return value for unsuccessful searches */
private static final OrderedListNode NOT_FOUND = null;

/**************************************************************************
* Attributes
*************************************************************************/

/** current number of items in list */
private int theSize;

/** reference to list header node */
private OrderedListNode head;

/** reference to list tail node */
private OrderedListNode tail;

/** current number of modifications to list */
private int modCount;


/**************************************************************************
* Constructors
*************************************************************************/

/**
* Create an instance of OrderedLinkedList.
*
*/
public OrderedLinkedList()
{
  // empty this OrderedLinkedList
  clear();
}


/**************************************************************************
* Methods
*************************************************************************/

/*
* Add the specified item to this OrderedLinkedList.
*
* @param obj  the item to be added
*/
public boolean add(Comparable obj)
{
  // TODO: Implement this method (8 points)
}

/*
* Remove the first occurrence of the specified item from this OrderedLinkedList.
*
* @param obj  the item to be removed
*/
public boolean remove(Comparable obj)
{
  // TODO: implement this method (7 points)
}

/**
* Empty this OrderedLinkedList.
*/
public void clear()
{
  // reset header node
  head = new OrderedListNode("HEAD", null, null);
  
  // reset tail node
        tail = new OrderedListNode("TAIL", head, null);
       
        // header references tail in an empty LinkedList
        head.next = tail;
       
        // reset size to 0
  theSize = 0;
  
  // emptying list counts as a modification
  modCount++;
}

/**
* Return true if this OrderedLinkedList contains 0 items.
*/
public boolean isEmpty()
{
  return theSize == 0;
}

/**
* Return the number of items in this OrderedLinkedList.
*/
public int size()
{
  return theSize;
}

/*
* Return a String representation of this OrderedLinkedList.
*
* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString()
    {
    String s = "";
   
    OrderedListNode currentNode = head.next;
   
    while (currentNode != tail)
    {
      s += currentNode.theItem.toString();
      
      if (currentNode.next != tail)
      {
       s += ", ";
      }
      
      currentNode = currentNode.next;
    }
   
    return s;
    }

/**************************************************************************
* Inner Classes
*************************************************************************/

/**
* Nested class OrderedListNode.
*
* Encapsulates the fundamental building block of an OrderedLinkedList
* contains a data item, and references to both the next and previous nodes
* in the list
*/


// TODO: Implement the nested class OrderedListNode (5 points). This nested class
// should be similar to the nested class ListNode of the class LinkedList, but
// should store a data item of type Comparable rather than Object.
}

Explanation / Answer

package dataStructures;

public class OrderedLinkedList
{
private static final OrderedListNode NOT_FOUND = null;

private int theSize;
private OrderedListNode head;
private OrderedListNode tail;
private int modCount;

public OrderedLinkedList()
{
  clear();
}

public boolean add(Comparable obj)
{
  OrderedListNode node = new OrderedListNode(obj);

  if(head.next == tail)
  {
   head.next = node;
   node.next = tail;
   tail.prev = node;
   return true;
  }

  if(obj.compareTo(head.next.theItem) < 0)
  {
   node.next = head.next;
   head.next = node;
   return true;
  }

  OrderedListNode current = head.next;
  OrderedListNode previous = head;
  while(current != tail && (node.theItem).compareTo(current.theItem) >= 0)
  {
   previous = current;
   current = current.next;
  }

  previous.next = node;
  node.next = current;

  return true;
}

public boolean remove(Comparable obj)
{
  OrderedListNode prev = null;
  OrderedListNode curr = head;
  
  
  while(curr != null &&
(obj.compareTo(curr.theItem) > 0))
  {
   prev = curr;
   curr = curr.next;
  }
  
  
  if(curr != null &&
(obj.compareTo(curr.theItem) == 0))
  {
   
   if(prev == null)
    head = head.next;
   else
    prev.next = curr.next;
   theSize--;
   
   return true;
  }
  else
   return false;

}

public void clear()
{
  head = new OrderedListNode("HEAD", null, null);

  tail = new OrderedListNode("TAIL", head, null);

  head.next = tail;

  theSize = 0;

  modCount++;
}

public boolean isEmpty()
{
  return theSize == 0;
}

public int size()
{
  return theSize;
}

public String toString()
{
  String s = "";

  OrderedListNode currentNode = head.next;

  while(currentNode != tail)
  {
   s += currentNode.theItem.toString();

   if(currentNode.next != tail)
   {
    s += ", ";
   }

   currentNode = currentNode.next;
  }

  return s;
}

public static class OrderedListNode
{

  Comparable theItem;
  OrderedListNode next;
  OrderedListNode prev;

  OrderedListNode(Comparable theItem)
  {
   this(theItem, null, null);
  }

  OrderedListNode(Comparable theItem, OrderedListNode prev,
    OrderedListNode next)
  {
   this.theItem = theItem;
   this.next = next;
   this.prev = prev;
  }

  Comparable getData()
  {
   return theItem;
  }

  OrderedListNode getNext()
  {
   return next;
  }

  OrderedListNode getPrev()
  {
   return prev;
  }

}

public static void main(String[] args)
{
  OrderedLinkedList list = new OrderedLinkedList();
  list.add("3");
  list.add("5");
  list.add("2");
  list.add("4");
  list.add("1");
  System.out.println(list);
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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