Linked lists, queues, procedures, functions and text files
Watch the whole lecture free
Make a free account to watch every lecture to the end: 6 practice questions, 2 real past-paper questions with the answers explained, the mistakes that lose marks, the full-marks tip, a one-card summary and a quick quiz.
That was the teaching part. The rest of this lecture is free with an account: 6 practice questions, 2 real past-paper questions with the answers explained, the mistakes that lose marks, the full-marks tip, a one-card summary and a quick quiz.
No password needed now: we email you a link to set one. Already have an account? Sign in, then come back to this page.
The teaching part (1 min) is free to watch. A free account opens the whole lecture: 6 practice questions, 2 real past-paper questions with the answers explained, the mistakes that lose marks, the full-marks tip, a one-card summary and a quick quiz.
What this lecture covers
- Order without moving anything
- A linked list
Read the transcript of the teaching part
Last time
Before we start: last time, in Test data, testing methods, types of error and writing pseudocode algorithms, you learned these points. Here they are again on one card. Keep them in mind, because today builds on them.
Order without moving anything
Imagine a list in alphabetical order, and a new name must go in the middle. With an ordinary array you would shift everything along. A linked list avoids that: each item says where the next one is. A queue is the other idea: join at the back, leave from the front. Both are tools for keeping order.
A linked list
A linked list uses two arrays: Data holds the items, and Pointer holds, for each item, the index of the next one. A start pointer gives the first. Say Data is DOG, CAT, EEL, ANT in positions 1 to 4. Start is 4. Pointers: 3, 1, 0, 2. Follow from 4: ANT, then position 2, CAT, then 1, DOG, then 3, EEL, then 0. Zero is the null pointer, meaning the end.
How often it comes up
How often Cambridge has asked each part, counted by ExamYard from every past paper in its question bank: Linked lists · Procedures, functions and parameters · Reading and writing text files.
The whole chapter: Files, Data Structures and Modules.
Chapter 10: Data types and structures
- Linked lists, queues, procedures, functions and text files 6 min
- Stacks, text files and writing modules 6 min
Also for A Level Computer Science 9618
Which topics come up most in A Level Computer Science 9618 past papers, counted from every paper since 2004: Paper 1 topic frequency, Paper 2 topic frequency.