Container Performance

You will compare the speed and memory usage of a Singly Linked List, Doubly Linked List, Binary Search Tree and an AVL tree

Video


copy over all the files provided for you


main1.cpp   - SLL insert front
this is complete and functional
this creates a singly linked list and inserts to the front

main2.cpp   - SLL insert back
this creates a singly linked list and inserts to the back

main3.cpp   - DLL insert front
this creates a doubly linked list and inserts to the front

main4.cpp   - DLL insert back
this creates a doubly linked list and inserts to the back

main5.cpp   - BST insert random values
this creates a BST and inserts random values

main6.cpp   - BST insert accending values
this creates a BST and inserts values that are in accending order

main7.cpp   - AVL insert random values
this creates a AVL Tree and inserts values that are in random order

main8.cpp   - AVL insert accending values
this creates a AVL Tree and inserts values that are in accending order




you will run each program 5 times and record the values
 then calculate the average for insert and search times fill out this document and email it to me at the address in the syllabus 

then run the program a 6th and use valgrind to get the memory usage
ONLY DO THIS on the 6th time  and not  when you are recording the execution time as it will effect the runtime 
performance and  while our sample size is small it should give us some data we can make observations from


msarr@sleipnir> valgrind --leak-check=full ./runme1
==603== Memcheck, a memory error detector
==603== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==603== Using Valgrind-3.10.0 and LibVEX; rerun with -h for copyright info
==603== Command: ./runme1
==603==
single linked list insert front
insert time:27081.000000
search time:1072.000000
==603==
==603== HEAP SUMMARY:
==603==     in use at exit: 0 bytes in 0 blocks
==603==   total heap usage: 10,000 allocs, 10,000 frees, 160,000 bytes allocated
==603==
==603== All heap blocks were freed -- no leaks are possible
==603==
==603== For counts of detected and suppressed errors, rerun with: -v
==603== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)



for the BST and AVL trees you will need to caclulate how full the trees are 
to do this you use the number of values in the tree divided by the total number of potential nodes

here is a list of the Big 0 of some operations here
https://www.bigocheatsheet.com/