rss DSKL

 avatar
NguyenAnhQuan
c_cpp
a month ago
3.2 kB
1
Indexable
Never
#include <iostream>

#define LIM 100005
#define EL cout<<"\n"

using namespace std;

struct Node {
    int data;
    Node* next;

    Node (int x) {  // create node
        data = x;
        next = nullptr;
    }
};

struct List {
    Node* head;
    Node* tail;

    List () {   // create list
        head = nullptr;
        tail = nullptr;
    }
};

void printList(List l) {
    Node* node = l.head;

    while (node != nullptr) {
        cout << node->data << " ";
        
        node = node->next;
    }

    cout << "\n";
}

Node* search(List l, int x) {
    Node* node = l.head;

    while (node != nullptr) {
        if (node->data == x) 
            return node;

        node = node->next;
    }

    return nullptr;
}

void addHead(List &l, Node* node) {
    if (l.head == nullptr) {
        l.head = node;
        l.tail = node;
    } else {
        node->next = l.head;
        l.head = node;
    }
}

void addTail(List &l, Node* node) {
    if (l.head == nullptr) {
        l.head = node;
        l.tail = node;
    } else {
        l.tail->next = node;
        l.tail = node;
    }
}

void addAfterQ(List &l, Node* q, Node* node) {
    if (q != nullptr) {
        node->next = q->next;
        q->next = node;
        if (l.tail == q) l.tail = node;
    } else {
        addHead(l, node);
    }
}

bool deleteHead(List &l) {
    if (l.head != nullptr) {
        Node* node = l.head;
        l.head = l.head->next;
        delete node;
        if (l.head == nullptr) l.tail = nullptr;
        return 1;
    }

    return 0;
}

int deleteAfterQ(List &l, Node* q) {
    if (q != nullptr) {
        Node* node = q->next;
        if (node != nullptr) {
            q->next = node->next;
            if (l.tail == node) l.tail = q;
            delete node;
        }
        return 1;
    }

    return 0;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    // Init Linked List 
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    List l;
    l.head = node1;
    l.tail = node5;

    // Test 1
    printList(l); 
    EL;

    // Test 2
    int x = 4;
    if (search(l, x) != nullptr) {
        cout << x << " : ok\n";
    } else {
        cout << x << " : not found\n";
    }
    EL;

    // Test 3
    addHead(l, new Node(11));
    printList(l);

    addHead(l, new Node(8));
    printList(l);

    EL;

    // Test 4
    addTail(l, new Node(6));
    printList(l);

    addTail(l, new Node(7));
    printList(l);

    EL;

    // Test 5
    Node* q = search(l, 5);
    addAfterQ(l, q, new Node(21));
    printList(l);

    EL;

    // Test 6  
    deleteHead(l);
    printList(l);

    EL;

    // check status of list after delete or before add

    // Test 7
    Node* q = search(l, 3);
    deleteAfterQ(l, q);
    printList(l);

    // Test 8


    // Test 9
    





    return 0;
}

Leave a Comment