Scribe logoScribeNotes & practice
Sign inStart free
  1. Notes
  2. ›IB Computer Science
  3. ›B2 Programming
  4. ›B2.2 Data structures

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.

  • 6 min read
  • 6 parts
  • 10 questions
  • Draft
Start a Quick 5 on this topic→Jump to the 10 questions
1/6An array stores items in numbered positions
  1. 1An array stores items in numbered positions
  2. 2A list can grow and shrink while the program runs
  3. 3Access is direct, but insertion and removal can need shifting
  4. 4A linked list connects separate nodes with pointers
  5. 5A stack removes the item that was added last
  6. 6A queue serves the item that has waited longest
  7. Check your recall
  8. Practice: 10 questions
1

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.

Figure 1. Each element sits at a numbered index, and the first index is 0. The last index is one less than the size.

Common mistake

A five-element array has no marks[5]. Its last index is 4, which is one less than its size.

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 1 done

2

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.

Part 2 done

Quick check

One question on the part you just read

Easy

State the index of the first element in the arrays used in these notes.
Show answer and explanation

Answer: A · Worked explanation

In these notes the first element has index 0, so a five-element array has indices 0 to 4. Starting at 1 is how people usually count, but it is not how indices work here. A negative index and the size of the array are not valid positions for the first element.
3

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 marks[2]\texttt{marks[2]}marks[2] straight from its index
  • Update: assign a new value, as in marks[2] = 8\texttt{marks[2] = 8}marks[2] = 8
  • 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

A list holds 4, 6, 8 at indices 0, 1 and 2. Insert 9 at index 1.
  1. 1
    Move 8 from index 2 to index 3. Start with the last element so nothing is overwritten.
  2. 2
    Move 6 from index 1 to index 2.
  3. 3
    Store 9 at index 1.

Answer: The list is now 4, 9, 6, 8.

Part 3 done

4

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

FeatureArrayLinked list
Access by positionDirect, using the indexFollow pointers from the start
Insert in the middleElements must shiftOnly pointers change
Extra memoryNone beyond the dataOne pointer per node
SizeUsually fixedGrows as needed
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

Exam tip

When you compare structures, name the operation. Direct access favours arrays, while insertion and removal favour linked lists.

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.

Part 4 done

Quick check

One question on the part you just read

Easy

Which structure follows the rule last in, first out?
Show answer and explanation

Answer: B · Worked explanation

A stack adds and removes items at the top, so the last item pushed is the first popped. A queue follows first in, first out, which is the opposite rule. An array and a list store ordered elements by index and do not by themselves restrict where items are added or removed.
5

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

A stack starts empty. Its top is at the right-hand end. Perform push 4, push 9, pop, push 2, pop, pop. State each value returned by pop and the final contents.
  1. 1
    Push 4 gives 4.
  2. 2
    Push 9 gives 4, 9.
  3. 3
    Pop returns 9, leaving 4.
  4. 4
    Push 2 gives 4, 2.
  5. 5
    Pop returns 2, leaving 4.
  6. 6
    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 5 done

6

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.

Figure 2. A stack adds and removes at the top. A queue adds at the back and removes from the front.

Worked example

Tracing a queue

A queue starts empty. Perform enqueue A, enqueue B, dequeue, enqueue C, dequeue. State each item returned and the final contents.
  1. 1
    Enqueue A gives A.
  2. 2
    Enqueue B gives A, B with A at the front.
  3. 3
    Dequeue returns A, leaving B.
  4. 4
    Enqueue C gives B, C.
  5. 5
    Dequeue returns B, leaving C.

Answer: The dequeues return A then B, and C remains.

Common mistake

Pop and dequeue are not the same. Pop removes the newest item, while dequeue removes the oldest.

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.

Note read

Check your recall[15 marks]

6 written questions. Answer each one in your head or on paper, then open the mark scheme.

  1. 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. 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. 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. 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. 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. 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.

3.

Easy[1 mark]

What does each node of a linked list contain?
Show answer and explanation

Answer: C · Worked explanation

Each node holds a value and a pointer that records where the next node is stored. Linked lists do not use indices, so a node has no index to hold. A node with only a value could not be joined to the others, and a pointer to the first node alone would not store any data.
4.

Medium·State[1 mark]

An array called scores has 6 elements. State the index of its last element.
Show answer and explanation

