# Linear Search of Linked List in Python

A linked list is a fundamental data structure in computer science and a common subject of technical job interview questions and programming challenges. One of the simplest challenges, and a great starting point for learning linked lists, is to search a linked list to see if it contains a given value.

## Linear Search of Linked Lists

Unlike arrays, which allow random access to individual items, linked lists are a chain of nodes that have to be traversed one-by-one to see if the list contains a given value. Each node typically contains a value and a pointer to the next node. The one-by-one traversal of nodes to find a value is called linear search and the worst case performance of linear search is O(n). As the number of nodes in the linked list increases so does the worst case performance. As you may expect, linked lists are typically not an ideal data structure for algorithms that repeatedly search a large number of values.

There are different ways to implement linked lists, but fundamentally it comes down to a class or struct typically called a Node that contains a value and a pointer to another Node. For simplicity, here is a sample Node class in Python.

```class Node(object):
def __init__(self, value: int, next_node: "Node" = None):
self.value = value
self.next_node = next_node

def __repr__(self):
return "Node <{}>".format(self.value)
```

We can create a linked list by chaining a number of Nodes together. Here is a linked list in Python that contains the integers 1 through 5.

`linked_list = Node(1, Node(2, Node(3, Node(4, Node(5)))))`

Once we have the linked list we can pass it to a function that performs linear search to see if it contains a value. For simplicity, the search function will return True if the linked list contains a value or False if it doesn't. The function accepts the head (first Node) of the linked list as well as an integer value to find.

```def find(head: Node, value: int) -> bool:
"""Returns True if value in linked list, otherwise False."""

while current_node is not None:
if current_node.value == value:
return True

current_node = current_node.next_node

return False```

The linear search algorithm for the linked list visits each Node one-by-one to see if its value is equal to the search value. If the value is found, it returns True. If the linear search algorithm loops through all Node instances in the linked list and comes up empty, it returns False.

The complete solution in Python for finding a value in a linked list using linear search is as follows.

```class Node(object):
def __init__(self, value: int, next_node: "Node" = None):
self.value = value
self.next_node = next_node

def __repr__(self):
return "Node <{}>".format(self.value)

def find(head: Node, value: int) -> bool:
"""Returns True if value in linked list, otherwise False."""

while current_node is not None:
if current_node.value == value:
return True

current_node = current_node.next_node

return False

if __name__ == '__main__':
linked_list = Node(1, Node(2, Node(3, Node(4, Node(5)))))
for i in range(1, 6): 