Lesson Objective
- Describe the linked list data structure.
- Show how to create, traverse, add data to and remove data from a linked list.
mrahmedcomputing
KS3, GCSE, A-Level Computing Resources
Lesson 2. Linked Lists
Lesson Notes
Linked Lists
A linked list is a data structure that provides a foundation that other data structures can be built on such as stacks, queues, graph and trees.
It is a dynamic abstract data structure which can be implemented as an array.
Composed of “nodes”. Each node is composed of two parts:
- The data (which may be a complex data structure)
- A pointer (the index) of the next node
A start pointer identifies the first node in the list.
A nextfree pointer shows the index of the next free space in the array.
This is a diagram of a linear linked list.
This is a diagram of a double linked list.
This is a diagram of a circular linked list.
Traversing a Linked List
- Using Link Lists in an Array.
- Static data structures (arrays), data is stored contiguously.
- Linked list can be stored however. Example is alphabetical.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | |||
| 02 | |||
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | |||
| 08 |
Where are linked lists used?
Linked lists can be used for:
- Operating systems managing a processor.
- Image viewers to switch between previous and next images.
- Music players to store songs in a playlist.
- Web browsers to navigate backwards and forwards.
Adding to a Linked List
- Check for free memory. Error if not.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | |||
| 08 |
- Add data in node shown by free pointer.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | Gap | ||
| 08 |
- List empty? Data becomes first note. END.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | Gap | ||
| 08 |
- Run the list and identify correct position, by comparing the new value to each position.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | Gap | ||
| 08 |
- New node set to where previous node pointed.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | Gap | 03 | |
| 08 |
- Previous node would be set to point to the new node. At the same time. Next free pointer moves.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 07 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | Gap | 03 | |
| 08 |
Delete from a Linked List
- Check if the list is empty. Report error if empty.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | |||
| 08 |
- If the item to be deleted is the first item in the list, set the start point to next node.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | |||
| 08 |
- Go through the list and identify the item (Example = Cat) that needs to be removed.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | |||
| 08 |
- Set the previous nodes pointer to the next node.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 04 | |
| 06 | Cat | 04 | |
| 07 | |||
| 08 |
- Note, the item hasn't actually been deleted. Move the nextfree pointer to the deleted nodes location.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 04 | |
| 06 | Cat | 07 | |
| 07 | |||
| 08 |
- When new data is enter, it will overwrite the data stored in the deleted node (06) as it is mades as free.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | # | # | |
| 02 | # | # | |
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 04 | |
| 06 | Cat | 07 | |
| 07 | |||
| 08 |
Traversing a Linked List
- Check if the list is empty.
- Start at the start pointer node.
- Output the data item.
- Follow pointer to the next node.
- Repeat steps 3 and 4 until end reached.
| RAM | Address | Data | Pointer |
|---|---|---|---|
| 01 | |||
| 02 | |||
| 03 | Hat | null | |
| 04 | Dog | 03 | |
| 05 | Bat | 06 | |
| 06 | Cat | 04 | |
| 07 | |||
| 08 |