An ADT List implementation using LinkedList

The class originally comes from Data Abstraction & Problem solving with C++ Written by Walls & Mirrors, but there are lots of changes since the first version

The Header File The CPP File

There are two version of the sort function

• MyLinkedList::sort compares each of the list items with the rest of them to find its place, it means that the performance is O(n^2)
• MyLinkedList::sortWithBST is using a BST to sort the list first and then generates the Linked List based on the data in BST. Two helper function are used AddListNodeToBinaryTree with the performance of O(logn) means that the perfomrance of O(nlogn) for the whole list and BuildLinkedListFromBST with the performance of O(n) to update the linked list

---

The MyLinkedList::FindMiddle() function finds the value of the middle node, using two pointers, the fast pointer moves twice as fast as the slow pointer, as a result when the fast pointer reaches the end, the slow pointer is in the middle of the list