CISC 121 Lecture Notes - Sequential Access, 2Cc, Merge Sort

• School: Queen's University
• Department: Computing
• Course: CISC 121
• Professor: Robin W Dawes

Document Summary

Merge sort t(n)= c if n<= 2 t(n) = c+c*n+2t(n/2) Ia: assume t(n) <= c*nlogn for some specific value of n. Show t(2n) <= c*(2n)log(2n) c(1+2n) + 2t(n) <= c*(2n)log(2n) Using class structure to define our own data structure. Only allow sequential access (have to go through previous terms to get to further along ones) Add new nodes at the end at the beginning in the middle delete nodes anywhere variations: Queue: can only add at the end can only delete from the beginning. Stack: can only add at the end can only delete from the end circular list: Last node linked to the first double linked list: list links go both ways (1 to 2, and 2 to 1, etc)