Linear Probing in Python

Question

About to get back into coding, so I implemented linear probing in Python. How did I do? Anything unnecessary? Am I using "global" right? I originally wanted to use an array with a fixed length, but couldn't get it to work.

list = ["x", "x", "x", "x", "x", "x", "x"]
state = 0
def main():
#tests
 linearProbing(1)
 linearProbing(1)
 linearProbing(1)
 print(list)
def linearProbing(x):
 global state
 global list
 c = x % len(list)
 while state != 1:
 if list[c] == "x":
 list[c] = x
 state = 1
 elif c == 0:
 c = len(list) - 1
 else:
 c -= 1
 state = 0
if __name__ == '__main__':
 main()

Answer 1

Am I using "global" right?

It would be better to not use global at all, by wrapping this in a class, with state and list as attributes, so an instance could reference them with self.state, for example.

How did I do?

state is used as a boolean. So it should be a boolean value, set to False instead of 0 and True instead of 1 values.

list is not a good name for a variable, as it shadows a built-in with the same name.

A quick tip: you can write ["x", "x", "x", "x", "x", "x", "x"] simpler as ["x"] * 7. In any case, duplicating "x" in multiple places (first when you initialize list, and then later in linearProbing), is not great. It would be better to put the value "x" in a variable, say FREESPOT = "x", and reuse that everywhere.

Answer 2

Global variables

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 list(range(7)).

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.

Other issues

• There is no way to tell when the list is full (at which point the insertion silently fails, leading to probable data loss).
• Using "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.

Suggested solution

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
 return
 raise IndexError('list is full')
def main():
 # Tests
 lst = [None] * 7
 linear_probe(1, lst)
 linear_probe(1, lst)
 linear_probe(1, lst)
if __name__ == '__main__':
 main()