Project 2: Analysis of Linear Data Structures

Choose 4 linear data structures.  For each data structure, choose an operation and evaluate its runtime.  Examples of operations on linear data structures include:
  • push-back
  • push-front
  • pop-back
  • pop-front
  • insert
  • remove
  • random access (index)
  • split: make two lists out of one
  • append: merge two lists end-to-end
Specifically, for each operation provide:
  • pseudocode of the algorithm
  • explanation of how the algorithm works, intuitively
  • charts showing the runtime of the algorithm for varying N (whatever N is...)
  • when would you use this data structure? when would you avoid it?
Additionally, provide:
  • introduction and background sections in your report to explain how your data structures work and which operations they support
  • a bibliography including any references you cite
  • all your code in an appendix.  Make sure your code is well documented (including citations)
Your report should be printed and turned in during class.  I would appreciate a PDF of your report emailed to me as well.