StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POCustom Linked List Sort Method
text
Body
copied!<p>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)</p> <p>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:</p> <pre><code>#ifndef LIST_HPP #define LIST_HPP #include <string> template <typename T> class Node; template <typename T> 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<T>* head_; Node<T>* current_; }; template <typename T> List<T>::List() : size_(0), head_(0), current_(0) { } template <typename T> List<T>::~List() { while (isEmpty()) { popFront(); } head_ = 0; } template <typename T> bool List<T>::isEmpty() const { return (!size_ || !head_); } template <typename T> T& List<T>::front() { if (isEmpty()) throw std::string("List Empty"); return head_->data(); } template <typename T> T& List<T>::back() { Node<T>* cur = head_; while (true) { if (cur->next() == 0) return cur->data(); cur = cur->next(); } } template <typename T> void List<T>::pushFront(const T& s) { current_ = head_ = new Node<T>(s, head_); size_++; } template <typename T> T List<T>::popFront() { if (isEmpty()) { throw std::string("List Empty"); } Node<T>* current_head = head_; current_ = head_ = head_->next(); T temp = current_head->data(); delete current_head; size_--; return temp; } template <typename T> const T* List<T>::each() { if (isEmpty()) return 0; if (current_ == 0) { current_ = head_; return 0; } const T* ret_str = &current_->data(); current_ = current_->next(); return ret_str; } template <typename T> void List<T>::removeElement(const T& s) { if (isEmpty()) { throw std::string("List Empty"); return; } Node<T>* prev = 0, *rnode; rnode = head_; while (rnode != 0) { if (rnode->data() == s) break; prev = rnode; rnode = rnode->next(); } if (prev == 0) { Node<T>* temp = head_; current_ = head_ = head_->next(); delete temp; } else { prev->next(rnode->next()); delete rnode; } size_--; } template <typename T> void List<T>::insert(const T& s) { if (isEmpty()) { pushFront(s); } else if (size_ == 1) { if (s <= head_->data()) pushFront(s); else head_->next(new Node<T>(s, 0)); size_++; } else { Node<T>* 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<T>(s, current)); size_++; } } template <typename T> unsigned int List<T>::size() const {return size_;} template <typename T> class Node { public: Node(const T& data, Node<T>* next = 0); T& data(); Node* next(); void next(Node<T>* n); private: T data_; Node* next_; }; template <typename T> Node<T>::Node(const T& data, Node* next): data_(data), next_(next) { } template <typename T> void Node<T>::next(Node<T>* n) { next_ = n; } template <typename T> Node<T>* Node<T>::next() { return next_; } template <typename T> T& Node<T>::data() { return data_; } #endif //LIST_HPP </code></pre> <p>Surely there is a way to sort with only one iteration through the list? Or maybe not.</p> <p>Thanks for any help in advance!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload