COS 111, Fall 1997

Implementing linked lists in Java

This is the Java we looked at in class to implement linked lists.
Disclaimer: This is not complete Java code. Furthermore, the Java has not been compiled and tested. Therefore, while conceptually correct, it could contain small errors.

node -- the class that defines the type of each item in a list

class node
 { private int data;                          //data for the item
   private node next;                        //identifies next item in the list

   public node (int value, node nextItem)    //constructor
    { data = value;
      next = nextItem;
    }

   public int getData()                     //method to get the data in an item
    { return data;}

   public node getNext()              //method to get the id. for the next item
    { return next;}

   public void changeNext(node newNext)  //method to change what is the next item
    { next = newNext;}
  }                                     //end of definition of class node

LinkedList -- the class that defines the type of each list.

 { private node first;                      //identifies the first (front) item
   private node last;                       //identifies the last (back) item

   public LinkedList ()                  //constructor -- constructs empty list
    { first = null;
      last = null;
    }

   public void insertFront(int data)   //method to insert item at front of list
    { if (first == null)               //if list initially empty
         {  first = new node (data, null);
            last = first;
         }
      else                             //if list initially contains item
         {  first = new node (data, first); 
         }
     }      


   public int removeFront()       //method to remove an item from front of list
                                          // returns the data value of the item
    { if (first != null)                  // if list is not empty
         {  int temp;                    // used to hold the data temporarily
            temp = first.getData;
            if (first == last)                // if only one item in list
                  { first = null;
                    last = null;
                  }
            else  {                          // if more than one item in list
                    first = first.getNext;
                  }
            return temp;
          }
       else                              //if list IS empty
         {
            ?                            //what can we do?
          }
    }


   public boolean emtpyTest()           //test if list empty
    { if (first == null)
         {return true;}
      else {return false;}


   public void insertBack(int data)     //method to insert item at back of list
     {
      HOMEWORK
     }


   public int removeBACK()       //method to remove an item from back of list
                                 // returns the data value of the item
     {
      LITTLE TRICKIER -- DISCUSSED SOME IN CLASS.  YOU CAN TRY FOR FUN.
      NOT HOMEWORK!
     }



  }                                     //end of definition of class LinkedList