Sort after inserting an item into a Linked List?

I have a C++ Program to insert Nodes to a linked list. The Nodes consist of a string that we'll call data, and a pointer to the next node that we'll call next. Also, the head node will be defined as head.

I'm not sure what's more efficient - 1. Inserting a bunch of strings to my list then sorting it afterward 2. Or sorting the list as I insert.

I think it's the latter, and I am wondering how I will go about implementing something like that.

I want to know the simplest way to implement s开发者_运维技巧uch a function.

---

first solution: insert k elements unsorted, just insert them to the start, it is O(1) each. and one sort: O(nlogn) after these k elements. you get amortized time of O(nlogn+k)/k = O(n(logn/k)).

second solution: inserting an element to a list is in sorted order is O(n), since you need to find the place in the list. for k insertions, it will be O(n*k), and amortized of O(n*k/k) = O(n).

So the first solution is better for logn < k, and the second for logn > k

For better efficiency, you will probably want a sorted data structure that access elements in O(logn) such as a skip-list [which is basically a variation of linked list with additional information for easier accessing] or an avl tree

---

I had answered a similar question (99 % similar :) ) HERE

Now its for integer i guess, for string you can compare using std::string compare function or strcmp provided by C library

As per my opinion and seeing other answers it would be better for your application (if it needs sorted linked list ) to sort the data as you insert .

---

I think it doesn't actually make a difference how you do it, when you sort while inserting, you'll have O(n) on the insert, cause you might have to traverse the entire list before you find the right spot to insert.

However when you sort after adding all items to the list, you'll also have at least O(n) to move items around the list.

---

The simplest solution is to use what C++ already offers - std::list and std::list::sort:

#include <list>
#include <algorithm>
#include <iostream>
#include <string>

class Node {
public:
    Node(const std::string& data) : Data(data) {
    }
    std::string Data;
};

bool NodeLess(const Node& n1, const Node& n2) {
    return n1.Data < n2.Data;
}

void main() {

    std::list<Node> l;
    l.push_back(Node("d"));
    l.push_back(Node("c"));
    l.push_back(Node("a"));
    l.push_back(Node("b"));

    l.sort(NodeLess);

    for (auto i = l.begin(); i != l.end(); ++i)
        std::cout << i->Data.c_str() << " ";

}

If you can get away with it (memory-wise), you could also use std::vector to pre-sort the items (through std::sort) before inserting them into linked list, which could be somewhat faster.

You could also use std::map (or even std::set) instead of list - it will "auto-sort" your items as you insert them.

If you still want to use your own list, you could implement begin and end in it, and use std::stable_sort. Note that std::stable_sort expects bidirectional iterators, (unlike std::sort which expects random-access iterators). To implement bidirectional iterators in your list, you'll need to make it doubly-linked, not just singly-linked.

If you want to implement the sort itself, it is possible to implement both Quicksort and Mergesort on linked lists.