2 Static arrays: Building your first data structure

 

In this chapter

  • a few basic ideas concerning data structures
  • introducing a fundamental data structure—arrays
  • the difference between statically and dynamically sized arrays
  • introducing typical operations that can be done on arrays
  • using arrays to solve a problem

In this chapter, we’ll begin to talk about how data structures work and how to implement them. The chapter is special in that it will slowly introduce you to the process we are going to follow throughout the book as we talk about the technology we are introducing. However, it will also familiarize you with some basic concepts that you will need for the rest of the book.

What is an array?

We will begin our journey to the land of data structures with arrays, specifically static arrays. Arrays organize data by holding a collection of elements and making them accessible through an index.

But right now, the most important question I want you to be able to answer is, why arrays? Let me explain by using an example.

Memory and drawers

First, we need to take a step back and talk about how memory is organized. For the sake of simplicity, I like to think of memory as a modular shelf holding removable drawers.

If the shelf structure is memory, then drawers are variables—a programming concept I assume you’re already familiar with. Think of memory as potential: if you want to use some memory, you can create variables, the drawers that can hold your data from which you can retrieve it.

When do I need an array?

Definitions: Statically vs. dynamically sized

Values and indexes

Initialization

Arrays in Python

Python lists vs. the array.array class

Indexing

Operations on arrays

A class for unsorted arrays

Adding a new entry

Removing an entry

Searching for a value

Traversal

Arrays in action