List ADT - Implementation Data Structures• Big-O’s of List ImplementationsADT OperationsArraySingly-Linked ListDoubly- Linked ListInsert(In order)(At front)NN1NDeleteNN1FindNNNFindKth1NNNext111Prev1N1IsEmpty111• Array Next and Prev assume that a current index is maintained as part of the list implementation.• Array IsEmpty assumes that the length of the list is maintained.• Insert (at current location) on a doubly-linked list is O(1). Insert (at an arbitrary location)...Reversing a List• If the list is implemented as an array...• What is the Big-O of this algorithm?• There are n/2 swaps (n is the length of the list).• O(n)Reversing a Linked List• Given a singly-linked list, with List_p pointing to the head of the list (no header element, th...curr = List_p;next = List_p->next;prev = NULL;while (next != NULL) {curr->next = prev;prev = curr;curr = next;next = curr->next;}Reversing a Linked List (cont’d)curr->next = prev;List_p = curr;• The Big-O of this algorithm is O(n).• What about Doubly-Linked Lists?• Just swap the prev and next pointers in each element. Also O(n).CSCI S-Q Lecture 3 - 6/29/98 - Page 1List ADT - Implementation Data Structures•Big-O’s of List Implementations• Array NEXT and PREV assume that a current index is maintained as part of the list implementation.• Array ISEMPTY assumes that the length of the list is maintained.•INSERT (at current location) on a doubly-linked list is O(1). INSERT (at an arbitrary location) on a doubly-linked list is O(N).ADT OperationsArraySingly-Linked ListDoubly-Linked ListINSERT(IN ORDER)(AT FRONT)NN1NDELETENN1FINDNNNFINDKTH1NNNEXT111PREV1N1ISEMPTY111CSCI S-Q Lecture 3 - 6/29/98 - Page 2Reversing a List• If the list is implemented as an array...• What is the Big-O of this algorithm?• There are n/2 swaps (n is the length of the list).• O(n)SWAPCSCI S-Q Lecture 3 - 6/29/98 - Page 3Reversing a Linked List• Given a singly-linked list, with List_p pointing to the head of the list (no header element, though this algorithm can easily be extended to use that implementation), assuming the list isn’t empty:curr = List_p;next = List_p->next;prev = NULL;while (next != NULL) {curr->next = prev;prev = curr;curr = next;next = curr->next;}1234List_pprev curr nextNULL1234List_pprev curr nextAfter 1 iteration:CSCI S-Q Lecture 3 - 6/29/98 - Page 4Reversing a Linked List (cont’d)curr->next = prev;List_p = curr;•The Big-O of this algorithm is O(n).• What about Doubly-Linked Lists?• Just swap the PREV and NEXT pointers in each element. Also O(n).1234List_pprev curr next1234List_pprev curr next1234List_pAfter 2After 3NULLiterations