​Recitation 4, Linked​ List Operations

Description

Objectives

1. 1. Insertion

1. 2. Traversal

1. 3. Deletion

1. 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. 1. Insertion at the start.

1. 2. Insertion at a given position.

1. 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. Create a new node,

2. Update the next pointer of that node to start of the list. (Value of the head pointer)

3. Update head pointer to new node.

​2. Insertion at a given position

For example let us insert a new node at position 2.

1. Create a new node (B).

2. Count and traverse until the node previous to given position i.e A.

3. Store the A’s next pointer value in a temporary variable.

4. Update the next pointer of A to the address of new node.

0. • First, the position of the node to be deleted (‘A’) must be found.

0. • The next step is to point the node pointing to ‘A’, to point to ‘B’.

0. • The last step is to free the memory held by ‘A’.

0. Deletion of the first node

0. • 1. 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 ​temp​having a reference copy of the head node.

2. Point the head node from ‘A’ to ‘B’

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

2. Deletion of the last node

2. 1. Given below is a linked list representation before deletion of the last node

2. Steps followed to delete the last node (‘A’) having value ‘4’.

2. 1. Create a variable ​prev ​having a reference copy of the head node.

   2. Create a variable ​pres ​having a reference copy of the next node after the head.

2. 3. Traverse the list until ​pres​is pointing to the last node ‘A’.

prev ​will be pointing to the second last node now.

4. Make ​prev ​point to ​NULL.

5. Free the node ‘A’ pointed to by ​pres.

​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

2. Steps followed to delete every node in the linked list.

2. 1. Create a variable ​prev ​having a reference copy of the head node.

2. 2. Create a variable ​pres ​having a reference copy of the next node after the head.

2. 3. While traversing the list, at each step delete/free the memory pointed to by ​prev.

2. 4. Now, point ​prev​to the ​pres​and point ​pres​to the next node after ​pres (ie. pres->next)​.

2. 5. Traverse the list until ​pres​is pointing to the ​NULL​.

prev ​will be pointing to the second last node now.

1. 6. Free the memory pointed to by ​prev. ​Now every element in the linked list is deleted/freed.

3. Linked list representation after deletion of all the nodes.

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