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 ​temp​having 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 ​pres​is 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 ​prev​to the ​pres​and point ​pres​to the next node after ​pres (ie. pres->next)​.

        v. Traverse the list until ​pres​is 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