Sorting Linked Lists
-
Hi! I'm learning about linked lists and have created the following class:
struct Node { int data; Node *next; Node *prev; }; class BasicList { public: /* CONSTRUCTORS / DESTRUCTORS */ BasicList(); // Default Constructor /* INSERTION METHODS */ void Prepend(int n); // Insert n into list as the first item void Append(int n); // Insert n into list as the last item void InsertAfter(int key, int n); // Insert n into list after key void InsertBefore(int key, int n); // Insert n into list before key void Swap(int first, int second); // Swap specified elements void Remove(int key); // Remove first occurance of key from list /* QUERY METHODS */ void DisplayNodes() const; // Display the data item from each node in the list bool IsEmpty() const; // Return true if the list is empty int Maximum() const; // Return the largest member in the list int Minimum() const; // Return the smallest member in the list int Occurances(int key) const; // Return the number of occurances of key int NumNodes() const; // Return the number of nodes in the list /* HELPER FUNCTIONS */ Node *GetAddress(int n); // Returns the address of the first instance of n found in list int *GetDataArray(); // Return a pointer to an array containing the data. Last item in array is NULL private: /* MEMBERS */ Node *head; // pointer to empty head node Node *tail; // pointer to empty tail node };All the functions work wonderfully so far. I want to add a method that will sort the linked list data. I'm not really sure where to begin. I checked Wikipedia, and found the following URL which presents a MergeSort algorithm. I'm not sure if this is the best way. Any opinions? http://en.wikipedia.org/wiki/Merge\_sort