Answer: D · Worked explanation

Indices start at 0, so six elements use indices 0 to 5. The last index is one less than the size. The value 6 confuses the size with the last index, and 7 would be beyond the end by two places. The value 4 is the index of the fifth element.
5.

Medium·Determine[1 mark]

A list holds 10, 20, 30, 40 at indices 0 to 3. The value 25 is inserted at index 2. Determine which element is then at index 3.
Show answer and explanation

Answer: A · Worked explanation

The elements from index 2 onwards move along by one place. So 25 goes to index 2, 30 moves to index 3 and 40 moves to index 4. The value 25 is at index 2, not 3. The value 40 would be at index 3 only if nothing had been shifted.
6.

Medium·Determine[1 mark]

A queue starts empty. Perform enqueue 3, enqueue 7, enqueue 1, dequeue, enqueue 9, dequeue. Determine which item is now at the front.
Show answer and explanation

Answer: C · Worked explanation

The first dequeue removes 3, leaving 7, 1. Enqueue 9 gives 7, 1, 9. The second dequeue removes 7, leaving 1, 9, so 1 is at the front. The value 9 is at the back, not the front. The values 3 and 7 have both been removed.
7.

Medium[1 mark]

A browser’s back button should return to the page visited most recently first. Which structure gives that behaviour directly?
Show answer and explanation

Answer: B · Worked explanation

Last in, first out matches returning to the most recent page, so a stack gives the behaviour directly. A queue would return the oldest page first, which is wrong. A linked list or an array could store the pages, but neither one by itself restricts removal to the newest item.
8.

Hard·Determine[1 mark]

An empty stack has its top at the right-hand end. Perform push 2, push 4, pop, push 6, push 8, pop, pop, push 1. Determine its contents from bottom to top.
Show answer and explanation

Answer: D · Worked explanation

Push 2 and push 4 give 2, 4. Pop removes 4. Push 6 and push 8 give 2, 6, 8. Two pops remove 8 and then 6, leaving 2. Push 1 gives 2, 1. The order 1, 2 reverses the stack, and 2, 6, 1 forgets the second of those two pops.
9.

Hard[1 mark]

A program often inserts items at the front of a long sequence and rarely reads items by position. Which choice is best, and why?
Show answer and explanation

Answer: B · Worked explanation

Inserting at the front of a linked list needs only a new node and a changed pointer, and the program rarely needs direct access. An array would have to shift every element on each insertion. A linked list uses extra memory for pointers, so the claim that it needs less memory is false.
10.

Hard·Calculate[1 mark]

An array holds 3, 6, 9, 12, 15 at indices 0 to 4. The element at index 1 is removed and later elements are shifted left to close the gap. Calculate how many elements must move.
Show answer and explanation

Answer: B · Worked explanation

The elements 9, 12 and 15 each move one place left, so three elements move. The value 4 wrongly counts the removed element or the first element as well. The value 2 leaves out one of the shifted elements. The value 1 counts only the deletion, ignoring the shifting.

Keep going

Next topicB2.3 Programming constructsPrevious topicB2.1 Programming fundamentals

More in B2 · Programming

  1. B2.1Programming fundamentalsNotes · 10 questions
  2. B2.2Data structuresNotes · 10 questions
  3. B2.3Programming constructsNotes · 10 questions
  4. B2.4Programming algorithmsNotes · 10 questions
  5. B2.5File processingNotes · 10 questions

All IB Computer Science topics →

Draft: written by Scribe and checked automatically, not yet by a subject reviewer.

Practice questions are original, written by Scribe and checked automatically for correctness.

Topic codes follow the official numbering. Not endorsed by IB Diploma Programme or any exam board.

On this page

0/6 read

  1. 1An array stores items in numbered positions
  2. 2A list can grow and shrink while the program runs
  3. 3Access is direct, but insertion and removal can need shifting
  4. 4A linked list connects separate nodes with pointers
  5. 5A stack removes the item that was added last
  6. 6A queue serves the item that has waited longest
  7. Check your recall
  8. Practice: 10 questions
All coursesScribeHow it worksPricingPrivacyTerms

Notes and questions are written by Scribe in our own words. Topic codes follow the official course numbering so you can find your place. Not produced or endorsed by the IB, College Board, AQA, OCR, Pearson Edexcel or any exam board.

© 2026 Scribe