Transcript Data Structures an Introduction 2010_01

HIT2037- HIT6037
Software Development in Java
22 – Data Structures and Introduction
Content

Introduction to data structures

Introduction to sorting

Introduction to searching
2
What is a Data Structure?

We have already worked out how to store objects in an
ArrayList

However, there are other “Data Structures” that allow us
to store collections of objects

Each structure has different strengths and weaknesses

One structure might be perfect for one application and
terrible for another
3
Linked List
 “A link list has a number of nodes each of which has a reference
to the next node” [1]

Key features
 Good where items need to be removed or added in the middle of the list (
just change the reference)
 Sequential access is efficient
 Java provides a LinkedList<typed> in the util package
 LinkedList<Student>
 An iterator can be used with a LinkedList
 See simulation
http://www.cs.stir.ac.uk/~mew/dissertation/simulation.htm
4
Linked List – Some Operations

addLast(E e)

addFirst(E e)

add(int index, E element)

getFirst()

getLast()

indexOf(Object o)

peekFirst()

peekLast()
Items in the list do not need to be
stored in order in memory
Linked Lists do not do this
efficiently. They only allow
sequential access
Variations include
Circular lists, link from head to tail
Double linked lists, traverse forward and
backwards
Other data structures such as
Stacks and Queues are often based
on Linked Lists
5
Queue
Why use it?
“Conceptually what we want”[2]
A pipe
Items you want to deal with order of arrival
(Time?)

Implements “first in first out”

Example “a queue of jobs to do”

Java provides a Queue class in the util package

Important operations
 add (E e) // returns true if it works
 poll() // retrieves head or returns false (check this)
 peek() // retrieves head but does not remove
 remove() // retrieves and removes head of queue
http://www.cosc.canterbury.ac.nz/mukundan/dsal/QueueAppl.html
6
Stack
Its interesting to note this
class inherits from Vector

Implements “last in first out”

“What does the stack do in the computers memory?”

Java provides a Stack class in the util package

Important operations
 push (E e) // add item to the stack
 pop() // take item off the top of the stack
 peek() //get without removing
Why use a stack,
Good for reversing a series of
operations
Open 1
open 2
open 3
Now go back, undo [3]
 empty() // see if stack is empty
 search(Object o) // returns position of object in stack
http://www.cosc.canterbury.ac.nz/mukundan/dsal/StackAppl.html
7
Hash Table, (from the api)

“This class implements a hashtable, which maps keys
to values. Any non-null object can be used as a key or
as a value.”
8
References

[1] Cay Horstmann, Java Concepts, 5th Edition, 2008

http://cslibrary.stanford.edu/103/

http://en.wikipedia.org/wiki/Big_O_notation

http://java.sun.com/javase/6/docs/api/java/util/Hashtable.html

[2], http://www.javamex.com/tutorials/synchronization_concurrency_8_queues.shtml

[3], http://msdn.microsoft.com/en-us/library/aa227588(VS.60).aspx

http://en.wikipedia.org/wiki/Hash_table
9