$29
Recitation 4 Linked List Operations Solution
Objectives
1. Insertion
2. Traversal
3. Deletion
4. Exercise
1. Insertion in a linked list
Adding a new node in a linked list is a multi-step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it must be inserted.
Scenarios in insertion
1. Insertion at the start.
2. Insertion at a given position.
3. Insertion at the end.
1. Inserting at the start of the list.
Now we will insert an element at the start of the list.
1
CSCI 2270 – Data Structures
Linked List Operations
a. Create a new node,
b. Update the next pointer of that node to start of the list. (Value of the head pointer)
c. Update head pointer to new node.
2. Insertion at a given position
For example let us insert a new node at position 2.
a. Create a new node (B).
b. Count and traverse until the node previous to given position i.e A.
c. Store the A’s next pointer value in a temporary variable.
d. Update the next pointer of A to the address of new node.
2
CSCI 2270 – Data Structures
Linked List Operations
e. Copy the temporary variable’s value to B’s next pointer.
f. Now B’s next pointer points to the address of the node C.
3. Insertion at the end
a. Create a new node B.
b. Traverse till the node whose next pointer points to NULL. (A)
c. Update the next pointer of A to B’s address.
d. Point B’s next pointer to NULL.
2. Traversal and printing
To print a list, we need to traverse through all the nodes in the list until we encounter the last node. When a node points to NULL we know that it is the last node.
node = root;
while ( node != NULL )
{
cout << node->value << endl;
node = node->next;
}
3. Deletion
Deleting a node in the linked list is a multi-step activity. Let’s call the node to be deleted as ‘A’ and the node ‘A’ is pointing to as ‘B’.
3
CSCI 2270 – Data Structures
Linked List Operations
◦ First, the position of the node to be deleted (‘A’) must be found.
◦ The next step is to point the node pointing to ‘A’, to point to ‘B’.
◦ The last step is to free the memory held by ‘A’.
1. Deletion of the first node
a. Given below is the linked list representation before the deletion of the first node
b. Steps followed to delete the first node (‘A’) having value ‘1’.
i. Create a variable temphaving a reference copy of the head node.
ii. Point the head node from ‘A’ to ‘B’
iii. Head is now pointing to ‘B’. So, The Linked List’s first element now is ‘B’ with the
value‘2’
iv. Free the node ‘A’ pointed to by temp.
c. Linked list representation after deletion.
4
CSCI 2270 – Data Structures
Linked List Operations
2. Deletion of the last node
a. Given below is a linked list representation before deletion of the last node
b. Steps followed to delete the last node (‘A’) having value ‘4’.
i. Create a variable prev having a reference copy of the head node.
ii. Create a variable pres having a reference copy of the next node after the head.
iii. Traverse the list until presis pointing to the last node ‘A’.
prev will be pointing to the second last node now.
iv. Make prev point to NULL.
v. Free the node ‘A’ pointed to by pres.
5
CSCI 2270 – Data Structures
Linked List Operations
c. Linked list representation after prev and pres have completed traversing.
d. Linked list representation after deletion of the node ‘A’ and pointing prev to NULL.
3. Deletion of a linked list
The deletion of a linked list involves iteration over the complete linked list and deleting (freeing) every node in the linked list.
a. Given below is a linked list representation before deletion of the last node
6
CSCI 2270 – Data Structures
Linked List Operations
b. Steps followed to delete every node in the linked list.
i. Create a variable prev having a reference copy of the head node.
ii. Create a variable pres having a reference copy of the next node after the head.
iii. While traversing the list, at each step delete/free the memory pointed to by prev.
iv. Now, point prevto the presand point presto the next node after pres (ie. pres->next).
v. Traverse the list until presis pointing to the NULL.
prev will be pointing to the second last node now.
vi. Free the memory pointed to by prev. Now every element in the linked list is deleted/freed.
c. Linked list representation after deletion of all the nodes.
7
CSCI 2270 – Data Structures
Linked List Operations
4. Exercise
Download the Recitation 4 folder from moodle. There are LinkedList header, implementation and main files.
Your task is to complete the following function/functions:
1. Given a position in the linked list, delete the node at that position.(Silver problem - Mandatory )
2. Swap the first and last nodes in a linked list (Gold problem)
8
