Addressing Arrays and Linked Lists: 25-Comp-A3 Computer Architecture, May 2013, Q2

Question 2: Addressing Arrays and Linked Lists (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) A 256-element array, 2 bytes/element, first element at address BASE, byte-addressable memory. (b) A 3-node singly-linked list (1)→(2)→(3); each node = 4-byte integer + 4-byte "next" pointer; big-endian storage; node (1) starts at 0x100, nodes packed back-to-back in list order.

Find. (a) A formula for the address of the N-th array element. (b) The exact byte-by-byte memory contents of all three list nodes.

Approach. (a) apply the standard array-indexing rule, address = base + index × element size. (b) lay out each 8-byte node back-to-back starting at 0x100, and write each 4-byte field in big-endian order (most-significant byte at the lowest address).

Check: "the N-th element" is read as 0-based (N = 0 is the first element, already sitting at BASE), matching how array indices are normally defined. If the exam intends 1-based counting (the "first" element is N = 1), every address below shifts to BASE + 2(N−1).

Part (a) — address of the N-th element. Each element occupies 2 bytes, so element $N$ begins $2N$ bytes past the array's own start: $$\text{address}(N)=\boxed{BASE+2N}\qquad N=0,1,\dots,255.$$
Part (b) — big-endian layout of the 3-node list. Each node is $4+4=8$ bytes, so with node (1) at 0x100, packing back-to-back gives node (2) at 0x100+8=0x108 and node (3) at 0x108+8=0x110. Node (3) is the tail, so its "next" pointer is NULL (0x00000000). Writing each 4-byte field big-endian (MSB at the lowest address of the field) gives the table below.

Fig. Q2(b) — linked-list layout in memory (byte contents in the table below).

Exact big-endian byte contents (element size = 8 bytes: int + next-pointer)
Address range	Field	Bytes (hex, MSB first)
0x100–0x103	node (1) int = 1	00 00 00 01
0x104–0x107	node (1) next → 0x108	00 00 01 08
0x108–0x10B	node (2) int = 2	00 00 00 02
0x10C–0x10F	node (2) next → 0x110	00 00 01 10
0x110–0x113	node (3) int = 3	00 00 00 03
0x114–0x117	node (3) next = NULL	00 00 00 00

Final results — Question 2
Part	Result
(a) N-th element address	$BASE+2N$ (0-based N)
(b) node addresses	(1)=0x100, (2)=0x108, (3)=0x110; full byte map above

Topic: Array indexing and endianness in a byte-addressable memory.

Key relations: $\text{addr}(N)=\text{base}+N\times\text{element size}$; big-endian stores a multi-byte value's most-significant byte at the lowest address (little-endian would reverse every 4-byte field above).

Why this works: a byte-addressable machine numbers every byte, so an array of fixed-size elements is just base-plus-stride addressing, and any multi-byte field needs an explicit byte-ordering convention because the hardware bus moves one byte (or word) at a time.

Common pitfall: off-by-one indexing (0-based vs. 1-based "N-th element"); reversing byte order (writing little-endian when big-endian was specified); forgetting the pointer field is itself a 4-byte quantity subject to the same endianness rule as the integer field.

Source: Patterson & Hennessy, Computer Organization and Design, 6th ed., Ch.2 §2.3 (byte order/endianness), Ch.3 (data representation).

Question 2 of 6: Addressing Arrays and Linked Lists

Question 2: Addressing Arrays and Linked Lists (20 marks)