Learning Objectives
By the end of this lesson, you will be able to:
- Show understanding that an ADT is a collection of data and a set of operations on those data
- Show understanding that a stack, queue and linked list are examples of ADTs
- Use a linked list to store data
- Describe how a linked list can be implemented using arrays
- Describe key features of linked lists and justify their use for a given situation
- Add, edit and delete data from linked lists
- Implement linked lists using two 1D arrays or record data types
- Understand and use pointers, start pointers, and null pointers in linked lists
Key Terms
Abstract Data Type (ADT)
A collection of data and a set of operations on those data
Linked List
A list containing several items in which each item points to the next item in the list
Node
An element of a linked list consisting of data items and a pointer
Pointer
A variable that stores the address of the node it points to
Null Pointer
A pointer that does not point at anything
Start Pointer
A variable that stores the address of the first element in a linked list
Heap (Free List)
Empty positions in the array that must be managed as an empty linked list
FreeListPtr
Stores the index where the next value will be stored in the array implementation
Record Data Type
A composite user-defined data type with multiple fields
Linked List Basics
A linked list is a list containing several items in which each item in the list points to the next item in the list. In a linked list, a new item is always added to the start of the list.
What is a Node?
An element of a list is called a node. A node consists of:
- Data items - The actual information stored in the node
- Pointer - A variable that stores the address of the next node
Key Components
Start Pointer
A variable that stores the address of the first element in the linked list
Null Pointer
A pointer that does not point at anything (marks the end of the list)
Heap / Free List
Empty positions in the array that must be managed as an empty linked list
A simple linked list with 3 nodes
Real-Life Example: Treasure Hunt Game
Imagine a treasure hunt game where each clue points to the location of the next clue:
• Each clue contains information (data) and points to the next clue (pointer)
• The first clue is accessed via the start pointer
• The last clue points to NULL (treasure found!)
Just like in a linked list, you must follow the pointers from one clue to the next to reach the end.
Linked List Visualization
Interact with this simple linked list. Add nodes to the beginning or end, and see how pointers are updated.
How it works:
- Add to Start: New node becomes first, its pointer points to old first node
- Add to End: Traverse to last node, change its pointer from NULL to new node
- Start Pointer: Always points to the first node in the list
- Null Pointer: Marks the end of the list (no next node)
Check Your Understanding: Linked List Basics
1. What are the two main components of a node in a linked list? [2 marks]
Answer
- [1 mark] Data items - the actual information stored in the node
- [1 mark] Pointer - a variable that stores the address of the next node
- [Additional] Together, these allow nodes to be linked together in a chain
2. What is the purpose of a null pointer in a linked list? [1 mark]
Answer
- [1 mark] To mark the end of the list (indicates there is no next node)
- [Additional] Without a null pointer, we wouldn't know when we've reached the end of the list
3. What does the start pointer store? [1 mark]
Answer
- [1 mark] The address (or index) of the first node in the linked list
- [Additional] Without a start pointer, we wouldn't know where the list begins
4. In a linked list, where is a new item always added? [1 mark]
Answer
- [1 mark] To the start of the list
- [Additional] This makes insertion very efficient as we only need to update the start pointer
5. Explain what happens when you add a node to the beginning of a linked list. [2 marks]
Answer
- [1 mark] The new node's pointer is set to point to the current first node
- [1 mark] The start pointer is updated to point to the new node
- [Additional] This takes constant time O(1) regardless of the list size
Linked List Operations
Linked lists support several fundamental operations: adding nodes, deleting nodes, and traversing the list. Understanding these operations is crucial for working with linked lists.
Adding Nodes
Adding to the Beginning
A new node is inserted at the beginning of the list:
- Content of startPointer is copied into the new node's pointer field
- startPointer is set to point to the new node
Adding to the End
A new node is inserted at the end of the list:
- The pointer field of the last node points to the new node
- The pointer field of the new node contains the null pointer
Deleting Nodes
Deleting the First Node
To delete the first node in the list:
- Copy the pointer field of the node to be deleted into StartPointer
- The node becomes available in the free list (heap)
Deleting the Last Node
To delete the last node in the list:
- Set pointer field for the previous node to null pointer
- The last node becomes available in the free list
Activity 1: Trace Linked List Operations
Trace the following operations on a linked list that is initially empty:
- Add "Apple" to the list
- Add "Banana" to the beginning
- Add "Cherry" to the end
- Delete the first node
- Add "Date" to the beginning
- What is the final order of nodes in the list?
Solution:
-
Start: Empty list
StartPointer = 0 (NULL) -
Add "Apple":
Start → Apple → NULL -
Add "Banana" to beginning:
Start → Banana → Apple → NULL -
Add "Cherry" to end:
Start → Banana → Apple → Cherry → NULL -
Delete first node:
Start → Apple → Cherry → NULL -
Add "Date" to beginning:
Start → Date → Apple → Cherry → NULL - Final order: Date → Apple → Cherry
Linked List Operations Simulator
Step through linked list operations visually. See how pointers are updated when adding or deleting nodes.
Array Representation
| Index | Data | Pointer |
|---|
How array implementation works:
- Data array: Stores the actual node values
- Pointer array: Stores the index of the next node
- StartPointer: Index of the first node in the list
- FreeListPtr: Index where the next new node will be stored
- Pointer value 0: Represents NULL (end of list)
Real-Life Example: To-Do List Application
A simple to-do list app could use a linked list to manage tasks:
New urgent tasks are added to the beginning, while less urgent ones can be added to the end. Completed tasks are removed from the beginning (assuming you work through the list in order).
Check Your Understanding: Linked List Operations
1. Describe the steps to add a node to the beginning of a linked list. [2 marks]
Answer
- [1 mark] Copy the content of startPointer into the new node's pointer field
- [1 mark] Set startPointer to point to the new node
- [Additional] This makes the new node the first node, linking it to the previous first node
2. How do you delete the first node in a linked list? [2 marks]
Answer
- [1 mark] Copy the pointer field of the node to be deleted into StartPointer
- [1 mark] The deleted node becomes available in the free list (heap)
- [Additional] This makes the second node become the new first node
3. What is the main advantage of adding nodes to the beginning of a linked list? [2 marks]
Answer
- [1 mark] It's very fast (constant time O(1))
- [1 mark] Only requires updating the start pointer and the new node's pointer
- [Additional] No need to traverse the entire list, unlike adding to the end
4. When deleting the last node, what must be done to the previous node's pointer? [1 mark]
Answer
- [1 mark] Set it to null pointer (0)
- [Additional] This marks it as the new end of the list
5. What happens to a deleted node in terms of memory management? [2 marks]
Answer
- [1 mark] It becomes part of the free list (heap)
- [1 mark] It can be reused when a new node needs to be added
- [Additional] The FreeListPtr tracks available nodes for reuse
Linked List Implementation
Linked lists can be implemented using two main methods: using two 1D arrays or using a record data type. Both methods track data and pointers separately.
Implementation Methods
Method 1: Two 1D Arrays
This method uses two separate arrays:
- Data Array: Stores the actual data values (strings, integers, etc.)
- Pointer Array: Stores the index of the next node in the list
- Elements at the same index in both arrays represent one node
Example:
| Index | Data | Pointer |
|---|---|---|
| 1 | Biology | 2 |
| 2 | Math | 3 |
| 3 | Physics | 0 |
StartPointer = 1, FreeListPtr = 4
Method 2: Record Data Type
This method defines a record (composite data type) with two fields:
- One field for data
- One field for storing pointers
- Declare a 1D array of this record type
Pseudocode Example:
Creates an array of 50 nodes, each with Name and Pointer fields
Step-by-Step Example: Ordered Linked List
Step 1: Empty Linked List
Initially, the linked list is empty. All nodes are in the free list (heap).
| Index | Data | Pointer |
|---|---|---|
| [1] | (empty) | 2 |
| [2] | (empty) | 3 |
| [3] | (empty) | 4 |
| [4] | (empty) | 5 |
| [5] | (empty) | 6 |
| [6] | (empty) | 7 |
| [7] | (empty) | 8 |
| [8] | (empty) | 9 |
| [9] | (empty) | 0 |
Step 2: Insert "Biology" (First Node)
"Biology" is inserted at index 1 (first free node).
| Index | Data | Pointer |
|---|---|---|
| 1 | Biology | 0 |
| 2 | (empty) | 3 |
| 3 | (empty) | 4 |
| 4 | (empty) | 5 |
| 5 | (empty) | 6 |
| 6 | (empty) | 7 |
| 7 | (empty) | 8 |
| 8 | (empty) | 9 |
| 9 | (empty) | 0 |
Pointer is 0 because it's the only node (end of list)
Step 3: Insert "Math" and "Physics" in Order
"Math" and "Physics" are added in alphabetical order.
| Index | Data | Pointer |
|---|---|---|
| 1 | Biology | 2 |
| 2 | Math | 3 |
| 3 | Physics | 0 |
| 4 | (empty) | 5 |
| 5 | (empty) | 6 |
| 6 | (empty) | 7 |
| 7 | (empty) | 8 |
| 8 | (empty) | 9 |
| 9 | (empty) | 0 |
Biology → Math → Physics → NULL (alphabetical order)
Step 4: Insert "Computer" Between Biology and Math
"Computer" is inserted in alphabetical order between Biology and Math.
| Index | Data | Pointer |
|---|---|---|
| 1 | Biology | 4 |
| 2 | Math | 3 |
| 3 | Physics | 0 |
| 4 | Computer | 2 |
| 5 | (empty) | 6 |
| 6 | (empty) | 7 |
| 7 | (empty) | 8 |
| 8 | (empty) | 9 |
| 9 | (empty) | 0 |
Biology → Computer → Math → Physics → NULL (updated pointers)
Key change: Biology's pointer changed from 2 to 4, Computer's pointer set to 2 (Math)
Activity 2: Trace Array Implementation
Given the following linked list state:
| Index | Subject | Pointer |
|---|---|---|
| 1 | Biology | 4 |
| 2 | Maths | 3 |
| 3 | Physics | 0 |
| 4 | Computer | 2 |
| 5 | Accounting | 1 |
- Draw the linked list diagram showing all nodes and pointers
- What is the order of subjects in the list?
- If we delete the first node, what will be the new StartPointer value?
- If we then delete node at index 2 (Maths), what pointer needs to be updated?
Solution:
1. Linked List Diagram:
2. Order of subjects:
Accounting → Biology → Computer → Maths → Physics
3. Delete first node (Accounting at index 5):
New StartPointer = pointer of deleted node = 1 (points to Biology)
FreeListPtr would be updated to 5 (released node)
4. Delete node at index 2 (Maths):
Previous node (Computer at index 4) pointer needs to be updated
Current: Computer points to 2 (Maths)
After deletion: Computer should point to 3 (Physics)
Maths pointer (3) is copied to Computer's pointer field
Advantages & Disadvantages of Linked Lists
Advantages:
- To add/delete a node in ordered linked list only pointers need to be changed – no need to sort complete list
- Insertion and deletion operations are quite easy, as there is no need to shift every element after insertion or deletion
- Only the address present in the pointers needs to be updated
- Some very helpful data structures like queues and stacks can be easily implemented using a Linked List
- Dynamic size - can grow and shrink as needed
Disadvantages:
- Store pointers for every data so require extra storage
- Memory required by a linked list is more than memory required by an array, as there is also a pointer field along with the data field
- Pointer field too requires memory to store the address of the next node
- To access node at index x in a linked list, we have to traverse through all the nodes before it (sequential access)
- In arrays, we can directly access an element at index x (random access)
- More complex to setup/implement than arrays
When to Use Linked Lists vs Arrays
| Scenario | Use Linked List When... | Use Array When... |
|---|---|---|
| Frequent insertions/deletions | Yes - pointers can be easily updated | No - requires shifting elements |
| Random access needed | No - must traverse from start | Yes - direct access by index |
| Memory efficiency | No - extra pointer storage | Yes - no extra pointers |
| Dynamic size | Yes - can grow/shrink easily | No - fixed size (static arrays) |
| Implementation complexity | More complex | Simpler |
Real-Life Example: Music Playlist
A music player playlist is a perfect example of a linked list:
The playlist has a "current song" pointer (like StartPointer). When you press "next," it follows the pointer to the next song. Adding a new song to your favorites (beginning) is quick - just update pointers.
Check Your Understanding: Implementation
1. What are the two methods for implementing linked lists? [2 marks]
Answer
- [1 mark] Using two 1D arrays - one for data, one for pointers
- [1 mark] Using a record data type with fields for data and pointer
- [Additional] Both methods separate data storage from pointer management
2. In the array implementation, what does a pointer value of 0 represent? [1 mark]
Answer
- [1 mark] Null pointer - end of the list
- [Additional] Indicates there is no next node in the list
3. What is the purpose of FreeListPtr? [2 marks]
Answer
- [1 mark] Stores the index where the next value will be stored
- [1 mark] Manages the free list (heap) of available nodes
- [Additional] When it becomes 0, no more space is available
4. Why do linked lists require more memory than arrays? [2 marks]
Answer
- [1 mark] Each node stores both data and a pointer
- [1 mark] The pointer field requires extra memory to store addresses
- [Additional] Arrays only store data, not pointers to next elements
5. When would you choose a linked list over an array? [2 marks]
Answer
- [1 mark] When you need frequent insertions and deletions
- [1 mark] When the size needs to change dynamically
- [Additional] When you don't need random access to elements
Key Takeaways
- An Abstract Data Type (ADT) is a collection of data and a set of operations on those data
- A linked list is a list where each item points to the next item in the list
- Each element in a linked list is called a node, consisting of data items and a pointer
- The start pointer stores the address of the first node in the list
- A null pointer (value 0) marks the end of the list
- New items are always added to the start of a linked list
- To add a node at the beginning: copy startPointer to new node's pointer, then update startPointer to point to new node
- To delete the first node: copy its pointer field into StartPointer
- Linked lists can be implemented using two 1D arrays (one for data, one for pointers) or a record data type
- FreeListPtr manages available nodes in the free list (heap)
- Advantages of linked lists: easy insertion/deletion, no shifting of elements, dynamic size
- Disadvantages of linked lists: extra memory for pointers, sequential access only, more complex implementation
- Use linked lists when you need frequent insertions/deletions and dynamic size
- Use arrays when you need random access and memory efficiency
- Common operations: CreateLinkedList, AddItem, RemoveItem, traverse the list
Question Bank
1. Explain what an Abstract Data Type (ADT) is and give three examples. [4 marks]
Marking Scheme & Answer
- [2 marks] An ADT is a collection of data and a set of operations on those data
- [2 marks] Three examples: stack, queue, linked list (1 mark each for any three)
- [Additional] ADTs define what operations can be performed, not how they're implemented
2. Describe the structure of a node in a linked list and explain the purpose of each component. [4 marks]
Marking Scheme & Answer
- [2 marks] A node consists of: data items (the actual information stored) and a pointer (stores address of next node)
- [1 mark] Data items: hold the value/content of the node
- [1 mark] Pointer: links to the next node, creating the chain
- [Additional] Together they allow dynamic connection between elements
3. Compare and contrast arrays and linked lists for storing data. [6 marks]
Marking Scheme & Answer
| Aspect | Arrays | Linked Lists |
|---|---|---|
| Memory usage | More efficient (only data) | Less efficient (data + pointers) |
| Access method | Random access (by index) | Sequential access (must traverse) |
| Insertion/deletion | Slow (requires shifting) | Fast (update pointers only) |
| Size flexibility | Fixed size (static arrays) | Dynamic (can grow/shrink) |
| Implementation | Simpler | More complex |
Key points: Arrays better for random access and memory efficiency. Linked lists better for frequent insertions/deletions and dynamic size.
4. Show step-by-step how to add a node to the beginning of a linked list. Use diagrams or pseudocode. [5 marks]
Marking Scheme & Answer
- [1 mark] Create new node with data value
- [2 marks] Copy content of startPointer into new node's pointer field (links new node to old first node)
- [2 marks] Set startPointer to point to the new node (makes new node the first)
Before: Start → B → D → L → NULL
After adding A: Start → A → B → D → L → NULL
A's pointer points to B (old first), StartPointer now points to A
5. A linked list stores names in alphabetical order. Show the final state after: [6 marks]
CreateLinkedList
AddItem("Nushie")
AddItem("Kellie")
AddItem("Scarlett")
RemoveItem("Nushie")
AddItem("Jon")
Marking Scheme & Answer
- [1 mark] CreateLinkedList: Empty list
- [1 mark] AddItem("Nushie"): Start → Nushie → NULL
- [1 mark] AddItem("Kellie"): Start → Kellie → Nushie → NULL (K before N alphabetically)
- [1 mark] AddItem("Scarlett"): Start → Kellie → Nushie → Scarlett → NULL (S at end)
- [1 mark] RemoveItem("Nushie"): Start → Kellie → Scarlett → NULL
- [1 mark] AddItem("Jon"): Start → Jon → Kellie → Scarlett → NULL (J before K)
Final answer: Start → Jon → Kellie → Scarlett → NULL
Alphabetical order: Jon (J), Kellie (K), Scarlett (S)
6. Write pseudocode to define a ListNode record type and declare an array for 50 nodes. [4 marks]
Marking Scheme & Answer
- [2 marks] Correct TYPE definition with Pointer and Name fields
- [1 mark] Correct ENDTYPE
- [1 mark] Correct array declaration for 50 nodes
- [Additional] This creates a record-based linked list implementation
7. Explain how the free list (heap) is managed in linked list array implementation. [4 marks]
Marking Scheme & Answer
- [1 mark] Empty positions in the array are managed as an empty linked list called the heap/free list
- [1 mark] FreeListPtr stores the index where the next value will be stored
- [1 mark] When a node is deleted, it's added to the free list for reuse
- [1 mark] When FreeListPtr becomes 0, no more space is available
- [Additional] Initially, all nodes are linked in the free list with pointers to next free position
8. Describe a real-world situation where a linked list would be preferable to an array. [3 marks]
Marking Scheme & Answer
- [1 mark] Music playlist: frequently adding/removing songs, playing in sequence
- [1 mark] Web browser history: new pages added, old ones removed, navigation in sequence
- [1 mark] Undo functionality in software: each action linked to previous state
- [Additional] Any situation requiring frequent insertions/deletions and sequential access
9. What happens to memory when nodes are deleted from a linked list? [3 marks]
Marking Scheme & Answer
- [1 mark] The node is not immediately erased from memory
- [1 mark] It becomes part of the free list (heap) for reuse
- [1 mark] FreeListPtr is updated to manage available nodes
- [Additional] When a new node is added, it can use space from previously deleted nodes
10. Complete the diagram for CreateLinkedList operation showing initial pointer values for 5 nodes. [4 marks]
Marking Scheme & Answer
| HeadPointer | NameList | ||
|---|---|---|---|
| Name | Pointer | ||
| 0 | [1] | (empty) | 2 |
| [2] | (empty) | 3 | |
| [3] | (empty) | 4 | |
| [4] | (empty) | 5 | |
| [5] | (empty) | 0 | |
- [1 mark] HeadPointer = 0 (empty list)
- [2 marks] Correct pointer chain: 1→2, 2→3, 3→4, 4→5, 5→0
- [1 mark] FreePointer = 1 (first free node)
- [Additional] All nodes are initially in the free list, ready for use