단일 연결 리스트(Single Linked List)

단일 연결 리스트

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct _NODE{
    int Data;
    //_NODE* Prev;
    _NODE* Next;
}NODE;

NODE* CreateNode();
NODE* FindNode(int Value);
NODE* FindPreviousNode(int Value);
void InsertRightNode(int Value, int NewData);
void InsertLeftNode(int Value, int NewData);
void HeadAppendNode(int Data);
void AppendNode(int Data);
void DisplayLinkes();
void LinkesClear();
void DeleteFirstNode();
void DeleteSpeciNode(int);
void DeleteLastNode();

NODE *head;

int main() {
    head = CreateNode();

    int n = 5;
    // int data;
    // cin >> n;
    NODE* arr[5];
    for(int i = 1; i <= n; i++){
        // cin >> data;
        AppendNode(i);
    }
    DisplayLinkes();
    HeadAppendNode(11);
    DisplayLinkes();
    InsertLeftNode(4, 5);
    DisplayLinkes();
    InsertLeftNode(11, 10);
    DisplayLinkes();
    InsertRightNode(10, 5);
    DisplayLinkes();
    InsertRightNode(11, 99);
    DisplayLinkes();
    HeadAppendNode(15);
    DisplayLinkes();
    DeleteFirstNode();
    DisplayLinkes();
    DeleteLastNode();
    DisplayLinkes();
    DeleteSpeciNode(99);
    DisplayLinkes();

    LinkesClear();
    DisplayLinkes();

}

NODE* CreateNode()
{
    NODE* temp = (NODE*)malloc(sizeof(NODE));
    //temp -> Prev = NULL;
    temp -> Next = NULL;
    return temp;
}

NODE* FindNode(int Value){ // 발견 노드 반환.
    NODE* curr = head -> Next;
    while(curr -> Data != Value){
        curr = curr -> Next;
    }
    return curr;
}

NODE* FindPreviousNode(int Value){ // 발견 노드 이전 노드 반환.
    NODE* curr = head -> Next;
    NODE* previous;
    if(head -> Next -> Data == Value){
        return head;
    }else{
        while(curr -> Data != Value){
            previous = curr;
            curr = curr -> Next;
        }
        return previous;
    }
}

void InsertRightNode(int Value, int NewData){
    NODE* temp = CreateNode();
    temp -> Data = NewData;
    NODE* curr = FindNode(Value);
    temp -> Next = curr -> Next;
    curr -> Next = temp;
}

void InsertLeftNode(int Value, int NewData){
    NODE* temp = CreateNode();
    temp -> Data = NewData;
    NODE* curr = FindPreviousNode(Value);
    if(head == curr){
        temp -> Next = head -> Next;
        head -> Next = temp;
    }else{
        temp -> Next = curr -> Next;
        curr -> Next = temp;
    }
}

void HeadAppendNode(int Data){
    NODE* temp = CreateNode();
    temp -> Data = Data;
    if(head -> Next == NULL){
        head -> Next = temp;
        temp -> Next = NULL;
    }else{
        temp -> Next = head -> Next;
        head -> Next = temp;
    }
}

void AppendNode(int Data){
    NODE* temp = CreateNode();
    temp -> Data = Data;

    if(head -> Next == NULL){
        head -> Next = temp;
        temp -> Next = NULL;
    }else{
        NODE* curr = head;
        while(curr -> Next != NULL){
            curr = curr -> Next;
        }
        curr -> Next = temp;
        temp -> Next = NULL;
    }
}

void DisplayLinkes(){
    NODE* tmp = head -> Next;
    while(tmp != NULL){
        cout << tmp -> Data << " ";
        tmp = tmp -> Next;
    }
    cout << endl;
}

void LinkesClear(){
    NODE* curr = head;
    while(curr != NULL){ // free가 아니라면?
        NODE* temp = curr;

        free(curr);
        curr -> Next = NULL;

        curr = temp;
        curr = curr -> Next;
    }
    // 새로운 변수를 만들고 삭제할 변수를 저장시키고 삭제할 변수를 삭제하면
    // 아무것도 없는(free된) 삭제한 변수에 새로운 변수를 대입한다.
}

void DeleteFirstNode(){
    NODE* curr = head ->Next;
    if(curr == NULL){
        return ;
    }else{
        head -> Next = curr -> Next;

        free(curr);
        curr -> Next = NULL;
    }
}

void DeleteSpeciNode(int Value){
    NODE* curr = head -> Next;
    NODE* previous;
    if(curr == NULL) return;
    else{
        while(curr -> Data != Value){
            previous = curr;
            curr = curr -> Next;
        }
        previous -> Next = curr -> Next;
        free(curr);
        curr -> Next = NULL;
    }

}

void DeleteLastNode(){
    NODE* curr = head -> Next;
    NODE* previous;
    if(curr == NULL){
        return ;
    }else{
        while(curr -> Next != NULL){
            previous = curr;
            curr = curr -> Next;
        }
        free(curr);
        curr -> Next = NULL;
        previous -> Next = NULL;
    }
}