Transcript Data Structures

Data structures
Abstract data types
Java classes for Data structures and
ADTs
Data structures


"Any method of organising a collection of
data to allow it to be manipulated
effectively…."
"Examples data structures are: array,
dictionary, graph, hash, heap, linked list,
matrix, object, queue, ring, stack, tree,
vector"
Imperial College Free Online Dictionary of Computing,
http://foldoc.doc.ic.ac.uk/foldoc/index.html
Data structures

so far we have used the array data structure


simple way of storing related elements of same type
occupies fixed contiguous space in memory



the array elements are next to each other
elements are accessed by their index
type and length is fixed when array is created
myArray =
3
6
3
1
6
3
4
1
0
1
2
3
4
5
6
7
Abstract data types


we also looked at how to use an array to model a list
we call a list an abstract data type

it has defined operations





etc.
it can be implemented in different ways


add to the end of the list
find an item in the list
delete an item from the list
array, piece of paper, tree, linked list
the operations have the same effect no matter how the list is
implemented
other examples of abstract data types

set, queue, stack, map
Sets

a set is an unordered
group of elements



duplicates are not
allowed
otherwise how would
you tell them apart?
the set of "foods I like"
contains the elements

cereal, chicken, chips,
tomato soup, orange
juice and chocolate
set of foods I like
Chips
Cereal
Chicken
Orange Tomato
juice
soup
Chocolate
Lists

a list is a group of elements arranged
in some order

so we can talk about




the order could be meaningful





the first element in the list
the last element in the list
element 3
alphabetical
by size
by time
or it could simply be the order the
elements were added
duplicates are allowed

they are distinguished by their position
Things I ate today
(in chronological order)
1. cereal
2. orange juice
3. chocolate
4. tomato soup
5. chocolate
6. chicken
7. chips
8. chocolate
Queue



a queue is a a group of items arranged in order of arrival
new items can only be added to the back of the queue
items can only be removed from the front of the queue




shoppers at supermarket check-out
taxis in rank
computer processes awaiting execution
first-in, first-out (FIFO)
Stacks



a stack is a group of items
arranged in order
new items can only be added to
the top of the stack
items can only be removed from
the top of the stack




stack of chairs or books
plates in cafeteria
temporary data storage in CPU
last in, first out (LIFO)
Maps

A map is a collection of
key/element pairs



each element is stored in a
position determined by its key
can look up an element using
algorithm
its key
confusion
also known as a dictionary


key is the word
element is the definition
university
Implementing ADTs

the abstract parts of abstract data type refers to the fact
that we can implement them in different ways


but their definition remains unchanged
we have already seen how to implement a list using an
array

how could a


queue (first in, first out)
stack (last in, first out)
be implemented using an array?
next =
myArray =
3
6
3
1
0
1
2
3
4
5
4
6
7
Disadvantages of arrays

arrays occupy contiguous space in memory

the array size has to be specified when it is created



so the processor can allocate the right amount of memory space
it can't be changed if more (or less) space is required
awkward when inserting into or deleting from the
middle of an array

all the other elements have to shuffled along
Linked lists


a more flexible way to store elements in order
for each element, store


its data
where to find the next element



a pointer or reference or address or link
elements do not need to be stored next to each other
list can grow or shrink as required

last element links to special value null indicating end
Linked lists

a linked list consists of a chain of nodes
h
sarah





adam
jim
this list has four nodes
each node has


tim
a data element (a name)
a link to the next node (arrow)
we can access the elements in turn by following
the links in the chain
elements can be added by splicing in new nodes
elements can be deleted by bypassing nodes
Data structures in Java



Java provides many classes to implement data
structures and ADTs
called Collections as they are used to collect
together related items
in package java.util


need to import to use
HashSet, Vector, ArrayList,
LinkedList, Stack, HashMap
HashSet class


implements a set
has methods to add and remove elements



add(Object o)
remove(Object o)
and a method to check if an object is a member
of the set

boolean contains(Object o)
Vector and
ArrayList classes

the Java Vector and ArrayList classes have similar
functionality


both model a list
both have methods to


add an element to the next available position
add an element in a given position

other elements will be shuffled along to make room



return an element, given its index
delete a given element, or the element at a given index


you don't need to write the code!
again the shuffling is done for you
return the first element or the last element
Vector and
ArrayList classes

these classes are implemented using an array


when the array is full, the elements are
automatically copied over to a larger array
we don't interact with the array directly



instead we use the public methods of the class
Vector was implemented first
ArrayList is the later version
LinkedList class

models a list


underlying data structure is a linked list



like Vector and ArrayList
more efficient for adding and deleting elements, and
changing size
less efficient for accessing elements by their index
has methods to model a queue


offer(Object o) adds an element to the end of
the queue
remove() removes the element as the head of the
queue
Stack class

a subclass of Vector that models a stack



so uses an array as the underlying data structure
push(Object o) pushes an element onto
the top of the stack
pop() removes and returns the top element
of the stack
HashMap class




HashMap models a map
when elements put into the map their key must be
specified

put(Object key, Object element)

the key must be an object

not a primitive type such as int

often Strings are used as keys
get(Object key) returns the object corresponding to
key
the mapping works by


generating a hashcode from the key
storing the element at a position indicated by the hashcode
The Iterator Interface

often need to access each element in a
Collection in turn


print the details of all students enrolled in a School
the Iterator interface in java.util allows
us to do this


first create an Iterator object
then use the Iterator next()method to obtain
the next object in the collection

while the Iterator hasNext() method returns true
The Iterator Interface
Vector studentList;
studentList = new Vector();
// code omitted to fill up student list
Iterator it = studentList.iterator();
while ( it.hasNext())
{
// retrieve and cast the next Student
Student s = (Student)it.next();
s.printDetails();
}


can create an Iterator from HashSet, Vector, ArrayList,
LinkedList, Stack collections
can create an Iterator indirectly from a HashMap

use values() method to first generate a collection from the map
Using Java collections

these collections can hold objects of any type

but not primitive types such as int



need to wrap in an Integer object
need to cast to appropriate type when retrieving from collection
the Collection class to use depends on requirements






list with frequent access using index: Vector or ArrayList
list with frequent insertions or deletions: LinkedList
collection with fast retrieval using key, order not important : HashMap
Stack: Stack
Queue: LinkedList
Set: HashSet
Further work

Reading

java documentation – the package
java.util
http://java.sun.com/j2se/1.5.0/docs/api/java/util/pa
ckage-summary.html

do NOT use the Java collection classes in your
assignment

as you will be assessed on your ability to model a
list using an array