Access array item by index

Context

Generally speaking, in computer theory, one of the key points when working with arrays is that you can randomly access any element given its index with a constant time operation - noted O(1). Conversely, chained lists force you to iterate from first element to next ones until you reach the end.
Using BrainFuck, the operation to randomly access an element in an array given its index is actually more close to the list mechanism. Here is the global idea:

• Use our target index as a counter
• Move first element out of the array and decrease counter
• When counter is null, pick first element of the array
• Move everything back at the right place
• Move the current reverted stack to the left, to use constant memory
• Loop until all items are moved

We'll consider a zero-based index array in this example.

Initial state

• Memory: 0, 0, array, 0, index
• Cursor: on index
• Input: any

Process

• While index is not null
• Decrease index
• Go to array's first element
• Move it to the left
• Go back to index
• Loop invariant: (considering the array as the part delimited by 2 zeros) the value with position index in the array - as index is decreased as well as array size, from beginning
• When index equals 0, then array starts with our target element
• When index is null
• Move to array's first item
• Copy outside array
• Move to left first
• Then move outside array and twice
• Move one of the copies at the beginning of the array (actually, one cell left the beginning of the array)
• Move all array items back to their original position

Code 

[
  while index is not null

  -
  decrease index

  <<[<]>[-<+>]
  move last element outside array

  >[>]>
  go back to index
]
<<[<]>
go the array's first element

[-<+>]
move to the left

<[->>[>]>+>+<<<[<]<]
copy outside array twice

>>[>]>>
go to second copy

[-<<<[<]<+>>[>]>>]
move second copy back to where it comes

<<<[<]<[[->+<]<]>>[>]>
move all items back to their original position

Code (minified)

[-<<[<]>[-<+>]>[>]>]<<[<]>[-<+>]<[->>[>]>+>+<<<[<]<]>>[>]>>[-<<<[<]<+>>[>]>>]<<<[<]<[[->+<]<]>>[>]>

Final state

• Memory: 0,array, 0, array[index]
• Cursor: on result (array[index])
• Input: unchanged
• Output: unchanged

Example

Live 'Letter-by-index' example, that generates an alphabet array (from A to Z), reads a number N (should be between 1 and 26) in the input, pick the corresponding array item, and print the Nth letter of the alphabet.
Obviously, it would have been faster to simply read the number and add 64 to it, but pointless for this example :)

Copy value

Context

We already wrote some code to move a value - copy that destroys source.
To copy a value, we need to "destroy-copy twice" the target value, and optionally move one of the copies to the initial location.
So, to copy A we need to add 1 to the next 2 cells, A times - first cell will then be null; and move contents of third cell to first one.

Initial state

• Memory: A, 0, 0
• Cursor: first cell
• Input: any

Process

• While first cell is not null, decrease first and increase second / third by 1, and move back to first
• Loop invariant: second cell = third cell, and first+second = A
• When first cell equals 0, then second and third equals A
• Move third cell value to first one

Code

[->+>+<<]>>[-<<+>>]<<

Final state

• Memory: A, A, 0
• Cursor: first cell
• Input: any
• Output: unchanged

Move (pseudo-copy) value

Context

To move (and not copy) a value A to another cell (here, next one), we need to add 1 A times to an empty cell and decrease A by 1 each time

Initial state

• Memory: A, 0
• Cursor: first cell
• Input: any

Process

• While first cell is not null, decrease first and increase second by 1, move back to first cell
• Loop invariant: sum of both cells is A
• When first cell equals 0, then second equals A

Code

[->+<]

Final state

• Memory: 0, A
• Cursor: first cell
• Input: any
• Output: unchanged