Array (data structure) facts for kids

In computer science, an array is like a special container that holds a group of items. Imagine a row of lockers, where each locker holds something. In an array, all the items are usually the same size, and each one has a unique number or "index" that helps you find it. This way, computers can quickly figure out where each item is stored using a simple math rule. The simplest kind of array is a straight line of items, called a one-dimensional array.

For example, if you have an array of ten numbers, like 0 to 9, they might be stored one after another in the computer's memory. If the first number is at a certain address, the computer knows the next number will be at that address plus a fixed amount, and so on. This makes it very fast to find any number in the array.

Sometimes, a two-dimensional array is called a "matrix" because it looks like a grid, similar to how numbers are arranged in math. Arrays are super important in computer programming. Almost every computer program uses them. They also help build many other ways to organize data, like lists and strings (which are sequences of characters).

Arrays are useful because you can figure out where an item is stored while the program is running. This means a single piece of code can work with many items in an array, no matter how big the array is. Because of this, all items in an array usually need to be the same size and stored in the same way. The rules for finding items in an array are usually set when the array is created.

The word "array" can also mean a special type of data that most programming languages offer. This type lets you store many values or variables that you can pick out using one or more indexes. While arrays are often stored in a simple, organized way, some languages might use other methods like hash tables or linked lists to manage them.

What Are Arrays?

Arrays are fundamental tools in computer programming. They help organize information in a structured way. Think of an array as a series of connected boxes, each holding a piece of data.

Why Are Arrays Important?

Arrays are among the oldest and most important ways to store data. They are used in almost every computer program you can imagine. They are also used to build many other common data structures, like lists of items or sequences of text (called strings). Arrays are very good at using the computer's memory efficiently. In most modern computers, the memory itself is like a giant one-dimensional array of data "words," where each word has its own address.

How Arrays Work

Arrays are useful because you can calculate the exact location of any item inside them while the program is running. This means you can write a single piece of code that can go through and process any number of items in an array. For this to work well, all the items in an array need to be the same size and stored in the same way. The rules for finding items and their locations are usually set when the array is first used.

History of Arrays

Computers have used arrays since the very beginning. Early digital computers used special machine code to set up and access array structures. These were used for data tables, math calculations with vectors and matrices, and many other tasks.

John von Neumann, a famous computer pioneer, wrote the first program to sort an array in 1945. This happened while the first "stored-program computer" was being built. At first, finding items in arrays was done by changing the computer's own code. Later, special "index registers" and "indirect addressing" methods made it easier and faster. Some large computers from the 1960s even had special hardware to check if array indexes were within the correct limits.

Early programming languages like FORTRAN (1957), Lisp (1958), COBOL (1960), and ALGOL 60 (1960) all had ways to handle arrays with multiple dimensions. The C programming language (1972) also supported them. Later, C++ (1983) added even more flexible ways to create arrays.

How Arrays Are Used

Arrays are used for many different things in computing:

• Math and Science: They help represent mathematical vectors and matrices, which are like grids of numbers.
• Databases: Many databases, big and small, use one-dimensional arrays where each item is a "record" of information.
• Building Other Data Structures: Arrays are often used as the foundation for other ways to organize data, such as:

* Lists (like a shopping list) * Heaps (special tree-like structures) * Hash tables (for quick lookups) * Queues (like a line at a store) * Stacks (like a pile of plates) * Strings (sequences of characters, like words or sentences)

• Memory Management: Sometimes, large arrays are used to manage how a program uses its memory. This is especially true for older systems where other ways to get memory were not available.
• Controlling Program Flow: Arrays can even help control how a program runs. Instead of many `IF` statements, an array can hold instructions or pointers that tell the program what to do next.

Finding Items in an Array

When you store data in an array, you find individual items using an "index." This index is usually a positive whole number. The index acts like a map, pointing to where the item is stored.

How Indexing Works

There are a few common ways to number the items in an array:

• Zero-based indexing: The first item in the array is given the index 0. This is very common in languages like C, Java, and Lisp. It's simple because the index tells you how far away an item is from the very beginning of the array.
• One-based indexing: The first item is given the index 1. Some older languages or mathematical traditions use this.
• N-based indexing: Some programming languages let you choose the starting index. You could even use negative numbers or other types of data as indexes!

Arrays with Multiple Dimensions

Arrays can have more than one dimension. Imagine a grid or a cube.

• A one-dimensional array is like a single row or column of items. You only need one index to find an item. For example, `myArray[5]` would get the item at index 5.
• A two-dimensional array is like a table with rows and columns. You need two indexes to find an item, one for the row and one for the column. For example, `myArray[1][3]` might get the item in the second row, fourth column (if using zero-based indexing).
• A three-dimensional array is like a cube. You need three indexes.

The number of indexes needed to find an item is called the array's dimension or rank.

