Arrays and Abstract Data Types (ADTs)

Arrays

• Defined as a collection of values of the same type
• Identified by an integer index
• Stored in consecutive memory locations
• Enables the computation of each element's location from its index

Array functions

• Creating a new array
• Setting the value of the ith element
• Getting the value of the ith element

Java Interface Example

interface ObjectArray {
    void create (int length);
    void set (int index, Object value);
    Object get (int index);
}

Abstract Data Types (ADTs)

• Abstract datatypes combine an interface with behavioural descriptions and requirements
• Operations on data
• Behavior of the operations
• Running times
• ADTs don't specify implementation or language
• The implementation is a concrete datatype
• Proposed by Barbara Liskov and Stephen Zilles, inventors of OOP
• Implemented as classes in Java
• Application programmers should be able to switch to a different implementation of an ADT with minimal code changes and no change in behaviour.
• ADT implementers should only allow data access through defined operations, keeping fields and helper methods private.

Arrays as an ADT

• Operations: create, set, get
• Getting get(i) returns the Object argument of the most recent call set(i, something)
• The set and get running time does not depend on array length.

Concrete datatypes

• Concrete datatypes are actual datatypes in actual languages, e.g., int, double[] [], class MyClass { ... } in Java.
• Concrete datatypes are defined entirely by their implementation.

Summary on ADTs

• ADTs define a datatype by specifying:
• Operations on the data
• Behavior of operations
• Running times

Lists

• A sequence of data items
• Java's LinkedList and ArrayList are examples
• Head: First item
• Tail: Last item

List ADT Operations/Functions

• void create(), boolean isEmpty(), int length()
• void insert(int index, String s) inserts data at the index
• String get(int index) returns the indexth item
• void delete(int index) deletes the indexth item

List ADT Running Time

• insert(), get(), delete() is proportional to the size of the list.

Linked Lists

• Doubly linked list: each item has a reference to the next and previous items.
• Singly linked list: each item only has a reference to the next one.

Lists vs Arrays

List Iteration

• Using a "current" item of the list, also known as cursor

Implementing Iteration Functions

• list.rewind (): Reset to start
• list.hasNext(): Check next element
• list.getNext(): Get next element

Java Standard Libraries

• Two implementations of lists: ArrayList and LinkedList
• ArrayList: stores entries in an array; fast for get (constant time); slow for insert and delete (time ∝ length); append is fast on average (constant time)
• LinkedList: a doubly linked list
• ListIterator interface and List.listIterator() method define iterators; allow insertion, deletion, etc. at the current position

List Summary

• Similar to growable arrays, but with insertion and deletion
• Random access typically expensive
• Efficient iteration possible
• Different implementations are suited to different purposes

Queue ADT Operations/Functions

• void create(): creates a new empty queue
• boolean isEmpty(): returns true if the queue is empty
• int length(): returns number of queue items
• void add(String s): adds to the back of the queue
• String remove(): removes and returns item from the front of the queue
• Executing time of all queue operations is independent of the queue's size

Queue Uses

• For things needing processing in a create/discover order
• Network switches processing packets
• Queueing theory, a branch of mathematics
• Event queues in GUIs
• Breadth-first search.

Queue Linked List

• It looks like a singly linked list, but the running time of add() and remove() must not depend on the list's length.
• insert() and delete() do depend on length, queues only add and remove at the ends.

Queue Summary

• First in, first out memory
• Operations are add and remove
• Able to grow to any length but add and remove always take the same amount of time.
• Often implemented as a singly linked list
• Uses: network switches, event handling, breadth-first search

Stacks

• LIFO (last in, first out)
• Analogy to stack of books

Stack ADT Operations/Functions

• void create(): creates a new empty stack
• boolean isEmpty(): returns true if the stack is empty
• int length(): returns the number of items on the stack
• void push(String s): puts data on top of the stack
• String pop(): returns and removes the top item of the stack
• Running time of all stack operations is independent of the stack's size.
• In Java, create() is replaced by the constructor.

Stack Uses

• Remembering things to come back to later
• Function/method calls use stacks
• Depth-first search

Stack Implementation with pointers

• Each item needs a reference to the item below it
• Tracking is needed for the top, but not for the bottom

Stack Implementation Summary

• LIFO memory
• Operations are push and pop
• Able to grow to any length but both always take the same amount of time
• Uses: function call implementation, depth-first search