Scribd Logo
Upload

Welcome to Scribd!

    • 168 views

    Lab Manual - Linear Linked List

    Uploaded by

    Juiyyy Tttt
    The document describes how to implement a singly linked list in C++. It includes defining a Node class to hold list elements and a LinkedList class to implement list operations. The key operations covered are creating and destroying lists, checking if a list is empty, inserting and searching nodes, printing lists, and deleting nodes. It also provides examples of additional exercises like reversing a list, deleting odd nodes, rearranging nodes, and swapping node positions.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Lab Manual - Linear Linked List

    Uploaded by

    Juiyyy Tttt
    168 views4 pages
    The document describes how to implement a singly linked list in C++. It includes defining a Node class to hold list elements and a LinkedList class to implement list operations. The key operations covered are creating and destroying lists, checking if a list is empty, inserting and searching nodes, printing lists, and deleting nodes. It also provides examples of additional exercises like reversing a list, deleting odd nodes, rearranging nodes, and swapping node positions.

    Original Title

    Lab Manual_Linear Linked List.docx

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes how to implement a singly linked list in C++. It includes defining a Node class to hold list elements and a LinkedList class to implement list operations. The key operations covered are creating and destroying lists, checking if a list is empty, inserting and searching nodes, printing lists, and deleting nodes. It also provides examples of additional exercises like reversing a list, deleting odd nodes, rearranging nodes, and swapping node positions.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    168 views4 pages

    Lab Manual - Linear Linked List

    Uploaded by

    Juiyyy Tttt
    The document describes how to implement a singly linked list in C++. It includes defining a Node class to hold list elements and a LinkedList class to implement list operations. The key operations covered are creating and destroying lists, checking if a list is empty, inserting and searching nodes, printing lists, and deleting nodes. It also provides examples of additional exercises like reversing a list, deleting odd nodes, rearranging nodes, and swapping node positions.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 4

    1.

    Singly Linked Lists


    The objective of this lab session is to acquire skills in working with singly linked lists. The task is to first
    implement the following operations:

    1) Create an empty linked list; // do so in the constructor.

    2) bool IsEmpty(); // checks whether the list is empty or not. Returns true if empty and false otherwise.

    3) InsertAtFront(value); // takes input from a user and inserts it at front of the list

    4) Void PrintList();

    5) InsertSorted(value); //If we want to maintain a sorted list, we should implement this function

    6) Search(value); This function shall search value in a list. If found, we will need to store two addresses:

    a. Address of the node in which the searched value is found in a pointer variable named Loc_;
    we will store NULL in Loc_ in case value is not found.

    b. Address of the node which is logical predecessor of value in a list.

    i. The Search() provides functionality for other operations such as insertion in a sorted
    list, deleting a value, modifying a value, printing it etc.

    7) Delete(value); // searches value and then deletes it if found.

    8) DestroyList(); // Distroys all nodes of the list leaving the list in empty state.

    Declare Node Class: The data structure that will hold the elements of the list is called Node.
    Declare it as follows:
    class ListNode{
    public:
    int data;
    ListNode *next;

    };

    Declare class Linked List: Now, declare your main class LinkedList. Inside this
    class, you shall define all key functions to implement all operations of a linked
    list.

    class LinkedList{
    public:
    ListNode *start; // special variable which stores address of head node.
    ListNode *PredLoc_; //to be used by Search(value) method to store address
    of logical predecessor of value in a list.
    ListNode *Loc_; //to be used by Search(value) method to store address of
    the node containing the searched value in a list. If it is not found it contains
    NULL.
    }

    1) Creating a LinkedList
    In order to create an empty list, assign NULL value to start pointer variable.
    LinkedList(){
    start=NULL;
    PredLoc_=NULL;
    Loc_=NULL;
    }
    2) Bool IsEmpty() function
    By checking content of the special pointer variable start/first, this function should return true value if the list is
    empty and false otherwise.

    3) Inserting a value at the Front of a list


    First, Reserve space for a new node to be inserted in the list by creating object of class ListNode and storing
    its address in a temporary pointer variable.
    ListNode *newnode = new ListNode();

    Now store value in data part of the new node:


    newnode->data=value;

    Finally, link newnode at front of the linked list via following two statements:
    newnode->next=start;
    start=newnode;

    4) void PrintList()
    This function prints all elements of a linked list starting from the first one.
    ListNode *temp = start;
    If(list not empty){
    While(not end of list){
    cout<<temp->data<<” “;
    // advance temp to successor node.
    }
    }

    5) Void Search( value)


    As discussed in the class, we will implement a general-purpose search function which will provide functionality
    to other operations like insertion, deletion, modification etc. This function shall take a value as argument from
    the user and then search it in the list. You should use two node pointer variables namely ploc and loc in this
    function.

    1. In the variable loc, save address of the node in which the searched value is found. In case, the searched
    value does not exist, save NULL value in loc.

    2. In the variable ploc, we shall store address of the logical predecessor node of the searched value.

    Void search(value){
    Initialize loc & ploc
    Loc= address of head node
    Ploc = address of logical predecessor of head node. Note that first node
    has no predecessor. So, we will always initialize ploc to NULL.
    For the moment assume that we are maintaining a list sorted in the
    ascending order. Search value until either 1) we reach the end of the list
    or 2) logical position of the value is passed.

    while (loc!=NULL and loc.data < value){


    Advance both ploc and loc
    }

    If(loc!NULL & loc.data!=value)


    Loc=NULL; //as value is not found so set loc equal to null.
    } //end of search function.
    After execution of the search(value) method, there are four possible combinations
    of loc and ploc

    Ploc Loc Interpretation


    Null Null Searched value not found and its logical position
    is at the front of the list
    Null Non-null Value found in the head node of the list
    Non-null Non-null Loc=non-null implies the searched value has been
    found. Ploc=non-null implies the value is not in
    the head node; it might be in any node other than
    the head node
    Non-null Null Loc=null implies searched value not found.
    Ploc=non-null implies its logical position is not
    at the front.

    6) Insertion in a Sorted List


    For the moment, assume duplications are not allowed in the list. You have to insert
    new value after call to search function by considering the above mentioned four
    possible combinations of loc and ploc pointer variables.

    InsertSorted(value){
    Search(value)
    If (value already exists) //check using loc
    Return without insertion and print a message
    else{
    If(position of value is as head node)
    Insert value at front.
    Else
    Insert after ploc.

    7) Delete a Value
    Find value using search method and if a node containing the searched value is
    found, then delete it from the linked list. Also free the allocated memory.

    Delete(value){
    //if list empty then return

    Search(value)
    If(value is found){ //check loc
    If(value is in the head node)//check ploc {
    //delete head node and free memory
    }
    else{
    //update link using ploc
    ploc->next = loc->next;
    //finally free memory using delete command.
    delete loc;
    }
    }
    8) Destroy a Linked List
    This method should destroy all nodes of a linked list making it empty. It should also free space
    allocated for all the nodes.

    Hint: Save address of current head node in a temporary pointer variable. Advance start variable to
    the second node so that it becomes new head node. Then, delete current head node using the
    temporary pointer variable.

    Assignment 1:
    1. Write a function that prints all nodes of a linked list in the reverse order.
    2. Write a function that deletes all those nodes from a linked list which have odd numbered value
    in their data part. For instance, if the original list is 1-> 2->3->4->5 -> 6, then, the updated list
    should be 2-> 4 -> 6
    3. Write a function which reverses the order of the linked list. If the original list is 1-> 2->3->4->5
    -> 6, the updated list should be 6 -> 5 -> 4 -> 3 -> 2 ->1. Note that this function should only
    change pointer fields in the nodes, you are not allowed to modify data field of any node.
    4. Write a function which rearranges the linked list by group the nodes having even numbered
    and odd numbered value in their data part. The updated list may look like 1-> 3 -> 5->2-> 4->
    6 or 2-> 4-> 6 -> 1-> 3 -> 5.
    5. Write a function which takes two values as input from the user and searches them in the list.
    If both the values are found, your task is to swap both the nodes in which these values are
    found. Note, that you are not supposed to swap values. You are supposed to change next
    pointer fields in the concerned nodes.

    You might also like