Linear structures formulas

w = size of one element in bytes; L = lower bound of the index (L = 0 for a C array, giving Base + i*w); Base = address of the first element A[L].

cols = number of columns. C stores 2-D arrays row-major, and these notes assume row-major unless a question says column-major. For column-major, whole columns are stored one after another: Base + (j*rows + i)*w, where rows = number of rows.

Array declared as A[L1..U1][L2..U2]; n_c = U2 - L2 + 1 is the number of columns; Base = address of A[L1][L2]. Column-major: Base + ((j - L2)*n_r + (i - L1))*w with n_r = U1 - L1 + 1.

Holds for a 0-indexed n x n lower-triangular matrix (only entries with i >= j are stored) packed row by row into a 1-D array. Rows 0 to i-1 contribute 1 + 2 + ... + i = i(i+1)/2 entries. Address = Base + index*w. The packed array holds n(n+1)/2 elements.

n distinct elements pushed in a fixed order (1, 2, ..., n) through one stack, with pushes and pops interleaved freely. C_n (the nth Catalan number) counts the distinct output sequences: C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42.

SIZE = capacity of the underlying array. Every dequeue advances front by the same rule: front = (front + 1) mod SIZE.

a = links from the head to the cycle's start node; c = number of nodes in the cycle; d = the SMALLEST number of links followed forward from the first meeting node to the cycle start (0 to c-1). Holds when both pointers start at the head and slow moves 1 and fast moves 2 links per iteration. d equals a itself only when a < c. In every case, advancing a links from the meeting node reaches the cycle start, which is why the reset-to-head method below works.