# Linear Probing in Python

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()


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.

• That's the kind of answer I was looking for, thank you very much :) – user74367 May 25 '15 at 19:11

## 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()