Arrays vs slices in Go

  • Array ([N]T) — fixed length, length is part of the type, value semantics. Rarely used directly.
  • Slice ([]T) — {ptr, len, cap} view into a backing array. Reference semantics for the underlying data. Used everywhere.
arr := [3]int{1, 2, 3}        // type: [3]int
sl  := []int{1, 2, 3}         // type: []int

s := make([]int, 0, 16)       // len=0, cap=16

Memory model

A slice header is a small struct:

+------+------+------+
| ptr  | len  | cap  |
+------+------+------+
   |
   v
[ a, b, c, d, e, ... ]   <- backing array

When you append past cap, Go allocates a new larger backing array and copies. Two slices that share a backing array see each other's writes.

Common operations and their complexity

Operation Complexity Notes
Index s[i] O(1) Bounds-checked.
Append a value Amortized O(1) Occasional O(n) reallocation.
Insert at index i O(n) Shifts elements.
Delete at index i, ordered O(n) s = append(s[:i], s[i+1:]...)
Delete at index i, unordered O(1) Swap with last, shrink.
Reverse O(n) Two-pointer swap.
Linear search O(n)
Binary search (sorted) O(log n) sort.Search / slices.BinarySearch.
Two-sum on sorted slice O(n) Two-pointer technique.

Why a separate arrayx package?

array is a reserved-feeling name and arr is too short. We use the package name arrayx to host generic algorithms over slices that aren't already in the standard library, so you can study them line-by-line.

The package provides:

  • Sum, Max, Min — reductions over ~int | ~float64 etc.
  • Reverse, Reversed
  • Contains, IndexOf
  • Insert, Remove, RemoveUnordered
  • BinarySearch (on sorted slice)
  • TwoSumSorted, RotateLeft

Run the tests

go test ./part2-dsa/ds/arrayx