linkedlist.java

labs to practise link list and double link list

package myList;

public class LinkedList
{
	
// really simple, contains just one reference to head element	
	
Elem head;

LinkedList()	//simple constructor
 {
	System.out.println("constructing new LinkedList for book(Author & Title)");
	head=null;
 }

//*********************************************

public boolean emptyList()
 {
  return head == null;
 }

//*********************************************

public void setHead(Elem h)
 {
  head = h;
 }

//*********************************************

public Elem getHead()
 {
  return head;
 }

//*********************************************

public void insertFirst(Elem el)
 {
  el.setNext(head);
  head = el;
 }

//*********************************************

public Elem lastNode()
 {
  // returns last element of list, null if empty list	

  Elem l;
  if (emptyList()) return null;
  l = head;
  while (l.getNext() != null) l = l.getNext();
  return l;
 }

//*********************************************

public void insertLast(Elem l)
 {
  // for an empty list insertlast is insertfirst!
	
  if (emptyList()) 
   insertFirst(l);
  else		//define the next-reference of the last element
   lastNode().setNext(l);
 }

//*********************************************

public void removeFirst(Elem d)
 {
  //pre: list not empty!
  //post: first element removed and returned in d
	
  if (!emptyList())
  {
   d.setTitle(head.getTitle()); 
   d.setAuthor(head.getAuthor());
   d.setNext(head.getNext());
   head = head.getNext();
  }
  else System.out.println("removeFirst: Error: empty list!");
 }

//*********************************************

public void removeLast(Elem d)
 {
  //pre: list not empty!
  //post: last element removed and returned in d
		
  Elem l, l1;
  
  if (!emptyList())
  {l = head; l1 = l;
   if (l.getNext() == null)
    {
	 head = null;  
    }
   else
    {   
     while (l.getNext()!= null)
      {
	   l1 = l; l = l.getNext();	 
      }
     l1.setNext(null);
    }
    d.setTitle(l.getTitle());
    d.setAuthor(l.getAuthor());
    d.setNext(null);
  }
  else System.out.println("removeLast: Error: empty list!");
 }

//*********************************************

public LinkedList copyList()
 {
  //returns the copy of the list as theNewList	
	
  LinkedList theNewList;
  Elem copy, old;
  
  theNewList = new LinkedList(); // make a new list
  if (!emptyList())
  {
   copy = new Elem(); 
   theNewList.setHead(copy);	//define the new head	  
   old = head;	 
   copy.setTitle(old.getTitle()); //copy the title
   copy.setAuthor(old.getAuthor()); //copy the author
   while(old.getNext() != null)
   {
	copy.setNext(new Elem());	//there is another element to copy
								//next is set to null in the constructor!
	copy = copy.getNext();		//move to the next destination
	old = old.getNext();		//move to next source element
	copy.setTitle(old.getTitle());// copy the title
	copy.setAuthor(old.getAuthor());//copy the author
   }
  }
  return theNewList;
 }

//*********************************************

public LinkedList cons(Elem e)
{
 // creates a list out of an element and an old list
 // the tail of the new list is a refernce to the old list!!
	
 LinkedList l = new LinkedList();
 e.setNext(head);
 l.setHead(e);
 return l;
}

//*********************************************

public Elem first()
{
 //pre: list not empty
 //post: list unchanged head element returned	
 if (!emptyList()) System.out.println("First: Error: Empty List!!");
 return head;
}

//*********************************************

public LinkedList tail()
{
 //pre: list not empty
 //post: list unchanged, reference to tail returned
	
 LinkedList l;	
 if (emptyList()) 
 {System.out.println("Tail: Error: Empty List!!");
  return null; 
 }
 else 
 {
  l = new LinkedList();
  l.setHead(head.getNext());
  return l;
 }
}

//*********************************************

public boolean equalList(LinkedList l1)
{
 //two lists are equal if bothe are empty or
 //if both are not empty and they are elementwise the same
	
 if(emptyList() != l1.emptyList()) return false;
 else
  if (emptyList()) return true;	 
  else return (head.getTitle() == l1.getHead().getTitle()) && 
  			   head.getAuthor() == l1.getHead().getAuthor() &&
               tail().equalList(l1.tail());
}

//*********************************************

public long length()
{
 //returns the number of elements in the list
 //by counting them  during traversal
	
 long cnt = 0;
 Elem e = head;
 while (e != null)
 {
  cnt++; e = e.getNext();	 
 }
 return cnt;
}

//*********************************************

public Elem lookForTitle(String t)
{
 //pre: list not empty.
 //post: list unchanged, if found elent with matching key returned
 //                      if not found return null
	
 Elem l;	
 if (emptyList())
 {
  System.out.println("lookForTitle: Error: Empty List!!");
  return null;
 }
 else
 {
  l = head;
  while ((l != null) && (l.getTitle().equals(t) == false))
   l = l.getNext();
  if (l != null)	//found it
  return l;
  else				//too bad
  {
   System.out.println("lookForTitle Error: Title not found!!");
   return null;
  }
 }
}

public Elem lookForAuthor(String a)
{
	 //pre: list not empty.
	 //post: list unchanged, if found elent with matching key returned
	 //                      if not found return null
		
	 Elem l;	
	 if (emptyList())
	 {
	  System.out.println("lookForAuthor: Error: Empty List!!");
	  return null;
	 }
	 else
	 {
	  l = head;
	  while ((l != null) && (l.getAuthor().equals(a) == false))
	   l = l.getNext();
	  if (l != null)	//found it
	  return l;
	  else				//too bad
	  {
	   System.out.println("lookForAuthor Error: Title not found!!");
	   return null;
	  }
	 }
}
//*********************************************

public String toString()
 {
  String s = "";
  Elem e;
  e = head;
  while (e != null)
  {
   s = s + e; e = e.getNext();	  
  }
  return s;
 }
}