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

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
copy main1.cpp to main2.cpp
#cp main1.cpp main2.cpp
change Insert to InsertBack

main3.cpp   - DLL insert front
same as main1.cpp but with Doubly Linked List
copy main1.cpp to main3.cpp
change SLinkedList to DLinkedList
in vi "escape :" then
%s/SLinkedList/DLinkedList/g
change SListNode to DListNode

main4.cpp   - DLL insert back
same as main2.cpp but with Doubly Liked List
copy main1.cpp to main3.cpp
change SlinkedList to DLinkedList
change SListNode to DListNode

main5.cpp   - BST insert accending values
copy main1.cpp to main5.cpp
change SLinkedList to BST
change SListNode to TreeNode
comment out the line that shuffles the array

main6.cpp   - BST insert random values
copy main5.cpp to main6.cpp
enable the line that shuffles them

main7.cpp   - AVL insert accending values
copy main5.cpp main7.cpp
change BST to AVL
comment out the line that shuffles the array

main8.cpp   - AVL insert random values
copy main7.cpp main8.cpp
enable the line that shuffles them



Once you have your main1 - main8  compiled and running properly you can fill out the provided handout

checklist

you will run each program 5 times and record the values
 then calculate the average for insert and search times

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)