15.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 4firstTo 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 list8Two 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 list1142first 2 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)1242first 2 48 2 ∅84 ∅1 2 3 4 5 6 7 8 9 102Next( )Prev( )Temp:= FirstTempFirst8Elt5Prev(Temp): = EltFirst:= EltPrev(Elt): = ∅Next(Elt): = Temp55Add element 5 to the set (in first position)1342first 2 48 2 ∅84 ∅1 2 3 4 5 6 7 8 9 102Next( )Prev( )Temp:= FirstTempFirst88Elt5Prev(Temp): = EltFirst:= 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)1442first 2 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)152first 48 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.1842first 4 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.Complete 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.19S = {2, 4, 8} n = 8.2 41 2 3 4 5 6 788Complete binary tree with n elementsBuild up the binary tree. In each parent store the least value of its children.202 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.212 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.222 41 2 3 4 5 6 78S = {2, 4, 8} n = 8.82 842 82Find greatest element less than je.g., find the greatest element less than 7 232 41 2 3 4 5 6 7882 842 825552O(log n) steps for finding greatest element less than j.start at 7go up the tree until a node has label < 7. Take left branch.Choose the largest label child going down.Delete an elemente.g., delete element 2242 41 2 3 4 5 6 78S = {4, 5, 8} n = 8.82 842 825552O(log n) steps for an deletion44Start at node 2 and update it and its ancestors.Operations using complete binary trees25Operation Number of steps initialize(S): O(n) add(S, j): O(log n)  delete(S, j): O(log n) IsElement(S, j): O(1) FindElement(S): O(1) Next(S, j): O(log n) Previous(S, j) : O(log n) MinElement(S) O(1) MaxElement(S) O(log n)26A network12345We can view the arcs of a networks as a collection of sets.Let A(i) be the arcs emanating from node i.e.g., A(5) = { (5,3), (5,4) }Note: these sets are usually static. They stay the same. Common operations: scanning the list A(i) one arc at a time starting at the first arc.27Storing Arc Lists: A(i)Operations permitted Find first arc in A(i) Store a pointer to the current arc in A(i) Find the arc after CurrentArc(i) i j cijuij24 15 4032 45 10 5 45 6053 25 20 4 35 50412 25 30 5 15 403 23 3528Scanning the arc listCurrentArc(i) is a pointer to the arc of A(i) that is being scanned or is the next to be scanned. 12 25 30 5 15 403 23 35CurrentArc(1) CurrentArc(1)Initially, CurrentArc(i) is the first arc of A(i)After CurrentArc(i) is fully scanned, CurrentArc(i) := Next(CurrentArc(i))29Scanning the arc listCurrentArc(i) is a pointer to the arc of A(i) that is