Arrays and Lists Arrays Contiguous memory locations lists Forms basis for all other data structures 2010 Goodrich Tamassia Using Recursion 1 Array based Implementation Use an array A of size N A variable n keeps track of the size of the array list number of elements stored Operation at i is implemented in O 1 time by returning A i Operation set i o is implemented in O 1 time by performing A i o A 0 1 2 2010 Goodrich Tamassia n i Array Lists 2 Insertion In operation insert 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 2010 Goodrich Tamassia Array Lists n 3 Element Removal In operation erase 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 2010 Goodrich Tamassia Array Lists n 4 Performance In the array based implementation of an array list The space used by the data structure is O n size empty at and set run in O 1 time insert and erase run in O n time in worst case If we use the array in a circular fashion operations insert 0 x and erase 0 x run in O 1 time In an insert operation when the array is full instead of throwing an exception we can replace the array with a larger one 2010 Goodrich Tamassia Array Lists 5 Growable Array based Array List In an insert o operation without an index we always insert at the end When the array is full we replace the array with a larger one How large should the new array be Incremental strategy increase the size by a constant c Doubling strategy double the size 2010 Goodrich Tamassia Array Lists Algorithm insert o if t S length 1 then A new array of size for i 0 to n 1 do A i S i S A n n 1 S n 1 o 6 Comparison of the Strategies We compare the incremental strategy and the doubling strategy by analyzing the total time T n needed to perform a series of n insert o operations We assume that we start with an empty stack represented by an array of size 1 We call amortized time of an insert operation the average time taken by an insert over the series of operations i e T n n 2010 Goodrich Tamassia Array Lists 7 Incremental Strategy Analysis We replace the array k n c times The total time T n of a series of n insert operations is proportional to n c 2c 3c 4c kc n c 1 2 3 k n ck k 1 2 Since c is a constant T n is O n k2 i e O n2 The amortized time of an insert operation is O n 2010 Goodrich Tamassia Array Lists 8 Doubling Strategy Analysis We replace the array k log2 n times The total time T n of a series of geometric series n insert operations is 2 proportional to 4 1 1 n 1 2 4 8 2k n 2k 1 1 3n 1 8 T n is O n The amortized time of an insert operation is O 1 2010 Goodrich Tamassia Array Lists 9 Linked Lists 2006 Goodrich Tamassia Linked Lists 10 Singly Linked List 3 2 A singly linked list is a concrete data structure consisting of a sequence of nodes Each node stores next node elem element link to the next node A 2006 Goodrich Tamassia B C Linked Lists D 11 Inserting at the Head 1 Allocate a new node 2 Insert new element 3 Have new node point to old head 4 Update head to point to new node 2006 Goodrich Tamassia Linked Lists 12 Removing at the Head 1 Update head to point to next node in the list 2 Allow garbage collector to reclaim the former first node 2006 Goodrich Tamassia Linked Lists 13 Inserting at the Tail 1 Allocate a new node 2 Insert new element 3 Have new node point to null 4 Have old last node point to new node 5 Update tail to point to new node 2006 Goodrich Tamassia Linked Lists 14 Removing at the Tail Removing at the tail of a singly linked list is not efficient There is no constant time way to update the tail to point to the previous node 2006 Goodrich Tamassia Linked Lists 15 Doubly Linked List A doubly linked list provides a natural implementation of the Node List ADT Nodes implement Position and store element link to the previous node link to the next node prev next elem node Special trailer and header nodes nodes positions trailer header elements 2010 Goodrich Tamassia Lists 16 Insertion We visualize operation insert p x which inserts x before p a a p c b p c b x a 2010 Goodrich Tamassia q x b Lists q p c 17 Insertion Algorithm Algorithm insert p e insert e before p Create a new node v v element e u p prev v next p p prev v link in v before p v prev u u next v link in v after u 2010 Goodrich Tamassia Lists 18 Deletion We visualize remove p a b c a b c p d p d a 2010 Goodrich Tamassia b c Lists 19 Deletion Algorithm Algorithm remove p u p prev w p next u next w linking out p w prev u 2010 Goodrich Tamassia Lists 20 Performance In the implementation of the List ADT by means of a doubly linked list The space used by a list with n elements is O n The space used by each position of the list is O 1 All the operations of the List ADT run in O 1 time Operation element of the Position ADT runs in O 1 time 2010 Goodrich Tamassia Lists 21 Examples single link list struct link one element of list int data data item link next pointer to next link class linklist a list of links private link first pointer to first link public linklist no argument constructor first NULL no first link void additem int d add data item one link void display display all links 2006 Goodrich Tamassia Linked Lists 22 Examples single link list int main int argc char argv linklist li make linked list li additem 25 add four items to list li additem 36 li additem 49 li additem 64 li display display entire list return 0 Write the functions additem and display 2006 Goodrich Tamassia Linked Lists 23 Examples single link list void linklist additem int d add data item link newLink new link newLink data d insert at head newLink …
View Full Document
Unlocking...