Lecture Algorithms and data structures: Chapter 21 - Lists. The main contents of the chapter consist of the following: Definition, perfect N-ary trees, complete N-ary trees, implementation using templates. | Review 1 Pseudo Code Basic elements of Pseudo code Basic operations of Pseudo code Flow Chart Symbols used in flow charts Examples List 2 List Data Structure List operations List Implementation Array Linked List The LIST Data Structure The List is among the most generic of data structures. Real life: shopping list, groceries list, list of people to invite to dinner List of presents to get 3 Lists A list is collection of items that are all of the same type (grocery items, integers, names) The items, or elements of the list, are stored in some particular order It is possible to insert new elements into various positions in the list and remove any element of the list 4 Lists List is a set of elements in a linear order. For example, data values a1, a2, a3, a4 can be arranged in a list: (a3, a1, a2, a4) In this list, a3, is the first element, a1 is the second element, and so on The order is important here; this is not just a random collection of elements, it is an ordered collection 5 Lists List is a set of elements in a linear order. For example, data values a1, a2, a3, a4 can be arranged in a list: (a3, a1, a2, a4) In this list, a3, is the first element, a1 is the second element, and so on The order is important here; this is not just a random collection of elements, it is an ordered collection 6 List Operations Useful operations createList(): create a new list (presumably empty) copy(): set one list to be a copy of another clear(); clear a list (remove all elments) insert(X, ?): Insert element X at a particular position in the list remove(?): Remove element at some position in the list get(?): Get element at a given position update(X, ?): replace the element at a given position with X find(X): determine if the element X is in the list length(): return the length of the list. 7 List Operations We need to decide what is meant by “particular position”; we have used “?” for this. There are two possibilities: Use the actual index of element: insert . | Review 1 Pseudo Code Basic elements of Pseudo code Basic operations of Pseudo code Flow Chart Symbols used in flow charts Examples List 2 List Data Structure List operations List Implementation Array Linked List The LIST Data Structure The List is among the most generic of data structures. Real life: shopping list, groceries list, list of people to invite to dinner List of presents to get 3 Lists A list is collection of items that are all of the same type (grocery items, integers, names) The items, or elements of the list, are stored in some particular order It is possible to insert new elements into various positions in the list and remove any element of the list 4 Lists List is a set of elements in a linear order. For example, data values a1, a2, a3, a4 can be arranged in a list: (a3, a1, a2, a4) In this list, a3, is the first element, a1 is the second element, and so on The order is important here; this is not just a random collection of elements, it is an ordered .
