CSE 331 Lecture Notes - Lecture 13: Priority Queue, Complexity Class, Big O Notation
Abstract Data Types
• A mathematical description of a collection with supported operations Start with the
operations you want to do and then define how to do it with whatever data is being
stored;
o Ex: List- a collection storing an ordered sequence of elements
o Each element is accessed by an index
o A list has a size
o Elements can be added to the front or back
o In Java, it can be rep as ArrayList object
Interfaces
• A list of methods that a class promises to implement
• Analogous to non-programming idea of roles or certifications
• Lists: List<Integer> a = new ArrayList<Integer>();
• Queues: Queue<String> b = new LinkedList<String>();
• Maps: Map<String, String> b = new TreeMap<String, String>();
• ADTs here are List, Map, Queue. An ArrayList is an implementation of List
• ADTs: List, Set, Map, Stack, Queue, Priority Queue, Graph
Case Study: List ADT
• Every item is accessible by an index (0-based) and there is a variable size
• Supported operations: get(index), set(value, index), append(value), insert(value, index),
delete(index), size();
• Side Note---Eclipse:
o Make a new project each time
o It automatically picks a place to set your code
o Right click on source (src) folder and make a new class to make new code file
Public class LinkedList {
Private TinNode front;
Private int size;
Public LinkedList() {
This.front = null;
This.size = 0;
}
Private class TinNode {
Public int data;
Public TinNode next;
Public TinNode() {
This(0,null) //calls the constructor and passes in these values
}
Public TinNode(int data, TinNode next) {
This.data = data;
this.TinNode = next;
}
}
