Exercises Unit 7.
Linked Lis
Exercise. Create the project LinkedList and add these classes, following the hierarchy.
We will use them later
public class LinkedListException extends Exception
LinkedListException()
super()
LinkedListException(String message)
super(message)
public class InvalidIndexException extends LinkedListException
InvalidIndexException()
super()
InvalidIndexException(String message)
super(message)
-1-
}
public class ObjectNotFoundException extends LinkedListException
ObjectNotFoundException()
super()
ObjectNotFoundException(String message)
super(message)
public class EmptyListException extends ObjectNotFoundException
EmptyListException()
super()
EmptyListException(String message)
super(message)
1.- Create the class LinkedList. It will represent a linked list of objects
You will need the class Element as well
The class Element will have the following elds: object and next. Where next is a pointer
to the next element of the list (null if it is the last element of the list). So, the type will be
Element
Methods in the Element class:
• public Element(Object newObject
• public void setNext(Element newNext
• public Element getNext(
• public Object getObject(
• public void setObject(Object newObject
• public void delete(): sets object and next to null
• otFoundException, EmptyListException: removes the object of the list
• public Object getFirstObject() throws EmptyListException: returns the rst object of the
list
• public Object getLastObject() throws EmptyListException: returns the last object of the
list
• public Object getObjectAtPosition(int i) throws EmptyListException,
InvalidIndexException: gets the object at that position in the list
-2-
}
fi
{
fi
The class LinkedList will have the following elds: rstElement, lastElement (pointers to
the rst and last elements of the list). So, the type will be Element
You will use the system of Exceptions you created in the previous exercise:
In LinkedList create the following methods
• public LinkedLis
• public void insertFirst(Object obj): inserts an object as the rst element of the lis
• public void insertLast(Object obj): inserts an object at the end of the lis
• public void print(): prints the list of element
• public boolean isEmpty(): returns true if the list is empt
• public void remove(Object obj) throws ObjectNotFoundException, EmptyListException:
removes the object of the list
• public Object getFirstObject() throws EmptyListException: returns the rst object of the
list
• public Object getLastObject() throws EmptyListException: returns the last object of the
list
• public Object getObjectAtPosition(int i) throws EmptyListException,
InvalidIndexException: gets the object at that position in the list
Test your class with a MainClass that creates a LinkedList and adds some Strings to the
beginning and the end of the list. Print the list, extract objects, print again, etc
public class Element
private Object object
private Element next
public Element(Object newObject)
object=newObject
next = null
public void setNext(Element newNext)
next=newNext
public Element getNext()
return next
public Object getObject()
return object
public void setObject(Object newObject)
object = newObject
public void delete()
object = null
next = null
-3-
}
fi
}
fi
{
fi
{
fi
.
fi
t
public class LinkedList
private Element rst
private Element last
public LinkedList()
rst = null
last = null
public void insertFirst(Object obj)
Element element = new Element(obj)
element.setNext( rst)
rst = element
if (last == null)
last = element
public void insertLast(Object obj)
Element element = new Element(obj)
element.setNext(null)
if (last != null
last.setNext(element)
last=element
if ( rst == null)
rst = element
public void print()
Element e = rst
while (e != null)
if (e != rst)
System.out.print(", ")
System.out.print(e.getObject())
e = e.getNext()
System.out.println()
public boolean isEmpty()
if ( rst == null
return true
else
return false
-4-
}
fi
fi
}
fi
fi
fi
}
fi
;
fi
;
fi
fi
;
public void remove(Object obj) throws ObjectNotFoundException,
EmptyListException
Element previous = rst
Element e = rst
if ( rst == null)
throw new EmptyListException()
while ((e != null) && (e.getObject() != obj))
previous = e
e = e.getNext()
if (e == null)
throw new ObjectNotFoundException();
if ( rst == last)
rst = null
last = null
} else
if ( rst == e)
rst = e.getNext()
if (last == e)
last = previous
previous.setNext(e.getNext())
e.delete()
public Object getLastObject() throws EmptyListException
if ( rst == null
throw new EmptyListException()
return last.getObject()
public Object getFirstObject() throws EmptyListException
if ( rst == null
throw new EmptyListException()
return rst.getObject()
-5-
}
fi
fi
fi
fi
{
fi
fi
}
fi
;
fi
fi
)
fi
;
public Object getObjectAtPosition(int i) throws EmptyListException,
InvalidIndexException
if ( rst == null)
throw new EmptyListException()
Element e = rst
int cont = 0
while ((e != null) && (cont < i))
e = e.getNext()
cont++
if ((cont == i) && (e != null))
return e.getObject()
} else
throw new InvalidIndexException()
public int getNumElements()
Element e = rst
int cont = 0
while (e != null)
e = e.getNext()
cont++
return cont
-6-
}
fi
{
fi
fi
;
public class MainClass
public static void main(String[] args)
LinkedList list = new LinkedList()
list.insertFirst("Uno")
list.insertFirst("dos")
list.insertFirst("tres")
list.print()
while (!list.isEmpty())
try
Object obj = list.getLastObject()
System.out.println(obj)
list.remove(obj)
} catch (EmptyListException ex)
System.out.println("Empty list")
} catch (ObjectNotFoundException e)
System.out.println("error")
-7-
}
-8-
