튜터링 단일 연결 리스트

단일 연결 리스트

#include <iostream>
#include <cstdio>
 
using namespace std;
 
class NODE {
private:
    friend class LIST;
    int data;
    NODE *next;
};
 
class LIST {
private:
    NODE *first, *last;
 
public:
    LIST() {
        first = last = NULL;
    }
    ~LIST() {
        // 소멸자 코드
    }
    // O(1)
    void insert(int val) {
        if (first == NULL) // or last == NULL
        {
            NODE *newNode = new NODE;
            newNode->data = val;
 
            first = last = newNode;
 
            newNode->next = NULL;
        }
 
        else if (last != NULL)
        {
            NODE *newNode = new NODE;
            newNode->data = val;
            newNode->next = NULL;
 
            last->next = newNode;
            last = newNode;
        }
    }
 
    // O(n)
    int del(int val) {
        NODE *cur = first;
 
        while (1) {
            if (cur == NULL)
                return -1;
 
            if (cur->data == val && cur == first)
            {
                first = first->next;
                delete cur;
 
                return 1;
            }
            else if (cur->next->data == val && cur->next == last)
            {
                NODE *tmp = last;
                last = cur;
 
                delete tmp;
 
                last->next = NULL;
 
                return 1;
            }
 
            if (cur->next->data == val)
            {
                // 찾았다.
                NODE *tmp = cur->next;
                cur->next = cur->next->next;
 
                delete tmp; // 노드를 지운다
 
                return 1;
            }
 
            else if (cur->next->data != val)
            {
                cur = cur->next;
            }
        }
    }
 
    // O(n)
    int find(int val) {
        NODE *cur = first;
        while (1){
            if (cur == NULL)
                return -1;
 
            if (cur->data == val)
                return 1;
 
            else if (cur->data != val)
                cur = cur->next;
        }
    }
 
    // O(n)
    void seeAll() {
        NODE *cur = first;
 
        while (cur != NULL)
        {
            cout << cur->data << " ";
            cur = cur->next;
        }
        cout << endl;
    }
};
int main()
{
    LIST list;
    list.insert(100);
    list.insert(200);
    list.insert(150);
 
    list.seeAll();
 
    list.del(150);
    list.seeAll();
 
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>