The definition here is that none of the operations can result in blockage. These are always non-blocking. There is always some implication that these are thread-safe even though they don’t use locks.
Actual Definition
If any thread performing an operation gets suspended during the operation, then other threads accessing the data structure are still able to complete their tasks.
This is distinct from the idea of waiting. These are typically quite complicated.
Lock-free algorithms are about ensuring there is forward progress in the system and not really specifically about speed. A particular algorithm implementation might be faster under lock-free algorithms. For example, if the compare and swap operation to replace a list head is faster than the mutex lock and unlock, you prefer the lock-free algorithm.