Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Ap 3

    Uploaded by

    Vaibhav Sharma

    Copyright:

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

    Ap 3

    Uploaded by

    Vaibhav Sharma
    2 views5 pages

    Original Title

    AP_3

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    Ap 3

    Uploaded by

    Vaibhav Sharma

    Copyright:

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

    Experiment 1.

    Student Name: Vaibhav Sharma UID: 22BCS12459


    Branch: BE – CSE Section/Group: 22BCS_ML-901 - A
    th
    Semester: 5 Date of Performance: 05/08/24
    Subject Name: Advanced Programming Lab-1
    Subject Code: 22CSP-314

    Problem 1 (Compare two linked lists)


    1. Aim:
    To demonstrate the concept of Linked List.

    2. Objective:
    • To learn about Linked List data Structure
    • To learn different approaches to compare two linked lists
    3. Algorithm:
    • Read the number of test cases.
    • For each test case:
    o Read the size and elements of the first linked list and construct it.
    o Read the size and elements of the second linked list and construct it.
    o Compare the two linked lists by checking each corresponding node.
    o If all corresponding nodes match and both lists are of the same length, they
    are identical.
    o Otherwise, they are not identical.
    • Print 1 if the linked lists are identical, otherwise print 0.

    4. Source Code:
    #include <iostream>
    using namespace std;

    struct SinglyLinkedListNode {
    int data;
    SinglyLinkedListNode* next;
    SinglyLinkedListNode(int node_data) {
    data = node_data;
    next = nullptr;
    }
    };
    SinglyLinkedListNode* insert_node(SinglyLinkedListNode* head, int data) {
    SinglyLinkedListNode* new_node = new SinglyLinkedListNode(data);
    if (head == nullptr) {
    return new_node;
    } else {
    SinglyLinkedListNode* temp = head;
    while (temp->next != nullptr) {
    temp = temp->next;
    }
    temp->next = new_node;
    }
    return head;
    }
    bool compare_lists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    while (head1 != nullptr && head2 != nullptr) {
    if (head1->data != head2->data) {
    return false;
    }
    head1 = head1->next;
    head2 = head2->next;
    }
    return (head1 == nullptr && head2 == nullptr);
    }
    int main() {
    int test_cases;
    cin >> test_cases;
    for (int t = 0; t < test_cases; t++) {
    int n1, n2, data;
    cin >> n1;
    SinglyLinkedListNode* head1 = nullptr;
    for (int i = 0; i < n1; i++) {
    cin >> data;
    head1 = insert_node(head1, data);
    }
    cin >> n2;
    SinglyLinkedListNode* head2 = nullptr;
    for (int i = 0; i < n2; i++) {
    cin >> data;
    head2 = insert_node(head2, data);
    }
    bool result = compare_lists(head1, head2);
    if (result) {
    cout << 1 << endl;
    } else {
    cout << 0 << endl;
    }
    }
    return 0;
    }
    5. Output:

    6. Time Complexity: O(n)

    Problem 2 (Inserting a Node Into a Sorted Doubly Linked List)

    a. Aim:
    To demonstrate the concept of Linked List.
    b. Objective:
    • To learn about Linked List data Structure.
    • To insert a node into a sorted Doubly Linked List.
    3. Algorithm:
    • Input the number of test cases (t).
    • For each test case:
    o Input the number of elements in the list (n).
    o Initialize an empty list ‘lst’.
    o For each element in the list:
    a. Input the element nodeValue.
    b. Add nodeValue to the end of the list ‘lst’.
    o Input the value data that needs to be inserted into the list in sorted order.
    o Insert data into ‘lst’ while maintaining sorted order:
    a. Traverse the list from the beginning to find the first position where
    the current element is greater than or equal to data.
    b. Insert data at that position.
    o Print the updated list.
    a. Traverse the list and print each element.
    3. Source Code:
    #include <iostream>
    #include <list>
    using namespace std;

    void insertSorted(list<int>& lst, int data) {


    auto it = lst.begin();
    while (it != lst.end() && *it < data) {
    ++it;
    }
    lst.insert(it, data);
    }

    void printList(const list<int>& lst) {


    for (int value : lst) {
    cout << value << " ";
    }
    cout << endl;
    }

    int main() {
    int t, n, data;
    cin >> t;
    while (t--) {
    cin >> n;
    list<int> lst;
    for (int i = 0; i < n; ++i) {
    int nodeValue;
    cin >> nodeValue;
    lst.push_back(nodeValue);
    }
    cin >> data;
    insertSorted(lst, data);
    printList(lst);
    }
    return 0;
    }
    4. Output:

    5. Time Complexity: O(n)


    6. Learning Outcomes:
    • Learned about Linked List data Structure.
    • Learned different approaches to compare two linked lists.
    • Learned to insert a node into a sorted Doubly Linked List.
    • Learned to read and handle input values, including list elements and new data.

    You might also like