A sorted linked list

[hopesfall]

I'm using a linked list to store ints and want to implement a way to ensure that no duplicate ints can be put in my linked list. What are some (conceptual) ways to accomplish this? Right now I have a head pointer pointing to the first node in the list and I have methods to insert and remove items but how should I approach this problem of not allowing two of the same int in the list?

[Vins3Xtreme]

define a function that find if the value is present in list.

[mtrenkmann]

A linked list is not the right data structure for this.

Consider to use std::set or std::unordered_set. These data structures keep track of not storing duplicates. Insertion takes O(log n) for std::set and O(1) for std::unordered_set.

If you want to use a linked list you have to search the list every time before inserting the new item if it is not already present. Runtime O(n) - not good.

[aquaz]

Consider the list L is always sorted. Then when you want to insert a value v into it, there are two cases:
-the list is empty, insert v.
-else: from the head, find the first value which is superior to v, two cases:
---you find it: insert v just before this value
---you don't find it, insert v at the end of the list
Be careful, you have to keep track of the last element inferior to v if the list is not doubly-linked