CODEWITHSUNDEEP
c++performancealgorithmsearchlinked-list
Paweł
Paweł

Reputation: 143

How to improve linked list searching. C++

I have simple method in C++ which searchs for string in linked list. That works well but I need to make it faster. Is it possible? Maybe I need to insert items into list in alphabetical order? But I dont think it could help in serching list anymore. In list there is about 300 000 items (words).

int GetItemPosition(const char* stringToFind)
{
    int i = 0;
    MyList* Tmp = FistListItem;
    while (Tmp){
        if (!strcmp(Tmp->Value, stringToFind))
        {
            return i;
        }
        Tmp = Tmp->NextItem;
        i++;
    }
    return -1;
}

Method returns the position number if item found, otherwise returns -1. Any sugesstion will be helpfull.

Thanks for answers, I can change structure. I have only one constraint. Code must implement the following interface:

int Count(void);
int AddItem(const char* StringValue, int WordOccurrence);
int GetItemPosition(const char* StringValue);
char* GetString(int Index);
int GetOccurrenceNum(int Index);
void SetInteger(int Index, int WordOccurrence);

So which structure will be the in your opinion the most suitable?

Upvotes: 2

Views: 4622

Answers (6)

Jarlax
Jarlax

Reputation: 1576

The best option is to use faster data structure for storing strings:

  • std::map - red-black tree behind the scenes. Has O(logn) for search/insert/delete operations. Suitable if you want to store additional values with strings (for example - positions).
  • std::set - basically the same tree but without values. Best for case when you need only contains operation.
  • std::unordered_map - hash table. O(1) access.
  • std::unordered_set - hash set. Also O(1) access.

Note. But in all of these cases there is a catch. Complexity is calculated only based on n (count of strings). In reality string comparison is not free. So, O(1) becomes O(m), O(logn) becomes O(mlogn) (where m is maximal length of string). This does not matter in case of relatively short strings. But if this is not true consider using Trie. In practice trie can be even faster than hash table - each character of query string is accessed only once instead of multiple times. For hash table/set it's at least once for hash calculation and at least once for actual string comparison (depending on collision resolution strategy - not sure how it is implemented in C++).

Upvotes: 0

nonsensickle
nonsensickle

Reputation: 4528

The answer is no, you cannot improve the search without changing your data-structure.

As it stands, sorting the list will not give you a faster search for any random item.

It will only allow you to quickly decide if the given item is in the list by testing against the first item (which will be either the smallest or the largest entry) and this improvement is not likely to make a big difference.

So can you please edit your question and explain to us your constraints?

  • Can you use a completely different data structure, like an array or a tree? (as others have suggested)
  • If not, can you modify the way your linked list is linked?
  • If not, we will be unlikely to help you...

Upvotes: 1

Thomas Matthews
Thomas Matthews

Reputation: 57678

Rather than using a linear linked list, you may want to use a binary search tree, or a red/black tree. These trees are designed on minimizing the traversals to find an item.

You could also store "short cut links". For example, if the list is of strings, you could have an array of links of where to start searching based on the first letter.

For example, shortcut['B'] would return a pointer to the first link to start searching for strings starting with 'B'.

Upvotes: 1

IrineK
IrineK

Reputation: 115

I suggest hashing. Since you've already got a linked list of your own), you can try chaining with linked lists for collision resolution.

Upvotes: 1

Mert Akcakaya
Mert Akcakaya

Reputation: 3129

Searching a linked list is linear so you need to iterate from beginning one by one so it is O(n). Linked lists are not the best if you will use it for searching, you can utilize more suitable data structures such as binary trees.

Ordering elements does not help much because still you need to iterate each element anyway.

Wikipedia article says:

In an unordered list, one simple heuristic for decreasing average search time is the move-to-front heuristic, which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.

Another common approach is to "index" a linked list using a more efficient external data structure. For example, one can build a red-black tree or hash table whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again).

So in the first case you can slightly improve (by statistical assumptions) your search performance by moving items found previously closer to the beginning of the list. This assumes that previously found elements will be searched more frequently.

Second method requires to use other data structures.

If using linked lists is not a hard requirement, consider using hash tables, sorted arrays (random access) or balanced trees.

Upvotes: 5

akrasuski1
akrasuski1

Reputation: 840

Consider using array or std::vector as a storage instead of linked list, and use binary search to find particular string, or even better, std::set, if you don't need a numerical index. If for some reasons it is not possible to use other containers, there is not much possible to do - you may want to speed up the process of comparison by storing hash of the string along with it in node.

Upvotes: 2

Related Questions