Question

In Java

In this lab we will creating two linked list classes: one that is a singly linked list, and another that is a doubly linked list ( This will be good practice for your next homework assignment where you will build your own string class using arrays and linked list ) .

These LinkedList classes should both be generic classes. and should contain the following methods:

• Print

• Add - Adds element to the end of the linked list.

• IsEmpty

• Push - Adds element to the beginning of the linked list

• InsertAt - Inserts an element at a given position

• Clear - Removes all elements from the linked list

• Contains - Returns true if element is in the linked list

• Get - Returns a value at a specific position

• IndexOf - Returns the first position where an element occurs, -1 if not

• LastOf - Returns the last position where an element occurs, -1 if not

• Remove - Removes the last item added to the list

• RemoveAt - Removes an element at a specific position

• RemoveElement - Removes the first occurrence of a specific element

• Size

• Slice - Returns a subset of this linked list given a beginning position start and end position stop.

You will also count the number of operations that is performed in each method and will calculate the RUN-TIME of each method, as well as calculating the BIG O, OMEGA and THETA notation of each method. This information should be written in a comment block before each method ( you may count the number of operations on each line if you want ).

You are required to write self commenting code for this Lab, refer to the Google Style Sheet if you haven't become familiar with it.

Answer 1

/////////////////////////////////////////////////////

public class SinglyLinkedList<T> {

   // inner class
public class Node<T>{
       private T item;// item
       private Node<T> next;// next link
      
       // constructor
       public Node(T data){
           this.setItem(data);
           this.setNext(null);
       }
      
       // getter and setter methods
       public Node<T> getNext() {
           return next;
       }
       public void setNext(Node<T> next) {
           this.next = next;
       }
       public T getItem() {
           return item;
       }
       public void setItem(T item) {
           this.item = item;
       }      
   }
  
  
   // root of the linkedlist
   private Node<T> root;
   // size of nodes
   private int size;
  
   // constructor
   public SinglyLinkedList(){
       this.root=null;
       this.size=0;
   }
  
   // add data at last
   public void Add(T item){
       // new object
       Node<T> node=new Node<T>(item);
       // set root
       if(this.root==null){
           this.root=node;
       }
       else{
           Node<T> cur=this.root;
           // get last node
           while(cur!=null){
               // last node found and set node at last
               if(cur.getNext()==null){
                   cur.setNext(node);
                   break;
               }
               cur=cur.getNext();
           }          
       }
       // increase size
       this.size++;
   }
  
   // add node at first
   public void Push(T item){
       Node<T> node=new Node<T>(item);
       node.setNext(root);
       this.root=node;
       this.size++;
   }
  
   // insert at position
   public void InsertAt(int i,T item){
       // create object
       Node<T> node=new Node<T>(item);
       int ind=0;
       Node<T> cur=this.root;
       Node<T> pre=null;
      
       //if index found
       while(cur!=null){
           if(ind==i){
               break;
           }
           ind++;
           pre=cur;
           cur=cur.getNext();
       }  
       // if index found in between 0 and size-1
       if(pre!=null){
           node.setNext(cur);
           pre.setNext(node);
       }
       // add at first
       else{
           node.setNext(root);
           root=node;
       }
       this.size++;
   }
   public void Clear(){
       this.root=null;
   }
  
   public boolean Contains(T item){
       Node<T> cur=this.root;
       while(cur!=null){
           if(cur.getItem()==item){
               return true;
           }
           cur=cur.getNext();
       }  
       return false;
   }
  
   public T Get(int i){
       int index=0;
       if(i<this.size){
           Node<T> cur=this.root;
           // find index position
          
           while(cur!=null){
               // if found return item
               if(index==i){
                   return cur.getItem();
               }
               index++;
               cur=cur.getNext();
           }
       }
       // otherwise return null  
       return null;
   }
  
   //
   public int IndexOf(T item){
       int index=0;
       Node<T> cur=this.root;
       while(cur!=null){
           // if first index found
           // return index
           if(item==cur.getItem()){
               return index;
           }
           index++;
           cur=cur.getNext();
       }
       return -1;
   }
   public int LastOf(T item){
       int index=0;
       int i=-1;
       Node<T> cur=this.root;
       while(cur!=null){
           // finding position index from 0
           if(item==cur.getItem()){
               i=index;              
           }
           index++;
           cur=cur.getNext();
       }
       // if last index exist
       // change it to last index
       if(i!=-1){
           i=this.size-1-i;
       }
       return i;
   }
   public T Remove(){
       if(this.size>0){
           Node<T> cur=this.root;
           Node<T> pre=null;
           // go in last
           while(cur.getNext()!=null){
               pre=cur;
               cur=cur.getNext();
           }
           // get last data
           T item=cur.getItem();
           // set next link of just previous of last link
           pre.setItem(null);
           this.size--;
           return item;
       }
       return null;
   }
  
  
   public T RemoveAt(int i){
       if(this.size>0){
           Node<T> cur=this.root;
           Node<T> pre=null;
           int ind=0;
           while(cur!=null){
               // if index found
               // break and get current link
               if(i==ind){
                   break;
               }
               ind++;
               pre=cur;
               cur=cur.getNext();
           }
          
           T item=null;
           // set link between previous and next link
           if(pre==null){
               item=this.root.getItem();
               this.root=this.root.getNext();              
           }
           else{
               item=cur.getItem();
               pre.setNext(cur.getNext());
           }
           this.size--;
           return item;
       }
       return null;
   }
   // remove at first
   public T RemoveElement(){
       T item=this.root.getItem();
       this.root=this.root.getNext();
       this.size--;
       return item;
   }
   public SinglyLinkedList<T> Slice(int a,int b){
       // create new singly linked list
       SinglyLinkedList<T> sl=new SinglyLinkedList<T>();
       int i=0;
       Node<T> cur=this.root;
       // if index exist between them , add them in newly created object
       while(cur!=null){
           if(a<=i && i<=b){
               sl.Add(cur.getItem());
           }
           i++;
           cur=cur.getNext();
       }
       return sl;
   }
   public int getSize(){
       return this.size;
   }

}

