Year 12 Lists and linked lists

• Computing
• Further Education (Key Stage 5)

OCR A Level - Lists and linked lists

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

What is a list?

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]

There are other data structures similar to lists such as:

- Records

- Tuples

- Dictionaries

Self investigation

Self Investigation

Visit W3 schools and research list methods in Python

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

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.

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

Dynamic memory allocation

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

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 ​

Further reading

CLICK HERE

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

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

Starter pointer 2

(       Node        )

addr 2

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

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

Start = 2

What data is third
in the list?

1. Car
2. Bike
3. Run
4. Walk

Is an example of a dynamic data structure

1. Fixed arrays
2. Stacks
3. Queues
4. Linked lists

numbers = [1,2,3,4,5] How would you delete 3?

1. numbers.pop(3)
2. numbers.pop(2)
3. numbers.clear(3)
4. numbers.del(3)

One thing I learned this lesson was?