Year 12 Lists and linked lists

OCR A Level - Lists and linked lists
1 / 22
next
Slide 1: Slide
ComputingFurther Education (Key Stage 5)

This lesson contains 22 slides, with interactive quizzes and text slides.

time-iconLesson duration is: 60 min

Items in this lesson

OCR A Level - Lists and linked lists

Slide 1 - Slide

Key objective - Learn what a linked list is and why we use them?
Key Objective - To learn what lists and linked lists are.


Learning objectives:
- Understand lists and linked lists
- Difference between dynamic and static data structures
- Implement list operations

Slide 2 - Slide

What is a list?

Slide 3 - Open question

Lists are data structures that can contain multiple data types.
The elements are stored in order and are indexed starting from 0.
They are stored non-contiguous, meaning they do not have to be stored next to each other in memory.

my_list = [10, 20, 30, 40, 50]

Slide 4 - Slide

There are other data structures similar to lists such as:

- Records
- Tuples
- Dictionaries

Slide 5 - Slide

Self investigation
Self Investigation
Visit W3 schools and research list methods in Python

Slide 6 - Slide

Operation
Initial List 
New List
my_list.insert(0, 5) 
[10, 20, 30, 40, 50]
my_list.append(60)
[10, 20, 30, 40, 50] 
my_list.remove(30)
[10, 20, 30, 40, 50] 
my_list.pop(1)
[10, 20, 30, 40, 50] 
my_list.reverse() 
[10, 20, 30, 40, 50] 
my_list.sort()
[40, 10, 30, 20, 50] 
[5,10,20,30,40,50]
[10,20,30,40,50,60]
[10,20,40,50

[10,30,40,50]
[50,40,30,20,10]
[10,20,30,40,50

Slide 7 - Drag question

Task:

You are tasked with developing a simple grade management system for a student. The program should allow the user to perform the following operations:
- Add a new grade to the list of grades.
- Remove a specific grade from the list.
- Compute the average of all grades in the list.
- Sort the grades either in ascending or descending order.
- Display the list of all grades the student has received.

Stretch:
- Write functions to find and display the highest and lowest grades in the list.
- Only allow grades between 0 and 100 (inclusive). Reject invalid inputs.
- Create a UI using simple loop that continuously asks the user for their choice of operation (add, remove, average, sort, display) and performs that operation until the user decides to exit.

Slide 8 - Slide

Slide 9 - Slide

Static Data Structure

- In languages like C/Java, lists (arrays) are fixed size
- This is a fixed data structure that is reserved at the start of the program. ​
- Eg we can set up a fixed size of list at the start of the program.​
- Static data structure fixed during program compilation​
- Memory locations fixed and can be accessed easily and quickly and are in a contiguous position in memory. ​
 - Memory is allocated even when it is not being used.​

Slide 10 - Slide

Dynamic memory allocation
Dynamic memory allocation uses linked lists and makes it much easier to remove

Slide 11 - Slide

Dynamic Data Structure

- In languages like Python, the list is dynamically resizable.
- More flexible and more efficient only use memory that is needed. 
- Access time may be slower due to indexing and pointer usage
- Memory can be allocated and deallocated as required while the program is running​
- Dynamic data structure can change during the running of the program ​

Slide 12 - Slide

Further reading

Slide 13 - Slide

Aspect
Static Data Structure
Dynamic Data Structure
Memory allocation
Size
Memory utilization
Access
Examples
Memory is allocated at compile-time
Faster
Fixed
Can be modified
Memory is allocated at run-time
Inefficient
Slower
efficient
Arrays, stacks and queues
Lists, hash tables and variable trees

Slide 14 - Drag question

Traversing link lists:

- Start at the node the pointer is pointing to (Start = )
- Output the item at the current node
- Follow the pointer to the next node repeating through each node until the end of the linked list.
- When the pointer field is empty/null it signals that the end of the linked list has been reached


Slide 15 - Slide

Starter pointer 2
(       Node        )
addr 2

Slide 16 - Slide

Addr
Data
Pointer
1
1
2
2
2
3
3
3
4
4
4
5
5
5
null

Slide 17 - Slide

Addr
Data
Pointer
1
Car
5
2
Bike
1
3
Plane
2
4
Walk
null
5
Run
4
Start = 2

Slide 18 - Slide

What data is third
in the list?

A
Car
B
Bike
C
Run
D
Walk

Slide 19 - Quiz

Is an example of a dynamic data structure
A
Fixed arrays
B
Stacks
C
Queues
D
Linked lists

Slide 20 - Quiz

numbers = [1,2,3,4,5] How would you delete 3?
A
numbers.pop(3)
B
numbers.pop(2)
C
numbers.clear(3)
D
numbers.del(3)

Slide 21 - Quiz

One thing I learned this lesson was?

Slide 22 - Open question