////////////////////////////////////////////////////////////////////////

public class DoublyLinkedList<T> {
   // inner class
   public class Node<T>{
       private T item;// item
       private Node<T> next;// next link
       private Node<T> pre;// previous link
// constructor
       public Node(T data){
           this.setItem(data);
           this.setNext(null);
           this.setPrevious(pre);
       }
// getter and setter methods
       public Node<T> getNext() {
           return next;
       }
       public void setNext(Node<T> next) {
           this.next = next;
       }
       public Node<T> getPrevious() {
           return pre;
       }
       public void setPrevious(Node<T> pre) {
           this.pre = pre;
       }
       public T getItem() {
           return item;
       }
       public void setItem(T item) {
           this.item = item;
       }      
   }
  
  
   // root of the linkedlist
   private Node<T> root;
// last link of the linkedlist
   private Node<T> last;
// size of nodes
   private int size;
       // constructor
   public DoublyLinkedList(){
       this.root=null;
       this.last=null;
       this.size=0;
   }
  
   // add data at last
   public void Add(T item){
// new object
       Node<T> node=new Node<T>(item);
// set root
       if(this.root==null){
           this.root=node;
           this.last=node;
       }
// set node at last
       else{
           node.setPrevious(last);
           last.setNext(node);
           last=node;
       }
       this.size++;
   }
// add node at first
   public void Push(T item){
       Node<T> node=new Node<T>(item);
// set root
       if(this.root==null){
           this.root=node;
           this.last=node;
       }
// set node at first
       else{
           node.setNext(root);
           this.root.setPrevious(node);      
           this.root=node;
       }
// set root      
       this.size++;
   }

// insert at position
   public void InsertAt(int i,T item){
// create object
       Node<T> node=new Node<T>(item);
       int ind=0;
       Node<T> cur=this.root;
       Node<T> pre=null;
   //if index found
       while(cur!=null){
           if(ind==i){
               break;
           }
           ind++;
           pre=cur;
           cur=cur.getNext();
       }  
// if index found in between 0 and size-1
       if(pre!=null){
           node.setNext(cur);
           node.setPrevious(pre);
           cur.setPrevious(node);
           pre.setNext(node);
       }
// add at first
       else{
           this.Push(item);  
       }
       this.size++;
   }
   public void Clear(){
       this.root=null;
   }
   public boolean Contains(T item){
       Node<T> cur=this.root;
       while(cur!=null){
           if(cur.getItem()==item){
               return true;
           }
           cur=cur.getNext();
       }  
       return false;
   }
   public T Get(int i){
       int index=0;
       if(i<this.size){
           Node<T> cur=this.root;

// find index position
           while(cur!=null){
// if found , return item
               if(index==i){
                   return cur.getItem();
               }
               index++;
               cur=cur.getNext();
           }
       }
       // otherwise return null      
       return null;
   }
   public int IndexOf(T item){
       int index=0;
       Node<T> cur=this.root;
       while(cur!=null){
// if first index found
           // return index
           if(item==cur.getItem()){
               return index;
           }
           index++;
           cur=cur.getNext();
       }
       return -1;
   }
   public int LastOf(T item){
       int index=0;
       int i=-1;
       Node<T> cur=this.last;
       while(cur!=null){
// if first index found from last
           // return index
           if(item==cur.getItem()){
               i=index;
               break;
           }
           index++;
           cur=cur.getPrevious();
       }
       return i;
   }
   public T Remove(){
       if(this.size>0){
// get last data
// set previous of last link as last
           T item=last.getItem();
           last=last.getPrevious();
           size--;
           return item;
       }
       return null;
   }
   public T RemoveAt(int i){
       if(this.size>0){
           Node<T> cur=this.root;
           Node<T> pre=null;
           int ind=0;
           while(cur!=null){

               // if index found
               // break and get current link
               if(i==ind){
                   break;
               }
               ind++;
               pre=cur;
               cur=cur.getNext();
           }
          
           T item=null;
// set link between previous and next link
           if(pre==null){
               item=this.root.getItem();
               this.root=this.root.getNext();              
           }
           else{
               item=cur.getItem();
               pre.setNext(cur.getNext());
           }
           this.size--;
           return item;
       }
       return null;
   }
// remove at first
   public T RemoveElement(){
       T item=this.root.getItem();
       this.root=this.root.getNext();
       size--;
       return item;
   }
   public DoublyLinkedList<T> Slice(int a,int b){
// create new doubly linked list
       DoublyLinkedList<T> sl=new DoublyLinkedList<T>();
       int i=0;
       Node<T> cur=this.root;
// if index exist between them , add them in newly created object
       while(cur!=null){
           if(a<=i && i<=b){
               sl.Add(cur.getItem());
           }
           i++;
           cur=cur.getNext();
       }
       return sl;
   }
   public int getSize(){
       return this.size;
   }

}

