liveBook · Manning

Array

As explained in Algorithms Every Programmer Should Know

An array is an indexed collection of elements stored in an ordered sequence.

Arrays store elements in contiguous memory and allow direct access by position. Inserting or deleting an element can require shifting others; linked lists instead require traversal to reach an element. section 1.4.2

Knapsack space optimization

A two-dimensional matrix tracks knapsack decisions, but if each state depends only on the row above and a cell up and to the left, a one-dimensional array can reduce memory use. This approach does not apply to every problem. section 7.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines contiguous storage and direct access, compares shifting costs, and describes one-dimensional optimization while noting it is not always possible.
Examples
Uses insertion at position three to illustrate shifting and knapsack states to illustrate one-dimensional storage.
What you can do after
Evaluate array-versus-linked-list tradeoffs and recognize when knapsack state dependencies permit one-dimensional storage.
How it connects
Connects arrays with linked lists through access and update tradeoffs, and with dynamic programming through knapsack state storage.

Also explained in

Compare how 48 books explain array →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.