dsa

Data Structures & Algorithms - Spring 2018
Log | Files | Refs | README

ListCDLSBased.java (4099B)

      1 package lab4;
      2 
      3 // Please note that this code is slightly different from the textbook code
      4 //to reflect the fact that the Node class is implemented using data encapsulation
      5 
      6 // ****************************************************
      7 // Reference-based implementation of ADT list.
      8 // ****************************************************
      9 public class ListCDLSBased implements ListInterface
     10 {
     11     // reference to linked list of items
     12     private DNode head;
     13     private int numItems; // number of items in list
     14 
     15     public ListCDLSBased()
     16     {
     17         numItems = 0;
     18         head = null;
     19     }  // end default constructor
     20 
     21     public boolean isEmpty()
     22     {
     23         return numItems == 0;
     24     }  // end isEmpty
     25 
     26     public int size()
     27     {
     28         return numItems;
     29     }  // end size
     30 
     31 
     32     private DNode find(int index)
     33     {
     34         DNode curr = head;
     35         if (index > numItems / 2) {
     36             int findIndex = numItems - index;
     37             for (int i = findIndex; i > 0; i--) {
     38                 curr = curr.getBack();
     39             }
     40             return curr;
     41         }
     42         else {
     43             for (int i = index; i > 0; i--) {
     44                 curr = curr.getNext();
     45             }
     46             return curr;
     47         }
     48     }
     49 
     50     public Object get(int index)
     51             throws ListIndexOutOfBoundsException
     52     {
     53         if (index >= 0 && index < numItems)
     54         {
     55             // get reference to node, then data in node
     56             DNode curr = find(index);
     57             Object dataItem = curr.getItem();
     58             return dataItem;
     59         }
     60         else
     61         {
     62             throw new ListIndexOutOfBoundsException(
     63                     "List index out of bounds exception on get");
     64         } // end if
     65     } // end get
     66 
     67     public void add(int index, Object item)
     68             throws ListIndexOutOfBoundsException {
     69         if (index >= 0 && index < numItems + 1) {
     70             if (head == null) {
     71                 DNode newNode = new DNode(item);
     72                 head = newNode;
     73             }
     74             else {
     75                 DNode curr;
     76                 if (index == numItems || index == 0) {
     77                     curr = head;
     78                 }
     79                 else {
     80                     curr = find(index);
     81                 }
     82                 DNode newNode = new DNode(item, curr, curr.getBack());
     83                 curr.getBack().setNext(newNode);
     84                 curr.setBack(newNode);
     85                 if (index == 0) {
     86                     head = newNode;
     87                 }
     88             }
     89             numItems++;
     90         }
     91         else {
     92             throw new ListIndexOutOfBoundsException(
     93                     "List index out of bounds exception on add");
     94         } // end if
     95     }  // end add
     96 
     97     public void remove(int index)
     98             throws ListIndexOutOfBoundsException
     99     {
    100         if (index >= 0 && index <= numItems)
    101         {
    102             DNode prev;
    103             if (index == 0) {
    104                 prev = head.getBack();
    105             }
    106             else {
    107                 prev = find(index - 1);
    108             }
    109             prev.getNext().getNext().setBack(prev);
    110             prev.setNext(prev.getNext().getNext());
    111             if(index == 0) {
    112                 head = prev.getNext();
    113             }
    114             numItems--;
    115         }
    116         else
    117         {
    118             throw new ListIndexOutOfBoundsException(
    119                     "List index out of bounds exception on remove");
    120         }
    121     }
    122 
    123     public void removeAll()
    124     {
    125         // setting head to null causes list to be
    126         // unreachable and thus marked for garbage
    127         // collection
    128         head = null;
    129         numItems = 0;
    130     } // end removeAll
    131 
    132     @Override
    133     public String toString() {
    134         Object dataItem;
    135         DNode curr = head;
    136         String result = "List of size " + size() + " has the following items : ";
    137         for (int i = 0; i < size(); i++) {
    138             if (curr != null) {
    139                 dataItem = curr.getItem().toString();
    140                 curr = curr.getNext();
    141                 result += dataItem + " ";
    142             }
    143         }
    144         return result;
    145     }
    146 
    147 
    148 } // end ListReferenceBased
    149