/////////////////////////////////////////////////////////////

import java.util.Random;
import java.util.Scanner;

public class Driver {
   public static void main(String [] args){
       // create 2 object
       // for singlylinkedlist
       SinglyLinkedList<Integer> sll=new SinglyLinkedList<Integer>();
       // for doublylinkedlist
       DoublyLinkedList<Integer> dll=new DoublyLinkedList<Integer>();
      
       // for user input
       Scanner sc=new Scanner(System.in);
       // for random choose
       Random rand=new Random();
      
       // insert 14 elements
       for(int i=0;i<14;i++){
           System.out.print("Enter element: ");
           int value=sc.nextInt();
          
           // randomly add last
           if(rand.nextInt(2)%2==0){
               System.out.println("Data added last.");
               sll.Add(value);
               dll.Add(value);
           }
           // randomly add first
           else{
               System.out.println("Data added first.");
               sll.Push(value);
               dll.Push(value);
           }
       }
      
       // print list
       System.out.print("\nSinglyLinkedList : ");
       for(int i=0;i<sll.getSize();i++){
           System.out.print(sll.Get(i)+" ");
       }
       System.out.print("\nDoublyLinkedList : ");
       for(int i=0;i<dll.getSize();i++){
           System.out.print(dll.Get(i)+" ");
       }
      
       // insert at index 4 and 9 from first
       sll.InsertAt(5, 40);
       sll.InsertAt(9, 60);
       dll.InsertAt(5, 40);
       dll.InsertAt(9, 60);
      
       // print them
       System.out.print("\n\n40 inserted at index 5 and 60 inserted at index 9 \n");
       System.out.print("\nSinglyLinkedList : ");
       for(int i=0;i<sll.getSize();i++){
           System.out.print(sll.Get(i)+" ");
       }
       System.out.print("\nDoublyLinkedList : ");
       for(int i=0;i<dll.getSize();i++){
           System.out.print(dll.Get(i)+" ");
       }
      
       // get index
       System.out.print("\nFirst index of 40 [SinglyLinkedList]: "+sll.IndexOf(40));
       System.out.print("\nLast index of 60 [SinglyLinkedList]: "+sll.LastOf(60));
      
       System.out.print("\nFirst index of 40 [DoublyLinkedList]: "+dll.IndexOf(40));
       System.out.print("\nLast index of 60 [DoublyLinkedList]: "+dll.LastOf(60));      
      
       // remove 2 elements from last and first
       sll.Remove();
       sll.Remove();
       sll.RemoveElement();
       sll.RemoveElement();
      
       dll.Remove();
       dll.Remove();
       dll.RemoveElement();
       dll.RemoveElement();
      
       // display
       System.out.print("\n\nRemove first 2 elements and last 2 elements\n");
       System.out.print("\nSinglyLinkedList : ");
       for(int i=0;i<sll.getSize();i++){
           System.out.print(sll.Get(i)+" ");
       }
       System.out.print("\nDoublyLinkedList : ");
       for(int i=0;i<dll.getSize();i++){
           System.out.print(dll.Get(i)+" ");
       }
      

       // remove at index 4 and 7
       sll.RemoveAt(4);
       sll.RemoveAt(7);
       dll.RemoveAt(4);
       dll.RemoveAt(7);
      
       // display
       System.out.print("\n\nRemove at index 4 and 7\n");
       System.out.print("\nSinglyLinkedList : ");
       for(int i=0;i<sll.getSize();i++){
           System.out.print(sll.Get(i)+" ");
       }
       System.out.print("\nDoublyLinkedList : ");
       for(int i=0;i<dll.getSize();i++){
           System.out.print(dll.Get(i)+" ");
       }
      
       // slice them 1 to 5
       SinglyLinkedList<Integer> sll1=sll.Slice(1, 5);
       DoublyLinkedList<Integer> dll1=dll.Slice(1, 5);
      

       // print them
       System.out.print("\n\nSlicing 1 to 5\n");
       System.out.print("\nSinglyLinkedList : ");
       for(int i=0;i<sll1.getSize();i++){
           System.out.print(sll1.Get(i)+" ");
       }
       System.out.print("\nDoublyLinkedList : ");
       for(int i=0;i<dll1.getSize();i++){
           System.out.print(dll1.Get(i)+" ");
       }
      
   }
}