The Self-Taught Computer Scientist

Chapter 10 Linked Lists
107
Search a Linked List
You can slightly modify your 
append
method from your 
LinkedList
class in the previous section to 
search for an item in a linked list:
def search(self, target):
current = self.head
while current.next:
if current.data == target:
return True
else:
current = current.next
return False
Your method, called 
search
, accepts one parameter called 
target
, which is the piece of data you 
are looking for. You iterate through your linked list, and if the current node’s data matches the target 
value, you return 
True
:
if current.data == target:
return True
If the current node’s data is not a match, you set 
current
to the next node in the linked list and 
continue iterating:
else:
current = current.next
If you reach the end of your linked list without a match, you know it is not in your list and return 
False
:
return False
You can see this algorithm in action by creating a linked list of 20 random numbers with values 
ranging from 1 to 30 and searching it for the number 10:
import random
a_list = LinkedList()
for i in range(0, 20):
j = random.randint(1, 30)
a_list.append(j)
print(j, end= " ")

---

Data Structures
108
Removing a Node from a Linked List
Removing a node from a linked list is another common technical interview question. You can also use 
a linear search to find a node in a linked list and delete it. You delete a node by changing the previous 
node’s pointer so it no longer points to the node you want to delete (Figure 10.8).
Here is how to remove a node from a linked list:
def remove(self, target):
if self.head == target:
self.head = self.head.next
return 
current = self.head
previous = None
while current:
if current.data == target:
previous.next = current.next
previous = current
current = current.next
Your method 
remove
accepts one parameter, 
target
, which is the piece of data that the node you 
want to remove contains.
Inside your method, first you handle what happens if the node you want to delete is the head of 
your list:
if self.head == target:
self.head = self.head.next
return