### Custom Linked List Sort Method

Hi I am making a custom linked list (for fun!) and want to implement a sort method that sorts the stored data using the stored types > and < operators (will require the type to have these operators overloaded)

What is the best way to do this? I guess the first thing one might jump to would be to compare the current node with the the node to its "right" see if one is greater than the other. Then keep iterating through the list until you don't swap any more nodes. However I am thinking there is probably a more efficient way to do this. Here is my code so far:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221`` ``````#ifndef LIST_HPP #define LIST_HPP #include template class Node; template class List { public: List(); ~List(); bool isEmpty() const; T& front(); T& back(); inline unsigned int size() const; void pushFront(const T& s); void removeElement(const T& s); void insert(const T& s); T popFront(); const T* each(); private: unsigned int size_; Node* head_; Node* current_; }; template List::List() : size_(0), head_(0), current_(0) { } template List::~List() { while (isEmpty()) { popFront(); } head_ = 0; } template bool List::isEmpty() const { return (!size_ || !head_); } template T& List::front() { if (isEmpty()) throw std::string("List Empty"); return head_->data(); } template T& List::back() { Node* cur = head_; while (true) { if (cur->next() == 0) return cur->data(); cur = cur->next(); } } template void List::pushFront(const T& s) { current_ = head_ = new Node(s, head_); size_++; } template T List::popFront() { if (isEmpty()) { throw std::string("List Empty"); } Node* current_head = head_; current_ = head_ = head_->next(); T temp = current_head->data(); delete current_head; size_--; return temp; } template const T* List::each() { if (isEmpty()) return 0; if (current_ == 0) { current_ = head_; return 0; } const T* ret_str = ¤t_->data(); current_ = current_->next(); return ret_str; } template void List::removeElement(const T& s) { if (isEmpty()) { throw std::string("List Empty"); return; } Node* prev = 0, *rnode; rnode = head_; while (rnode != 0) { if (rnode->data() == s) break; prev = rnode; rnode = rnode->next(); } if (prev == 0) { Node* temp = head_; current_ = head_ = head_->next(); delete temp; } else { prev->next(rnode->next()); delete rnode; } size_--; } template void List::insert(const T& s) { if (isEmpty()) { pushFront(s); } else if (size_ == 1) { if (s <= head_->data()) pushFront(s); else head_->next(new Node(s, 0)); size_++; } else { Node* current, *prev = 0, *new_node = 0; while (current != 0) { if (s <= current->data()) break; prev = current; current = current->next(); } if (prev == 0) pushFront(s); else prev->next(new Node(s, current)); size_++; } } template unsigned int List::size() const {return size_;} template class Node { public: Node(const T& data, Node* next = 0); T& data(); Node* next(); void next(Node* n); private: T data_; Node* next_; }; template Node::Node(const T& data, Node* next): data_(data), next_(next) { } template void Node::next(Node* n) { next_ = n; } template Node* Node::next() { return next_; } template T& Node::data() { return data_; } #endif //LIST_HPP ``````

Surely there is a way to sort with only one iteration through the list? Or maybe not.

Thanks for any help in advance!
What you are asking for is O(n) time complexity. This is not even possible for data which is contiguous in memory. There are some algo's though which can give O(n) complexity but they are not practical for production environments.

Here you have a linked list which has nodes scattered in memory. generally the sort take O(n^2)time complexity for a linked list. This can be marginally improved (reducing the constant factor may be). What you can do is use a external data structure may be a tree or hash table and keep some metadata in that (sorted) which will map to the actual linkedlist.

Last edited on
I wrote this code a few weeks ago. Looks like I am ahead of myself. The list seems to sort the data as I insert it.
Topic archived. No new replies allowed.