Member Avatar for group256

Hi everyone,

I'm dealing with a linked list that is supposed to be sorted. It's consisted of a series of strings which each of these strings are associated with 4 more strings. So, I'm looking for a way to sort this linked list with optimum way possible. I have some ideas myself:

1- Make 5 big array and copy everything into it.
Then sort the first string and make any change that is done to first to the rest of arrays.

2- Do the same algorithm using vectors.

3- Or do the same thing using linked list.

Let's say it's something like this, please bare in mind the numbers are in string format:

3 Tom Hanks 52 male actor
1 Sean Penn 50 male actor
2 Clive Owen 44 male actor

after sorting

1 Sean Penn 50 male actor
2 Clive Owen 44 male actor
3 Tom Hanks 52 male actor

Please let me know what could be the easiest and best way to do it.

  • 4 Contributors
  • 5 Replies
  • 254 Views
  • 19 Hours Discussion Span
  • Latest Post Latest Post by GDICommander

Dani AI

Generated

As framed it, the records carry a leading numeric key stored as text. The practical advice from , and points to two clean options depending on constraints:

  • Keep the list and use std::list::sort — it runs in O(n log n), is stable, and operates by merging nodes (no big temporary arrays). This is the simplest, safest choice when the data is already a linked list or when frequent splicing/insertion is required.
  • Move references/iterators into a std::vector and use std::sort — faster in practice for large N thanks to cache locality, then rebuild the list by splicing nodes in sorted order. This uses extra temporary storage (the vector) but typically outperforms list::sort for big datasets.

Implementation tips that matter in real code: parse the numeric key once when creating each node (store an int alongside the original string) so the comparator does not call stoi on every compare. Prefer stable comparisons if ties must preserve original order. Avoid O(n^2) sorts (bubble/selection) on large lists.

Example (concise) — store the parsed key and use list::sort:

struct Actor {
    int id;            // parsed numeric key
    std::string id_str;
    std::string name;
    std::string age, gender, role;
};

std::list<Actor> L = /* filled with parsed id */;
L.sort([](const Actor &a, const Actor &b){ return a.id < b.id; });

Final notes: use stoi (with try/catch) or a safe parser when converting strings; pick vector+std::sort when raw speed matters and memory is available; otherwise prefer list::sort — it’s the natural, memory-efficient choice for linked lists.

Recommended Answers

All 5 Replies

Member Avatar for Tom Gunn

You can use std::sort with a STL container, like a vector or a list.

sort() uses random access iterators, so it will not work on a list. STL lists use bidirectional iterators, but they also support their own sort method.

Member Avatar for group256

No other answer???

Member Avatar for Topi Ojala

One way springs to mind, might not be as effective as a linked list, but still...

First, create a struct of a data you want e.g. struct Actor, containing the info given to you. Then push these Actors in to a vector, deque, table, whatever you want, sorted by the first number ( string2int ).

Member Avatar for GDICommander

You can implement a sort strategy on your linked list, like bubble sort, quick sort, merge sort. Some strategies do not require an additionnal container for the answer.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.