IB Computer Science · B2 · Programming
B2.2 Data structures
Describe arrays and lists, explain how elements are accessed, added and removed, compare arrays with linked lists, and trace stack and queue operations.
1/6An array stores items in numbered positions
- An array stores items in numbered positions
- A list can grow and shrink while the program runs
- Access is direct, but insertion and removal can need shifting
- A linked list connects separate nodes with pointers
- A stack removes the item that was added last
- A queue serves the item that has waited longest
- Check your recall
- Practice: 10 questions
Part 1 of 6: An array stores items in numbered positions
A row of numbered lockers lets you reach one bag without checking the others. An array works the same way. It stores a fixed number of items under one name.
Each position has an index, a whole number that starts at 0 in these notes. The item stored at an index is an element. An array called marks with five elements has indices 0 to 4.
Elements in an array usually share one data type. The size is fixed when the array is created.
Key terms · tap one for its definition
array
An array is a fixed-size, ordered collection of elements, usually of one data type, stored under a single name.
index
An index is the whole-number position of an element within an array or list.
Part 2 of 6: A list can grow and shrink while the program runs
A fixed size is a limit when you do not know how many items will arrive. A list removes that limit. It is an ordered collection that can change length as items are added or removed.
A shopping list is the everyday picture. You can add an item at the end or cross one out. Many languages let a list use indices, just like an array.
Arrays suit data of known size, such as the seven days of a week. Lists suit data of changing size, such as the messages in an inbox.
Key term
list
A list is an ordered collection of elements that can grow or shrink as elements are added or removed.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: A · Worked explanation
Part 3 of 6: Access is direct, but insertion and removal can need shifting
Because elements sit in order, changing the contents is not always one step. There are four basic operations.
- Access: read straight from its index
- Update: assign a new value, as in
- Insert: move later elements along, then store the new one
- Remove: delete the element, then move later elements back to close the gap
Access is fast because the index tells the computer exactly where to look. Insertion and removal in the middle are slower, because several elements must move.
Worked example
Inserting into a list
- Move 8 from index 2 to index 3. Start with the last element so nothing is overwritten.
- Move 6 from index 1 to index 2.
- Store 9 at index 1.
Answer: The list is now 4, 9, 6, 8.
Part 4 of 6: A linked list connects separate nodes with pointers
Shifting is the price of keeping elements side by side in memory. A linked list avoids it.
A linked list stores each item in a node. A node holds a value and a pointer, which is a reference to the next node. The nodes need not sit next to each other.
To insert an item, create a node and change the pointers around it. No other node moves. To reach the fifth item, however, you follow four pointers from the start.
An array compared with a linked list
- Feature
- Access by position
- Array
- Direct, using the index
- Linked list
- Follow pointers from the start
- Feature
- Insert in the middle
- Array
- Elements must shift
- Linked list
- Only pointers change
- Feature
- Extra memory
- Array
- None beyond the data
- Linked list
- One pointer per node
- Feature
- Size
- Array
- Usually fixed
- Linked list
- Grows as needed
Key terms · tap one for its definition
linked list
A linked list is a collection of nodes in which each node holds a value and a pointer to the next node.
node
A node is one element of a linked list, holding a value and a pointer.
pointer
A pointer is a reference that records where another item, such as the next node, is stored.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: B · Worked explanation
Part 5 of 6: A stack removes the item that was added last
Some tasks need access to only one end of a collection. A pile of plates is the usual picture.
A stack follows the rule last in, first out. You add and remove items at the same end, called the top. The last item pushed is the first item popped. Items beneath the top cannot be reached until the ones above are popped.
Push adds an item to the top. Pop removes the top item and returns it. The undo command in an editor works this way.
Worked example
Tracing a stack
- Push 4 gives 4.
- Push 9 gives 4, 9.
- Pop returns 9, leaving 4.
- Push 2 gives 4, 2.
- Pop returns 2, leaving 4.
- Pop returns 4, leaving an empty stack.
Answer: The pops return 9, 2 and 4, and the stack ends empty.
Key terms · tap one for its definition
stack
A stack is a collection that follows last in, first out, with items added and removed at one end called the top.
push
Push is the stack operation that adds an item to the top.
pop
Pop is the stack operation that removes the top item and returns it.
Part 6 of 6: A queue serves the item that has waited longest
A queue reverses the rule. People at a bus stop board in the order they arrive.
A queue follows the rule first in, first out. Items join at the back and leave from the front. No item can jump ahead of those already waiting.
Enqueue adds an item at the back. Dequeue removes and returns the item at the front. A printer handling jobs from many users uses a queue.
Worked example
Tracing a queue
- Enqueue A gives A.
- Enqueue B gives A, B with A at the front.
- Dequeue returns A, leaving B.
- Enqueue C gives B, C.
- Dequeue returns B, leaving C.
Answer: The dequeues return A then B, and C remains.
Key terms · tap one for its definition
queue
A queue is a collection that follows first in, first out, with items added at the back and removed from the front.
enqueue
Enqueue is the queue operation that adds an item at the back.
dequeue
Dequeue is the queue operation that removes the item at the front and returns it.
Check your recall[15 marks]
6 written questions. Answer each one in your head or on paper, then open the mark scheme.
- 1.Describe[2 marks]
Describe the purpose of an array.
Show mark schemeHide mark scheme
Model answer
An array stores several values, usually of one data type, under a single name. Each element can be reached directly by its index.
- 1 mark for stating that it stores a fixed number of related values under one name
- 1 mark for stating that elements are accessed by index
- 2.Outline[3 marks]
Outline how a new element is inserted at index 1 of a list.
Show mark schemeHide mark scheme
Model answer
Starting with the last element, move each element from index 1 onwards one place along. This makes space at index 1. Then store the new value there.
- 1 mark for stating that later elements are moved along
- 1 mark for stating that this starts from the last element so nothing is overwritten
- 1 mark for stating that the new value is stored at index 1
- 3.Compare[4 marks]
Compare arrays with linked lists for access by position and for insertion in the middle.
Show mark schemeHide mark scheme
Model answer
An array reaches any element directly using its index, but a linked list must follow pointers from the start. Inserting in the middle of an array needs later elements to shift, but a linked list only changes pointers.
- 1 mark for stating that an array gives direct access by index
- 1 mark for stating that a linked list follows pointers from the start
- 1 mark for stating that insertion in an array needs elements to shift
- 1 mark for stating that insertion in a linked list only changes pointers
- 4.Determine[3 marks]
Determine the final contents of a stack, with its top on the right, after these operations on an empty stack: push 5, push 8, pop, push 3, push 6, pop. State each value returned by pop.
Show mark schemeHide mark scheme
Model answer
The first pop returns 8. The second pop returns 6. The stack finally holds 5, 3 with 3 at the top.
- 1 mark for stating that the first pop returns 8
- 1 mark for stating that the second pop returns 6
- 1 mark for giving the final contents as 5, 3
- 5.Explain[2 marks]
Explain why a queue, rather than a stack, suits a ticket desk serving customers.
Show mark schemeHide mark scheme
Model answer
A queue is first in, first out, so the customer who arrived first is served first. A stack would serve the newest arrival first, which would be unfair.
- 1 mark for stating that a queue serves items in order of arrival
- 1 mark for explaining that a stack would serve the newest first, which is unfair
- 6.State[1 mark]
State the name of the operation that removes the item at the front of a queue.
Show mark schemeHide mark scheme
Model answer
Dequeue.
- 1 mark for stating dequeue

Practice this topic
10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)
0 right0 of 10 answered
Includes the 2 quick checks in the note above.
Easy[1 mark]
Show answer and explanation
Answer: C · Worked explanation
MediumState[1 mark]
Show answer and explanation
Answer: D · Worked explanation
MediumDetermine[1 mark]
Show answer and explanation
Answer: A · Worked explanation
MediumDetermine[1 mark]
Show answer and explanation
Answer: C · Worked explanation
Medium[1 mark]
Show answer and explanation
Answer: B · Worked explanation
HardDetermine[1 mark]
Show answer and explanation
Answer: D · Worked explanation
Hard[1 mark]
Show answer and explanation
Answer: B · Worked explanation
HardCalculate[1 mark]
Show answer and explanation
Answer: B · Worked explanation