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

Preface

Quite often, as software developers, when presented with a new task or challenge, we find ourselves grabbing code fragments or patterns that we are most familiar with. We typically make this choice because those fragments and patterns represent the shortest path between two points, namely, the client’s requirements and a deadline (also known as payday). However, this approach sometimes prevents us from learning new skills and ideas that will make us better and more efficient developers.

This book was written to give aspiring, new, or relatively inexperienced but busy developers an opportunity to step back and examine some of the fundamental concepts regarding data types and data structures. To that, we will examine how these types and structures are built, how they function, and how we can leverage them in our everyday applications. By doing so, we will gain new knowledge, skills, abilities and, hopefully, get some new ideas on how to leverage these basic components.

What this book covers

Chapter 1, Data Types: Foundational Structures, is a very brief overview of basic data types that comprise of data structures. This will be a rapid overview as even new programmers will already be familiar with some or most of these components. Attention will be paid to applications for each type, best practices, and a high-level comparison of any variations between platforms.

Chapter 2, Arrays: Foundational Collections, introduces you to the array data structure. This discussion will include specific details of the structure, including the typical applications, as well as specific concerns for each language. This is an important foundation chapter, as many of the subsequent data structures are built using arrays.

Chapter 3, Lists: Linear Collections, covers the specific details of the list data structure, including the most common functions associated with lists, typical applications for lists, and specific concerns for each language.

Chapter 4, Stacks: LIFO Collections, introduces you to the stack data structure. In this chapter, the reader will learn the specific details of the structure including the most common functions associated with stacks, typical applications for stacks, and specific concerns for each language.

Chapter 5, Queues: FIFO Collections, talks about the specific details of the queue data structure, including the most common functions associated with queues, typical applications for queues, and specific concerns for each language.

Chapter 6, Dictionaries: Keyed Collections, delves into the specific details of the dictionary data structure, including the most common functions associated with dictionaries, typical applications for dictionaries, and specific concerns for each language.

Chapter 7, Sets: No Duplicates, discusses the specific details of the set data structure, including the foundations of set theory; the most common functions associated with sets, typical applications for sets, and specific concerns for each language.

Chapter 8, Structures: Complex Types, explores the specific details of structures or the struct data structure, including most common functions associated with structs, typical applications for structs, and specific concerns for each language.

Chapter 9, Trees: Non-Linear Structures, talks about the specific details of the abstract tree structure with particular emphasis on the binary tree. This discussion will include an examination of the most common functions associated with trees, typical applications for trees, and specific concerns for each language.

Chapter 10, Heaps: Ordered Trees, delves into the specific details of the heap data structure, including the most common functions associated with heaps, typical applications for heaps, and specific concerns for each language.

Chapter 11, Graphs: Values with Relationships, introduces the specific details of the graph data structure, including the most common functions associated with graphs, typical applications for graphs, and specific concerns for each language.

Chapter 12, Sorting: Bringing Order Out of Chaos, is an advanced chapter that focuses on the concept of sorting. This concept will be introduced by examining several common and popular sorting algorithms, with particular attention being paid to operational cost, common applications, and concerns accompanying each algorithm.

Chapter 13, Searching: Finding What You Need, is also an advanced chapter that focuses on the concept of searching for data within a data structure. This concept will be introduced by examining several common and popular searching algorithms, with particular attention being paid to operational cost, common applications, and concerns for each language.

What you need for this book

In order for you to take full advantage of this book, you will need a modern computer. The code examples in this book are broad enough that you can use a Mac, PC, or even a Linux machine. Ultimately, you will also need a functioning development environment, such as Visual Studio, XCode, Eclipse, or NetBeans, that can run on your chosen development machine.

Who this book is for

This book is for anyone who wants to improve their knowledge and skills in fundamental programming concepts related to data structures. More specifically, this book is for new or self-taught programmers or programmers who range in experience from relatively new to having three or four years of experience. This book focuses on the four languages most commonly used in mobile software development, so the audience also includes those interested in mobile software development. The reader should have a basic understanding of programming, including how to create console applications, and how to use an Integrated Development Environment, or IDE, for their preferred development language

