Book Image

Everyday data structures

By : William Smith
Book Image

Everyday data structures

By: William Smith

Overview of this book

Explore a new world of data structures and their applications easily with this data structures book. Written by software expert William Smith, you?ll learn how to master basic and advanced data structure concepts. ? Fully understand data structures using Java, C and other common languages ? Work through practical examples and learn real-world applications ? Get to grips with data structure problem solving using case studies
Table of Contents (20 chapters)
Everyday Data Structures
Credits
About the Author
About the Reviewer
www.PacktPub.com
Customer Feedback
Preface
Free Chapter
1
Data Types: Foundational Structures

Linear search


A search, also called a sequential search, is simply a loop through a collection with some kind of comparison function to locate a matching element or value. Most linear searches return a value representing the index of the matching object in the collection, or some impossible index value such as -1 when an object is not found. Alternative versions of this search could return the object itself or null if the object is not found.

This is the simplest form of search pattern and it carries an O(n) complexity cost. This complexity is consistent whether the collection is in random order or if it has already been sorted. In very small collections linear searches are perfectly acceptable and many developers make use of them daily. However, when working with very large collections it is often beneficial to find alternatives to this sequential search approach. This is particularly true when working with lists of very complex objects, such as spatial geometries, where search or analysis...