15.082J/6.855J/ESD.78J September 14, 2010Overview of this LectureTwo standard data structuresRepresentations of subsets of a setExample 1: Creating an empty setExample 2: Is x ∈ S?Representing a linked list as an arrayTwo key conceptsA note on data structuresAbstract data type: SetOperationsImplementation using doubly linked listAdd element 5 to the set (in first position)Slide 13Delete element 2 from the set (assume it is neither in first or last position)Slide 15Operations using doubly linked listsMaintaining disjoint subsets of elementsMaintaining ordered listsMental BreakSlide 20Complete binary tree with n elementsSlide 22Slide 23Slide 24Find greatest element less than jDelete an elementOperations using complete binary treesA networkStoring Arc Lists: A(i)Scanning the arc listSlide 31The Adjacency Matrix (for directed graphs)The Adjacency Matrix (for undirected graphs)Adjacency Matrix vs Arc ListsTreesForestOne way of storing subtreesOn storing treesStacks -- Last In, First Out (LIFO)Queues – First in, First Out (FIFO)Binary SearchSlide 42Slide 43SummarySlide 4515.082J/6.855J/ESD.78J September 14, 2010 Data Structures2Overview of this LectureA very fast overview of some data structures that we will be using this semesterlists, sets, stacks, queues, networks, treesa variation on the well known heap data structurebinary searchIllustrated using animationWe are concerned with O( ) computation counts, and so do not need to get down to C++- level (or Java level).3Two standard data structures1 0 1 1 0 1 0 1 0 01 2 3 4 5 6 7 8 9 10Array: a vector: stored consecutively in memory, and typically allocated in advance cells: hold fields of numbers and pointers to implement lists.1 6 3 8 4firstThis is a singly linked listRepresentations of subsets of a set41 0 1 1 0 1 0 1 0 01 2 3 4 5 6 7 8 9 10Array Asubset S = {1, 3, 4, 6, 8}1 6 3 8 4firstList LThe choice of data structure depends on what operations need to be carried out.Example 1: Creating an empty set50firstInitialize: subset S = ∅0 0 0 0 01 2 3 4 n…O(n) stepsO(1) stepsExample 2: Is x S?∈61 0 1 1 0 1 0 1 0 01 2 3 4 5 6 7 8 9 101 6 3 8 4first To determine if 9 S?, one needs to scan the ∈entire list. Is 9 S?∈O(1) stepsO(n) steps7Representing a linked list as an array6 8 ∅ 3 41 2 3 4 5 6 7 8 9 101 6 3 8 4firstArray: NextIf Next(j) is empty, then j is not on the listIf Next(j) = , then j is the last element on the list∅8Two key conceptsAbstract data types: a descriptor of the operations that are permitted, e.g., abstract data type: set Sinitialize(S): creates an empty set Sadd(S, s): replaces S by S {s}.∪delete(S, s): replaces S by S \{s} IsElement(S, s): returns true if s ∈ Setc.Data structure: usually describes the high level implementation of the abstract data types, and can be analyzed for running time.doubly linked list, etc9A note on data structuresPreferencesSimplicityEfficiencyIn case there are multiple good representations, we will choose one10Abstract data type: SetOperationsOperation (assume S {1, 2, 3, … n}.⊆initialize(S): S := ∅add(S, j): S := S {j} ∪delete(S, j): S := S\{j} IsElement(S, j): returns TRUE if s ∈ SFindElement(S): if S ≠ , returns j for some j S∅ ∈Next(S, j) : if j S, it finds the next element ∈ after j on S (viewed as a list)Implementation using doubly linked list1142first2 48 21 2 3 4 5 6 7 8 9 10∅84 ∅1 2 3 4 5 6 7 8 9 102Next( )PrevFirst = 8Add element 5 to the set (in first position)1242first2 48 2 ∅84 ∅1 2 3 4 5 6 7 8 9 102Next( )Prev( )Temp:= FirstTempFirst8Elt5Prev(Temp): = Elt First:= EltPrev(Elt): = ∅Next(Elt): = Temp55Add element 5 to the set (in first position)1342first2 48 2 ∅84 ∅1 2 3 4 5 6 7 8 9 102Next( )Prev( )Temp:= FirstTempFirst88Elt5Prev(Temp): = Elt First:= EltPrev(Elt): = ∅Next(Elt): = Temp58∅55Adding an element to a set takes O(1) steps using this implementation.Delete element 2 from the set (assume it is neither in first or last position)1442first2 48 2 ∅84 ∅1 2 3 4 5 6 7 8 9 102Next( )Prev( )TempFirst8Elt258∅55Delete element 2 from the set (assume it is neither in first or last position)152first48 2 ∅8 24 ∅1 2 3 4 5 6 7 8 9 102Next( )Prev( )First8Elt2Prev(Elt) := 0Next(Prev(Elt)):=Next(Elt)Next(Elt): = 058∅55Deleting an element from the set takes O(1) steps using this implementation.4Prev(Next(Elt)):=Prev(Elt)816Operations using doubly linked listsOperation Number of stepsinitialize(S): O(n)add(S, j): O(1) delete(S, j): O(1)IsElement(S, j): O(1)FindElement(S): O(1)Next(S, j): O(1)Previous(S, j) : O(1)Maintaining disjoint subsets of elements1742First(1) 2 48S1 = {8, 2, 4}S1 = {5, 7, 1}42First(2) 7 157 8 2 5 ∅Prev( )∅∅284 ∅ 11 2 3 4 5 6 7 8 9 102Next( )7 24∅8 5First( )Maintaining ordered listsThe doubly linked list is not efficient for maintaining ordered lists of nodes.1842first4 824 ∅1 2 3 4 5 6 7 8 9 102Next( )8 2 ∅Prev( )5Inserting an element into the set (such as 7) requires finding Prev and Next for 7 (4 and 8), and this requires O(n) time with this implementation.Mental Break19Who created the cartoon characters "The Simpson's? Matt GroeningWhich country would you be in if you were to ski in the Dolomites? ItalyWho was the first U.S. president to adopt the informal version of his first name? Jimmy CarterMental Break20Which country owns the island of Bermuda? Great BritainWhat colors do most color blind persons have trouble distinguishing? red and greenWhat bird is used as the sign of peace? the doveComplete binary tree with n elementsComplete binary trees for storing ordered lists of nodes or arcs. We assume that the number of nodes is n (e.g., 8) and the number of arcs is m.21S = {2, 4, 8} n = 8.2 41 2 3 4 5 6 78 8Complete binary tree with n elementsBuild up the binary tree. In each parent store the least value of its children.222 41 2 3 4 5 6 78S = {2, 4, 8} n = 8. 82 4 8Complete binary tree with n elementsBuild up the binary tree. In each parent store the least value of its children.232 41 2 3 4 5 6 78S = {2, 4, 8} n = 8. 82 842 8Complete binary tree with n elementsBuild up the binary tree. In each parent store the least value of its children.242 41 2 3 4 5 6 78S = {2, 4, 8} n = 8. 82 842 82Find greatest element less than je.g., find the greatest