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 acceding values this creates a AVL Tree and inserts values that are in acceding order you will run each program 5 times and record the values on the sheets I give you filling out 1st run, 2nd run, 3rd run, 4th run and 5th run then calulate the avage of those 5 values to populate the average column then run the program a 6th and use valgrind to get the memory usage ONLY USE valgrind on the 6th run of the program 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 calculate 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 max nodes = 2^(tree height) -1 percent full is number of values inserted (1000) / max nodes here is a list of the Big 0 of some operations here https://www.bigocheatsheet.com/