ICT208 Algorithms and Data Structures
Assessment 2: Linked-List Case Study 1 – Vaccination Centre
| Linked Lists- Case study 1 In this assessment, students will analyse a case and develop linked structures by using pointers and finally write code.
| Due in week 7 | 40% | 1,2,3,4 |
Case study:
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:
Each element in the link is called a node which is composed of two parts:
a. Data stored by the node
b. Link pointed to the next node in the linked list
In this assessment 2, you are required to develop a Linked List in visual studio called LinkedList.cpp which uses a Linked List to the order in which people arrive at a vaccination clinic.
1. Node in the linked list with appropriate data types: each node stores the person’ name and the person’s current position (index) in the Linked List and link to the next node in the Linked List. Every time a new person arrives, a new node is created and added to the linked list. The position (index) of new node is one more than that of the previous node.
- Deletion− Deletes a node at the beginning of the linked list: method signature is void deleteFirst()
- Insert Last− Adds a node at the end of the linked list: method signature is void insertLast(String newPersonName)
- Delete Last− Deletes a node from the end of the linked list: method signature is void deleteLast()
- Insert before− Adds a node before another node (according to the provided index in the method parameter) of the linked list: method signature is void insertAfter(int index)
- Delete− Deletes a node from the linked list using the index: method signature is voide deleteAfter(int index)
- Search – Search through the linked list to identify the first occurrence of node with match data against the target: method signature is int search(String PersonName)
- Display − Displays the complete linked list in a forward manner: method signature is String display( )
The following reference sites can be of helpful to enhance your understanding of Linked List class structure based on Node and associated methods:
1. https://www.geeksforgeeks.org/data-structures/linked-list/
2. https://www.freecodecamp.org/news/data-structures-explained-with-examples-linked-list/
3. https://beginnersbook.com/2013/12/linkedlist-in-java-with-example/
Submission requirement: upload the LinkedList.cpp to Moodle by week 7.
Marking rubric
| Marking criteria | Lecturer expectation | Marks |
| Declaration of node in Linked List | Node contains correct data members with data types | 10 |
| Insertion of node at the front, or after another node using index or end of Linked List | Insertion, insert last, insert after methods are correctly implemented with comments | 35 |
| Deletion of node at the front or using an index or at end of Linked List | Deletion, delete last, delete are correctly implemented with comments | 35 |
| Search through the linked list to identify the first occurrence of node with matching key | Search is correctly implemented with comments | 10 |
| Display the complete linked list from front node to the end node of their stored browsing URL | Display is correctly implemented with comments | 10 |