본문으로 바로가기

Singly Linked List Data Structure

category Data Structure 2023. 9. 11. 22:29
#include<iostream>
using namespace std;

class Node {
public:
    int key;
    int data;
    Node* next;

    Node() {
        key = 0;
        data = 0;
        next = NULL;
    }

    Node(int k, int d) {
        key = k;
        data = d;
        next = NULL;
    }
};

class SinglyLinkedList {
public:
    Node* head;

    SinglyLinkedList() {
        head = NULL;
    }

    SinglyLinkedList(Node* n) {
        head = n;
    }

    // 1. Check if node exists using key value
    Node* nodeExists(int k) {
        Node* temp = NULL;
        Node* ptr = head;
        while (ptr != NULL) {
            if (ptr->key == k) {
                temp = ptr;
            }
            ptr = ptr->next;
        }
        return temp;
    }

    // 2. Append a node to the list
    void appendNode(Node* n) {
        if (nodeExists(n->key) != NULL) {
            cout << "Node Already exists with key value: " << n->key << ". Append another node with a different Key value" << endl;
        }
        else {
            if (head == NULL) {
                head = n;
                cout << "Node Appended" << endl;
            }
            else {
                Node* ptr = head;
                while (ptr->next != NULL) {
                    ptr = ptr->next;
                }
                ptr->next = n;
                cout << "Node Appended" << endl;
            }
        }
    }

    // 3. Prepend Node - Attach a node at the start
    void prependNode(Node* n) {
        if (nodeExists(n->key) != NULL) {
            cout << "Node Already exists with key value: " << n->key << ". Append another node with a different Key value" << endl;
        }
        else {
            n->next = head;
            head = n;
            cout << "Node Prepended" << endl;
        }
    }

    // 4. Insert a Node after a particular node in the list
    void insertNodeAfter(int k, Node* n) {
        Node* ptr = nodeExists(k);
        if (ptr == NULL) {
            cout << "No node exists with key value: " << k << endl;
        }
        else {
            if (nodeExists(n->key) != NULL) {
                cout << "Node Already exists with key value: " << n->key << ". Append another node with a different Key value" << endl;
            }
            else {
                n->next = ptr->next;
                ptr->next = n;
                cout << "Node Inserted" << endl;
            }
        }
    }

    // 5. Delete Node by unique key
    void deleteNodeByKey(int k) {
        if (head == NULL) {
            cout << "Singly Linked List already Empty. Can't delete" << endl;
        }
        else if (head != NULL) {
            if (head->key == k) {
                head = head->next;
                cout << "Node UNLINKED with key value: " << k << endl;
            }
            else {
                Node* temp = NULL;
                Node* prevptr = head;
                Node* currentptr = head->next;

                while (currentptr != NULL) {
                    if (currentptr->key == k) {
                        temp = currentptr;
                        currentptr = NULL;
                    }
                    else {
                        prevptr = prevptr->next;
                        currentptr = currentptr->next;
                    }
                }
                if (temp != NULL) {
                    prevptr->next = temp->next;
                    cout << "Node UNLINKED with key value: " << k << endl;
                }
                else {
                    cout << "Node doesn't exist with key value: " << k << endl;
                }
            }
        }
    }

    // 6. Update node
    void updateNodeByKey(int k, int d) {
        Node* ptr = nodeExists(k);
        if (ptr != NULL) {
            ptr->data = d;
            cout << "Node Data Updated Successfully" << endl;
        }
        else {
            cout << "Node doesn't exist with key value: " << k << endl;
        }
    }

    // 7. printing
    void printList() {
        if (head == NULL) {
            cout << "No nodes in singly linked list" << endl;
        }
        else {
            cout << endl << "Singly Linked Values : ";
            Node* temp = head;
            while (temp != NULL) {
                cout << "(" << temp->key << "," << temp->data << ") -->";
                temp = temp->next;
            }
            cout << endl;
        }
    }
};

https://www.youtube.com/watch?v=mDt53JLj8sM&list=PLIY8eNdw5tW_zX3OCzX7NJ8bL1p6pWfgG&index=12 

 

'Data Structure' 카테고리의 다른 글

Linked List  (0) 2023.05.29