Conventions

In this book, you will find a number of text styles that distinguish between different kinds of information. Here are some examples of these styles and an explanation of their meaning.

Each chapter of this book will also include a case study, or similar code example, that will be broken down and detailed to explain how the data structure is applied.  As such, this book is full of code examples.

A block of code is set as follows:

    public boolean isEmpty()
    {
        return this._commandStack.empty();
    }

When we wish to draw your attention to a particular part of a code block, the relevant lines or items are set in bold:

    func canAddUser(user: EDSUser) -> Bool 
    { 
        if (_users.contains(user)) 
        { 
            return false; 
        } else {
            return true; 
    }

New terms and important words are shown in bold. Words that you see on the screen, for example, in menus or dialog boxes, appear in the text like this: "The first validation method, isFull(), checks if our stack has reached its capacity."

We will also discuss algorithms and mathematical concepts related to algorithms in this text. Whenever operational cost values written in Big-O notation are shown they appear as follows: "This is small consolation, however, because the selection sort algorithm still has an O(n2 ) complexity cost."

Likewise, when mathematical formulas and algorithms are used, they will appear as follows: "Our algorithm will find the smallest value in S[0...4], which in this case is 3, and place it at the beginning of S[0...4]."

Note

Warnings or important notes appear in a box like this.

Tip

Tips and tricks appear like this.

Reader feedback

Feedback from our readers is always welcome. Let us know what you think about this book-what you liked or disliked. Reader feedback is important for us as it helps us develop titles that you will really get the most out of. To send us general feedback, simply e-mail [email protected], and mention the book's title in the subject of your message. If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, see our author guide at www.packtpub.com/authors.

Customer support

Now that you are the proud owner of a Packt book, we have a number of things to help you to get the most from your purchase.

Downloading the example code

You can download the example code files for this book from your account at http://www.packtpub.com. If you purchased this book elsewhere, you can visit http://www.packtpub.com/support and register to have the files e-mailed directly to you.

You can download the code files by following these steps:

  1. Log in or register to our website using your e-mail address and password.

  2. Hover the mouse pointer on the SUPPORT tab at the top.

  3. Click on Code Downloads & Errata.

  4. Enter the name of the book in the Search box.

  5. Select the book for which you're looking to download the code files.

  6. Choose from the drop-down menu where you purchased this book from.

  7. Click on Code Download.

Once the file is downloaded, please make sure that you unzip or extract the folder using the latest version of:

  • WinRAR / 7-Zip for Windows

  • Zipeg / iZip / UnRarX for Mac

  • 7-Zip / PeaZip for Linux

The code bundle for the book is also hosted on GitHub at https://github.com/PacktPublishing/Everyday-Data-Structures. We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!

Errata

Although we have taken every care to ensure the accuracy of our content, mistakes do happen. If you find a mistake in one of our books-maybe a mistake in the text or the code-we would be grateful if you could report this to us. By doing so, you can save other readers from frustration and help us improve subsequent versions of this book. If you find any errata, please report them by visiting http://www.packtpub.com/submit-errata, selecting your book, clicking on the Errata Submission Form link, and entering the details of your errata. Once your errata are verified, your submission will be accepted and the errata will be uploaded to our website or added to any list of existing errata under the Errata section of that title.

To view the previously submitted errata, go to https://www.packtpub.com/books/content/support and enter the name of the book in the search field. The required information will appear under the Errata section.

Piracy

Piracy of copyrighted material on the Internet is an ongoing problem across all media. At Packt, we take the protection of our copyright and licenses very seriously. If you come across any illegal copies of our works in any form on the Internet, please provide us with the location address or website name immediately so that we can pursue a remedy.

Please contact us at [email protected] with a link to the suspected pirated material.

We appreciate your help in protecting our authors and our ability to bring you valuable content.

Questions

If you have a problem with any aspect of this book, you can contact us at [email protected], and we will do our best to address the problem.