Some parts of the state of the art are patented, others aren't.
For clearance, you have to know what's *patented*. Below is claim #1 of the patent the Google got stung for. There's no way any software developer, big or small, could know all the claims of the tens of thousands of software patents out there, *and* know all the details of the functionality of the software they ship so that they can do cross-analysis to find infringements.
a linked list to store and provide access to records stored in a memory of the system, at least some of the records automatically expiring, a record search means utilizing a search key to access the linked list, the record search means including a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed, and means, utilizing the record search means, for accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list.