Topic 2
Array-Based Lists
Learning Outcomes
At the end of the class, students are able to List different types of List data structure Implement various List operations, such as search, insert, remove etc. design and implement a generic class to process various types of lists
Array-Based Lists
List: A collection of elements of the same type Length of list is number of elements in list
Class ArrayList (Java 2 SE 5.0)
java.util Class ArrayList - ArrayList( ) - add(int index, E element) - isEmpty() - size() - otherMethods( ).
4
Operations Performed on a List
Create the list: initialize to an empty state Determine whether the list is empty Determine whether the list is full Find the size of the list Destroy (clear) the list Determine whether an item is the same as a given list element
5
Operations Performed on a List
Insert an item in the list at the specified location Remove an item from the list at the specified location Replace an item at the specified location with another item Retrieve an item from the list at the specified location Search the list for a given item
6
Type of List Elements
(Malik, 2003)
class Object directly or indirectly becomes a superclass of every Java class, user defined or built in Reference variable of Object type can refer to any object of any class class DataElement, superclass of every class specifying data type of list elements Abstract methods of class DataElement: equals, compareTo, makeCopy, and getCopy
7
Type of List Elements
(Malik, 2003)
Type of List Elements
class IntElement used when list of integers is manipulated class DoubleElement used when list of decimal numbers is manipulated class StringElement, designed in chapter, used when list of strings is manipulated
class IntElement
(Malik, 2003)
10
class StringElement
(Malik, 2003)
11
class ArrayListClass
An abstract class Is superclass of the classes that implement a list Has three instance variables
length: specifies the number of elements currently in the list maxSize: specifies the maximum number of elements that can be processed by the list list: an array of reference variables
12
class ArrayListClass
13
Definitions of Nonabstract Methods of ArrayListClass
public boolean isEmpty() { return (length == 0); } public boolean isFull() { return (length == maxSize); } } } public int maxListSize() { return maxSize; public int listSize() { return length;
14
Definitions of Nonabstract Methods of ArrayListClass
public void print() { for(int i = 0; i < length; i++) System.out.print(list[i] + ); System.out.println(); }
public boolean isItemAtEqual(int location, DataElement item) { return (list[location].equals(item)); }
15
Definitions of Nonabstract Methods of ArrayListClass
public void insertAt(int location, DataElement insertItem) { if(location < 0 || location >= maxSize) System.err.println(The position of the item to + be inserted is out of range); else if(length >= maxSize) //list is full System.err.println(Cannot insert in a full list.); else { for(int i = length; i > location; i--) list[i] = list[i - 1]; //move the elements down list[location] = insertItem.getCopy(); //insert the //item at the specified position length++; //increment the length } }//end insertAt 16
Definitions of Nonabstract Methods of ArrayListClass
public void insertEnd(DataElement insertItem) { if(length >= maxSize) //the list is full System.err.println(Cannot insert in a full list.); else { list[length] = insertItem.getCopy(); //insert item //at end length++; } }//end insertEnd
17
//increment the length
Definitions of Nonabstract Methods of ArrayListClass
public void removeAt(int location) { if(location < 0 || location >= length) System.err.println(The location of the item to + be removed is out of range.); else { for(int i = location; i < length - 1; i++) list[i] = list[i + 1]; list[length - 1] = null; length--; } }//end removeAt
18
Definitions of Nonabstract Methods of ArrayListClass
public DataElement retrieveAt(int location) { if(location < 0 || location >= length) { System.err.println("The location of the item to be " + "retrieved is out of range."); return null; } else return list[location].getCopy(); }//end retrieveAt
19
Definitions of Nonabstract Methods of ArrayListClass
public void replaceAt(int location, DataElement repItem) { if(location < 0 || location >= length) System.err.println(The location of the item to + be replaced is out of range.); else list[location].makeCopy(repItem); }//end replaceAt public void clearList() { for(int i = 0; i < length; i++) list[i] = null; length = 0; System.gc(); }//end clearList 20
Definition of ArrayListClass
public abstract class ArrayListClass { protected int length; //to store the length //of the list protected int maxSize; //to store the maximum //size of the list protected DataElement[] list; //array to hold //list elements //Place the definitions of the instance // methods and abstract methods here.
21
Unordered List
class UnorderedArrayList is a subclass of the class ArrayListClass Elements are not necessarily sorted class UnorderedList implements operations search, insert, and remove
22
class UnorderedArrayList
23
Search
Necessary components to search a list:
Array containing the list Length of the list Item for which you are searching
After search completed:
If item found, report success, return location in array If item not found, report failure
24
Search
public int seqSearch(DataElement searchItem) { int loc; boolean found = false; for(loc = 0; loc < length; loc++) if(list[loc].equals(searchItem)) { found = true; break; } if(found) return loc; else return -1; }//end seqSearch
25
Insert and Remove
Insert
Inserts a new item in the list Uses method seqSearch to determine whether insertItem is already in list
Remove
deletes an item from the list uses the methods seqSearch and removeAt to remove an item from the list
26
Insert
public void insert(DataElement insertItem) { int loc; if(length == 0) //list is empty list[length++] = insertItem; //insert the item and //increment the length else if(length == maxSize) System.err.println(Cannot insert in a full list.); else { loc = seqSearch(insertItem); if(loc == -1) //the item to be inserted //does not exist in the list list[length++] = insertItem.getCopy(); else System.err.println(The item to be inserted is + already in the list. No + duplicates are allowed.); } }//end insert 27
Remove
public void remove(DataElement removeItem) { int loc; if(length == 0) System.err.println(Cannot delete from an empty list.); else { loc = seqSearch(removeItem); if(loc != -1) removeAt(loc); else System.out.println(The item to be deleted is + not in the list.); } }//end remove
28
Time Complexity of List Operations
29
Programming Example: Polynomials
Purpose: To design and implement the class Polynomial to perform various polynomial operations in a program Program implements the following polynomial operations: 1. Evaluate a polynomial at a given value 2. Add polynomials 3. Subtract polynomials 4. Multiply polynomials
30
Programming Example: Polynomials
31
Programming Example: Polynomials
32
Topic Summary
Operations performed on a list Type of list elements Abstract class DataElement Classes IntElement, DoubleElement, StringElement class ArrayListClass
Definitions of Nonabstract Methods of ArrayListClass Definition of ArrayListClass
33
Topic Summary
Unordered List Class UnorderedArrayList
Implementations of search, insert and remove
Time Complexity of List Operations Programming examples
34
