Introduction to Java Data Structure and Program Design Data 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 middle Linked List vs Arrary http en wikipedia org wiki Linked list Linked List Java Example Linked List Java Example The 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 retrieval Stack and Queue Stack and Queue The 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 Backtracking Queue Usage Breadth First Search Maze Solving Priority 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 Problem Java Debugging Set breakpoint Run Toggle Break Point OR Ctrl Shift B Run program with breakpoint Run Debug Select OR Java Debugging Java Debugging Java Debugging Java Debugging http www vogella com tutorials EclipseDe bugging article html Example Find the median of a unsorted array int 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 odd Example import 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 Reuse Arrays class 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 Example import 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 O nlogn 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 Example QuickSelect O n algorithm Example Review Questions What is the difference between the print and println method Show the results of following expressions 18 5 18 5 Review 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 output int 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 output int x 1 while x 20 x System out println x x 4 2 7 12 16 Exercise Compare Class Object Method Array and ArrayList Stack Queue and Priority Queue Class File Project and Package Program 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 notation Program 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 method Program Design Guidelines Classes and Packages import statement is used to include the used packages Avoid declaring variables with public visibility Access class variables with methods Program 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 paths public 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 Preconditions Output x 0 y 0 output 0 NOT x 0 y 0 output x x y return output NOT x 0 y 0 x y output y Any Questions