In standard arrays, each index must be within a certain range of numbers. The computer calculates the exact memory address of an item using a simple math formula based on its indexes.

One-Dimensional Arrays

A one-dimensional array is the simplest type. You use a single index to access its items. For example, if you declare `int numbers[10];` in a language like C, you create an array that can hold ten whole numbers. The indexes for this array would go from 0 to 9. So, `numbers[0]` is the first item, and `numbers[9]` is the last.

The computer finds an item by taking a starting memory address (called the "base address") and adding a calculated amount based on the item's index. If the indexes start at 0, the base address is simply the address of the very first item.

Multidimensional Arrays

For arrays with more than one dimension, the formula for finding an item becomes a bit more complex, but it's still a simple calculation. For a two-dimensional array with indexes `i` and `j`, the address would be the base address plus `(row_multiplier * i)` plus `(column_multiplier * j)`.

For example, `int grid[2][3];` creates a two-dimensional array with 2 rows and 3 columns. It can store 6 integer items. Even though it looks like a grid, the computer stores these items one after another in memory, usually row by row.

This formula is very fast because it only involves a few multiplications and additions. If the multipliers are powers of 2, the computer can even use faster "bit shifting" tricks instead of full multiplication.

How Arrays Are Stored in Memory

Often, array items are stored right next to each other in memory. This is called a "contiguous" layout. However, it's not always necessary. Sometimes, when you take a "slice" of an array (like picking out certain rows or columns), the new sub-array might not be stored all together.

How items are stored in row-major and column-major order.

For two-dimensional arrays, there are two main ways items are arranged in memory:

• Row-major order: (Used by C) All the items in the first row are stored together, then all the items in the second row, and so on. So, if you have a 3x3 grid, it would be stored as: item1, item2, item3 (first row), then item4, item5, item6 (second row), then item7, item8, item9 (third row).
• Column-major order: (Used by Fortran) All the items in the first column are stored together, then all the items in the second column, and so on. For the same 3x3 grid, it would be stored as: item1, item4, item7 (first column), then item2, item5, item8 (second column), then item3, item6, item9 (third column).

Storing items close together in memory is important for speed. When a computer needs to access data, it often loads a whole "chunk" of memory into a fast temporary storage area called a "cache." If array items are next to each other, the computer can load many items at once, making processing much faster. This is called "spatial locality."

Changing Array Size

Arrays that have a fixed size when they are created are called "static arrays." You can't add or remove items from them directly. However, you can create a new, bigger array, copy all the old items into it, and then add new items. This is how "dynamic arrays" work, which can grow or shrink as needed. Adding items to the end of a dynamic array is usually very efficient.

Some array systems don't actually change their memory size but keep track of how many items are currently being used. This makes them like dynamic arrays with a set maximum size.

How Efficient Are Arrays?

Finding or storing an item in an array is incredibly fast, taking a constant amount of time no matter how big the array is. Arrays also use memory very efficiently, with little extra space needed for each item. Sometimes, items can even be "packed" together to use even less memory. A good example is a bit array, where each item is just a single bit (a 0 or a 1).

Arrays are also great for "data parallelism," meaning many parts of a program can work on different parts of an array at the same time, speeding things up.

Arrays Compared to Other Data Structures

Arrays are just one way to organize data. Here's how they compare to some others:

• Dynamic Arrays: These are like regular arrays but can grow or shrink. They are efficient for adding or removing items at the end.
• Associative Arrays: These are useful when your indexes are very spread out (e.g., index 1 and index 2 billion). They save a lot of memory compared to a regular array that would need space for all the indexes in between.
• Balanced Trees: These structures are good if you need to quickly find items AND add or remove them anywhere in the structure. Finding an item takes a bit longer than an array, but adding/removing is faster than a dynamic array in the middle.
• Linked Lists: These are good for adding or removing items anywhere very quickly. However, finding an item in a linked list takes much longer than in an array because you have to go through each item one by one until you find the one you want.
• Iliffe Vector: This is a way to store a multidimensional array using a one-dimensional array of "pointers" (which are like addresses) to other arrays. This allows for "jagged arrays" where each row can have a different size.

A two-dimensional array stored as a one-dimensional array of one-dimensional arrays (rows).

Dimension of an Array

The "dimension" of an array tells you how many indexes you need to pick out a single item.

• A one-dimensional array is like a simple list. You need one index.
• A two-dimensional array is like a rectangle or a grid of data. You need two indexes (row and column).
• A three-dimensional array is like a block or cube of data. You need three indexes.

This is different from the total number of items in the array. For example, an array with 5 rows and 4 columns is two-dimensional, but it contains 20 items in total. A "three-dimensional vector" in math can be represented by a one-dimensional array that just has three items.

See Also

In Spanish: Vector (informática) para niños