list should not be global, because it limits your function to ever working on one global list, hindering code reuse. Instead, it should be passed as a parameter. Since
list is the name of a built-in type in Python, you should probably avoid using it as the name of a variable — that would break code like
state should absolutely not be global. It's just a flag that is used locally within the
linearProbing() function, and it's always 0 whenever
linearProbing() is not executing. Better yet, just don't use flag variables for controlling program flow (see solution below).
Especially if you are a beginner, you should just consider
global to be taboo, and avoid using it altogether. There is always a better way.
- There is no way to tell when the list is full (at which point the insertion silently fails, leading to probable data loss).
"x" as a special value to indicate an available slot is weird. Typically,
None would be used for that purpose.
- Counting loops are typically written using
for … in range(…).
- You can take advantage of the fact that negative list indices refer to positions relative to the end of the list.
- Write a docstring. It's a good habit.
def linear_probe(x, lst):
Put integer x into a list at position x % len(lst), probing
backwards until a free spot is found. Raise IndexError if
the list is full.
preferred_index = x % len(lst)
for c in range(preferred_index, preferred_index - len(lst), -1):
if lst[c] is None:
lst[c] = x
raise IndexError('list is full')
lst = [None] * 7
if __name__ == '__main__':