Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    DSA Lab 8

    Uploaded by

    23-20911-092

    Copyright:

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

    DSA Lab 8

    Uploaded by

    23-20911-092
    2 views7 pages

    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 views7 pages

    DSA Lab 8

    Uploaded by

    23-20911-092

    Copyright:

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

    Data Structures & Algorithms

    Lab

    Submitted to:
    Sir Rehan Ahmed
    Submitted by:

    Rowaida Jamil
    Reg no:
    2023-BSE-053
    Class:
    BSE-3B

    Lab #8
    Task 1:
    Give answers to the following.
    1. Consider the following doubly linked list.

    Write C++ statements to:


    a. Print the value 26 using the pointer ‘last’:

    b. Print the value 17 using the


    pointer ‘first:

    c. Print the address of the node containing value 9 using the pointer ‘last’:

    2. Given the following linked list, state what does each of the following statements refer to?

    first->data;

    last->next;

    first->next->prev;

    first->next->next->data;

    last->prev->data;
    3. Redraw the following list after the given instructions are executed:

    ptr->next->prev = ptr->prev; ptr-


    >prev->next = ptr->next;
    delete ptr;

    Code Task#1
    Implement the class Doubly Linked List, with all provided functions.

    Code:
    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    class DList
    { private:
    struct node
    {
    int data;
    node *next;
    node *prev;
    } *head;
    public:
    DList(){head = nullptr; }
    ~DList(){
    node *temp = head;
    while (temp->next != nullptr)
    { node *nextnode = temp->next;
    delete temp;
    temp = nextnode;
    }
    head = nullptr;
    }
    bool emptyList()
    {return head == nullptr;
    }
    void insertafter(int oldV, int newV)
    {
    node *temp = new node;
    temp->data = newV;
    temp->next = temp->prev = nullptr;
    node *search = head;
    while (search != nullptr)
    {if (search->data == oldV)
    {temp->next = search->next;
    search->next->prev = temp;
    temp->prev = search;
    search->next = temp;
    break;
    }
    if (search->next != nullptr)
    search = search->next;
    else
    { search->next = temp;
    temp->prev = search;
    return; }
    }
    }
    void deleteNode(int value)
    { if (emptyList())
    cout << "linked list is empty" << endl;
    else if (head->data == value)
    { node *temp = head;
    head = head->next;
    head->prev = nullptr;
    delete temp;
    }
    else
    {
    node *temp = head;
    while (temp->next != nullptr)
    {if (temp->data == value)
    {temp->next->prev = temp->prev;
    temp->prev->next = temp->next;
    temp->next = temp->prev = nullptr;
    delete temp;
    return;
    }
    else
    temp = temp->next;
    }
    }
    }
    void insert_begin(int value)
    {
    node *temp = new node;
    temp->data = value;
    temp->next = temp->prev = nullptr;
    if (emptyList())
    head = temp;
    else{
    temp->next = head;
    head->prev = temp;
    head = temp;
    }
    }
    void insert_end(int value)
    {
    node *temp = new node;
    temp->data = value;
    temp->next = temp->prev = nullptr;
    if (emptyList())
    head = temp;
    else
    {
    node *sEnd = head;
    while (sEnd->next != nullptr)
    sEnd = sEnd->next;
    sEnd->next = temp;
    temp->prev = sEnd;
    }
    }
    void traverse()
    {
    if (emptyList())
    cout << "List is Empty" << endl;
    else
    { node *search = head;
    while (search != nullptr)
    {cout << search->data << " ";
    search = search->next; }
    cout << endl;
    }
    }
    void traverse2()
    { node *s1 = head;
    while (s1->next != nullptr)
    s1 = s1->next;
    while (s1 != nullptr)
    {cout << s1->data << " ";
    s1 = s1->prev;
    }
    cout << endl;
    }
    };

    int main()
    {
    DList d;
    cout << "Insertion at the end:" << endl;
    d.insert_end(3);
    d.insert_end(2);
    d.insert_end(6);
    d.traverse();
    cout << "Insertion at the beginning:" << endl;
    d.insert_begin(7);
    d.insert_begin(9);
    d.insert_begin(4);
    d.traverse();
    cout << "Insertion after number 4 and 2:" << endl;
    d.insertafter(5, 9);
    d.insertafter(2, 7);
    d.traverse();
    cout << "Reversed order of the list:" << endl;
    d.traverse2();
    cout << "Deleted two elements from the list(5,0):" << endl;
    d.deleteNode(5);
    d.deleteNode(0);
    d.traverse();
    cout << "After calling the destructor:" << endl;
    d.~DList();
    d.traverse();
    system ("pause");
    return 0;
    }

    Output:

    Code Task#2
    A stack can be implemented using a Doubly linked list. The first node can serve as the ‘top’
    of Stack and ‘push’ and ‘pop’ operations can be implemented by adding and removing
    nodes at the head of the linked list. Implement the Stack class using a linked list (Doubly)
    and provide all the standard member functions.Data type to strore in the stack must be
    char.

    Code:

    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    class node
    { public:
    char data;
    node *next, *prev;
    }*top;
    class Stack
    { public:
    Stack(){top=nullptr;}
    bool emptyList()
    { return top==nullptr; }
    void push(char value)
    { node *temp=new node;
    temp->data=value;
    temp->next=temp->prev=nullptr;
    if(!emptyList())
    { temp->next=top;
    top->prev=temp;
    }

    top=temp;
    }
    void pop()
    { if(emptyList())
    cout<<"List is empty, can not pop"<<endl;
    else
    { node *newNode=top;
    top=top->next;
    top->prev=nullptr;
    newNode->next=newNode->prev=nullptr;
    delete newNode;
    }
    }
    void traverse()
    { if(emptyList())
    cout<<"List is empty."<<endl;
    else
    { node *search = top;
    while(search!=nullptr)
    { cout<<search->data<<" ";
    search=search->next;
    }
    cout<<endl; }
    }
    };
    int main()
    { Stack s;
    cout<<"Push first 5 alphabets:"<<endl;
    s.push('e');
    s.push('d');
    s.push('c');
    s.push('b');
    s.push('a');
    s.traverse();
    cout<<"popped 2 elements from the stack:"<<endl;
    s.pop();
    s.pop();
    s.traverse();
    system ("pause");
    return 0;
    }
    Output:

    You might also like