Introduction to JavaData StructureLinked ListLinked List vs ArraryLinked List Java ExampleSlide 6Stack and QueueSlide 8Slide 9Stack UsageQueue UsagePriority Queue (Heap)Slide 13Slide 14Java DebuggingSlide 16Slide 17Slide 18Slide 19Slide 20ExampleSlide 22Slide 23Slide 24Slide 25Review QuestionsSlide 27ExerciseSlide 29Slide 30Slide 31Program Design GuidelinesSlide 33Slide 34Slide 35Slide 36Slide 37Introduction to JavaData Structure and Program DesignData Structure•Array, ArrayList•Linked List•Stack•Queue•Priority Queue (Heap)Linked List•Used for collecting a sequence of objects–Node: Data part & Address part–Allow efficient insertion and removal of elements in the middleLinked List vs Arrary•http://en.wikipedia.org/wiki/Linked_listLinked List Java ExampleLinked List Java ExampleThe Original Content of list1 :[E, A, B, C, D]The Content of list1 after removing A: [E, B, C, D]The Content of list1 after removing first elem: [B, C, D]Stack and Queue•A stack is a collection of items with “first in last out” retrieval•A queue is a collection of items with “first in fist out” retrievalStack and QueueStack and QueueThe Original Content of stack1: [1, 2, 3, 4]The Content of stack1 after pop: [1, 2]The Original Content of queue1: [1, 2, 3, 4]The Content of queue1 after poll: [2, 3, 4]Stack Usage•Depth-First Search BacktrackingQueue Usage•Breadth-First Search Maze SolvingPriority Queue (Heap)•A priority queue collects elements, each of which has a priority.•When removing an element, the element with the highest priority is retrieved.•Insertion and removal O(log n), locate highest priority O(1)•Application:–Job scheduling, Dijkstra’s Algorithm, Discrete event simulation, Huffman coding[A, B, D, F, C, E]A[B, C, D, F, E]B[C, E, D, F]C[D, E, F]D[E, F]E[F]F[]•Shortest Path ProblemJava Debugging•Set breakpoint:–“Run” -> “Toggle Break Point” OR–Ctrl + Shift + B•Run program with breakpoint:–“Run” -> “Debug” OR–SelectJava DebuggingJava DebuggingJava DebuggingJava Debugging•http://www.vogella.com/tutorials/EclipseDebugging/article.htmlExample•Find the median of a unsorted arrayint[] grades ={87, 78, 93, 77, 69, 100, 90, 100, 85}; •Design:–Class: HomeworkGrade()–Method: findMedian(int[] a)–Algorithm: sort first then return•a[N/2] if N is even•(a[N/2-1] + a[N])/2 if N is oddExampleimport java.util.Arrays;public class HomeworkGrade {public static double findMedian(int[] a) {int[] b = new int[a.length];System.arraycopy(a, 0, b, 0, b.length);Arrays.sort(b);if (a.length % 2 == 0) {return (b[(b.length / 2) - 1] + b[b.length / 2]) / 2.0;} else {return b[b.length / 2];}} public static void main(String[] args) {int[] grades ={87, 78, 93, 77, 69, 100, 90, 100, 85}; System.out.println("The median is : " + median(grades));}Reuse Arrays classExampleimport java.util.Arrays;public class HomeworkGrade {public static double median(int[] a) {int[] b = new int[a.length];System.arraycopy(a, 0, b, 0, b.length);Arrays.sort(b);if (a.length % 2 == 0) {return (b[(b.length / 2) - 1] + b[b.length / 2]) / 2.0;} else {return b[b.length / 2];}} public static void main(String[] args) {int[] grades ={87, 78, 93, 77, 69, 100, 90, 100, 85}; System.out.println("The median is : " + median(grades));}O(nlogn)Example•QuickSelect: O(n) algorithmExampleReview Questions•What is the difference between the print and println method?•Show the results of following expressions:–18/5–18%5Review Questions•Describe each of the following:–public static method;–public method;–public static variable;–private variable.Exercise•Transform the following while loop into an equivalent for loop making sure that it produces the same outputint x = 1;while (x < 20) {x++; System.out.println(x);x += 4;}Exercise•Transform the following while loop into an equivalent for loop making sure that it produces the same outputint x = 1;while (x < 20) {x++; System.out.println(x);x += 4;}271216Exercise•Compare:–Class, Object, Method–Array and ArrayList–Stack, Queue, and Priority Queue–Class File, Project, and PackageProgram Design Guidelines•Preparation–Think before start coding–A working program is not necessarily a good program–Express and document your design with consistent and clear notationProgram Design Guidelines•Structure Programming–Do not use the continue statement–Use break statement to terminate switch–Use the minimum number of return statements in one methodProgram Design Guidelines•Classes and Packages–import statement is used to include the used packages–Avoid declaring variables with public visibility–Access class variables with methodsProgram Design Guidelines•Use eclipse debugging tool to find and fix your program•Test the “working” program with different testing cases to cover:–all statements–all logics–all pathspublic int maxPositive(int x,int y){ int output = 0; if ((x < 0) && (y < 0)) output = 0; else if (x >= y) output = x; else output = y; return output;}Preconditions Output(x <= 0) && (y <= 0) output = 0NOT ((x <= 0) && (y <= 0))x >= youtput = xNOT ((x <= 0) && (y <= 0))x < youtput = yAny