[go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 278 views

    Data Structures & Algorithms LAB - Spring 2014 (BS-CS-F12 Morning & Afternoon)

    Uploaded by

    Rizwan Khadim
    This document provides instructions for a series of tasks involving linked lists. It describes implementing a singly linked list class with functions for insertion, removal, and traversal. It then tasks adding functions for removing the last, second last, and kth nodes; combining two lists; and merging two lists alternately. Test code is to be written for each function.

    Copyright:

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

    Data Structures & Algorithms LAB - Spring 2014 (BS-CS-F12 Morning & Afternoon)

    Uploaded by

    Rizwan Khadim
    278 views3 pages
    This document provides instructions for a series of tasks involving linked lists. It describes implementing a singly linked list class with functions for insertion, removal, and traversal. It then tasks adding functions for removing the last, second last, and kth nodes; combining two lists; and merging two lists alternately. Test code is to be written for each function.

    Original Description:

    This is lab manual

    Original Title

    Lab-08

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides instructions for a series of tasks involving linked lists. It describes implementing a singly linked list class with functions for insertion, removal, and traversal. It then tasks adding functions for removing the last, second last, and kth nodes; combining two lists; and merging two lists alternately. Test code is to be written for each function.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    278 views3 pages

    Data Structures & Algorithms LAB - Spring 2014 (BS-CS-F12 Morning & Afternoon)

    Uploaded by

    Rizwan Khadim
    This document provides instructions for a series of tasks involving linked lists. It describes implementing a singly linked list class with functions for insertion, removal, and traversal. It then tasks adding functions for removing the last, second last, and kth nodes; combining two lists; and merging two lists alternately. Test code is to be written for each function.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    Thursday, May 15, 2014.

    Data Structures & Algorithms LAB – Spring 2014


    (BS-CS-F12 Morning & Afternoon)
    Lab # 8

    Instructions: 
    • Attempt the following tasks exactly in the given order. 
    • Make sure that there are no dangling pointers or memory leaks in your programs. 
    • Indent your code properly. 
    • Use meaningful variable and function names. Follow the naming conventions. 
    • Use meaningful prompt lines/labels for all input/output that is done by your programs. 

    Task # 0 (Pre‐Requisite)  (Max Time: 20 Minutes)
    Implement a singly linked list class which stores integers in unsorted order. Your class
    declarations should look like:

    class LinkedList;  class LinkedList {  
    class Node {        private: 
    friend class LinkedList;    Node* head; 
      private:    public: 
      int data;    LinkedList();  // Default constructor
      Node* next;    ~LinkedList();  // Destructor
    };    … 
    }; 

    Apart from the default constructor and destructor, the LinkedList class should also have the
    following public member functions:

    void insert (int val) 
    To insert a new value (val) into the linked list. The time complexity of this function should be
    constant i.e. O(1). In other words, there should be no loop in this function.

    bool remove (int val) 
    This function removes the node containing the first occurrence of val from the linked list. This
    function should return true if such a node is found (and removed) from the linked list, and it
    should return false otherwise.

    void display () 
    This function displays the contents of the linked list on screen.

    Page 1 of 3
    Thursday, May 15, 2014.

    Task # 1      (Max Time: 45 Minutes)
    Now, add the following three public member functions to the LinkedList class:

    bool removeLastNode (int& val) 
    A call to this function will remove the last node of the linked list. Before deallocating the node,
    this function should store the data present in that node into the variable val. This function
    should return false if the list is empty; otherwise it should remove the last node of the linked list
    and return true.

    bool removeSecondLastNode (int& val) 
    A call to this function will remove the second last node of the linked list. Before deallocating the
    node, this function should store the data present in that node into the variable val. This function
    should return false if the list contains fewer than two nodes; otherwise it should remove the
    second last node of the linked list and return true. (Note: You are NOT allowed to modify the
    data of any node in the linked list).

    bool removeKthNode (int k, int& val) 
    This function will remove the kth element (node) from the linked list. For example, if the linked
    list object list contains {4  2  8  1  9  5  4  6}, then the function call list.removeKthNode(4)
    should remove the 4th element (node) from the linked list and the resulting list should be:
    {4 2 8 9 5 4 6}. Before deallocating the node, this function should store the data present in that
    node in the variable val. This function should return false if the linked list contains fewer than k
    elements; otherwise it should remove the kth node from the linked list and return true. (Note: You
    are NOT allowed to modify the data of any node in the linked list).

    Also write a drive main function to test the working of each of the above-mentioned functions.

    Task # 2      (Max Time: 20 Minutes) 
    Add the following public member function to the LinkedList class:

    void combine (LinkedList& list1, LinkedList& list2) 
    This function will combine the nodes of the two linked lists (list1 and list2) to form one list.
    All the nodes of the first list (list1) will precede all the nodes of the second list (list2).
    For example, if list1 contain {7 3 4 2} and list2 contains {5 9}, then after the function call
    list3.combine(list1,list2), list3 should contain {7  3  4  2  5  9} and list1 and list2
    should be empty now.
    Note: You are NOT allowed to create any new node in this function. You are also NOT allowed
    to modify the “data” field of any node. You can assume that the LinkedList object on which this
    function is called is empty at the start of this function.

    Also write a driver main function to test the working of the above function.

    Page 2 of 3
    Thursday, May 15, 2014.

    Task # 3      (Max Time: 25 Minutes) 
    Add the following public member function to the LinkedList class:

    void shuffleMerge (LinkedList& list1, LinkedList& list2) 
    This function will merge the nodes of the two linked lists (list1 and list2) to make one list,
    by taking nodes alternately from the two lists.
    For example, if list1 contains {2 6 4} and list2 contains {8 1 3}, then after the function call
    list3.shuffleMerge(list1,list2), list3 should contain {2  8  6  1  4  3} and list1 and
    list2 should be empty now.
    Note: You are NOT allowed to create any new node in this function. You are also NOT allowed
    to modify the “data” field of any node. You can assume that both lists (which are being merged)
    have the same number of elements. You can also assume that the LinkedList object on which
    this function is called is empty at the start of this function.

    Also write a driver main function to test the working of the above function.

    Page 3 of 3

    You might also like