This chapter provides knowledge of lists. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Lists and Iterators 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Lists and Iterators © 2014 Goodrich, Tamassia, Goldwasser Lists and Iterators 1 The ADT q The interface includes the following methods: © 2014 Goodrich, Tamassia, Goldwasser Lists and Iterators 2 1 Lists and Iterators 3/19/14 Example q A sequence of List operations: © 2014 Goodrich, Tamassia, Goldwasser Lists and Iterators 3 Array Lists q q An obvious choice for implementing the list ADT is to use an array, A, where A[i] stores (a reference to) the element with index i. With a representation based on an array A, the get(i) and set(i, e) methods are easy to implement by accessing A[i] (assuming i is a legitimate index). A 0 1 2 © 2014 Goodrich, Tamassia, Goldwasser i Lists and Iterators n 4 2 Lists and Iterators 3/19/14 Insertion q q In an operation add(i, o), we need to make room for the new element by shifting forward the n - i elements A[i], , A[n - 1] In the worst case (i = 0), this takes O(n) time A 0 1 2 i n 0 1 2 i n 0 1 2 o i A A © 2014 Goodrich, Tamassia, Goldwasser n Lists and Iterators 5 Element Removal q q In an operation remove(i), we need to fill the hole left by the removed element by shifting backward the n - i - 1 elements A[i + 1], , A[n - 1] In the worst case (i = 0), this takes O(n) time A 0 1 2 o i n 0 1 2 i n 0 1 2 i A A © 2014 Goodrich, Tamassia, Goldwasser Lists and Iterators n 6 3 Lists and Iterators 3/19/14 Performance q In an array-based implementation of a dynamic list: n n n q The space used by the data structure is O(n) Indexing the element at i takes O(1) time add and remove run in O(n) time In an add operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one © 2014 Goodrich,
