Linked List (구조체 이용)

구조체와 포인터를 이용하여 Linked List를 만드는 예시이다.

우선 구조체는 데이터와 다음구조체의 주소를 가지는 포인터를 갖는다.

struct Data {
    int value;
    Data* pNext;
};

1. 입력

Data* pHead = NULL;
 
if (menu == 1)
{
    int input = 0;
    cout << "입력할 값은? : ";
    cin >> input;
 
    //새로운 구조체를 만들어 그 안에 값을 넣는다. pNext는 처음에는 널값으로 생성.
    Data* pNewData = new Data;
    pNewData->value = input;
    pNewData->pNext = NULL;
 
    // 헤드가 비어있다면 새로운 값을 헤더로
    if (pHead == NULL)
        pHead = pNewData;
    else
    {
        // 아니라면 temp에 헤드를 넣어준다.
        Data* temp = pHead;
        // 이후 헤드부터 Next가 존재하면 계속 타고가서 마지막까지감
        while (temp->pNext != NULL)
        {
            temp = temp->pNext;
        }
        // 마지막에서 pNext에 새로만든 구조체(pNewData)주소를 연결해준다.
        temp->pNext = pNewData;
    }
    cout << "값이 입력되었습니다. \n\n";
}

주석을 다 달아놨지만. 우선 Head가 존재한다. Head는 Linked List의 시작점을 뜻한다.

입력은 새로운 구조체를 생성해 그 안에 입력받은 value값을 넣어주고 pNext는 NULL로 생성한다.

그리고 Head가 비어있다면 새로운값을 연결해주고(주소를 넣어줌. 포인터니까)

Head에 값이 있다면 pNext를 따라 계속 다음주소로 넘어가고 그 다음주소로 넘어가고..

마지막주소에 도달하면 그다음값으로(pNext) 새로운값(pNewData)의 주소를 넣어주면 리스트가 연결될 것이다.

temp는 탐색하기 위한 변수라고 생각하면 이해에 도움이 될 것이다.

그림으로 그리자면 이런식이 될 것이다.

2. 출력

else if (menu == 2)
{
    Data* temp = pHead;
    if (pHead == NULL)
        cout << "입력된 값이 없습니다. \n\n";
    else {
        // Head부터 반복하면서 value값을 출력
        while (temp->pNext != NULL)
        {
            cout << temp->value << " ";
            temp = temp->pNext;
        }
        // 마지막값의 value값도 출력
        cout << temp->value << "\n\n";
    }
}

입력과 마찬가지로 temp를 이용하여 Head부터 쭉 타고가면서 value값을 순서대로 출력해준다.

즉 입력받은 순서대로 모든 값이 출력 될 것.

3. 삽입

else if (menu == 3)
{
    int input = 0;
    cout << "삽입할 값은? : ";
    cin >> input;
 
    // 새로운 데이터를 생성
    Data* pNewData = new Data;
    pNewData->value = input;
    pNewData->pNext = NULL;
 
    // Head가 비어있다면(데이터가 없다면) Head에 주소를 넣어줌
    if (pHead == NULL)
    {
        pHead = pNewData;
        cout << "저장된 값이 없어 첫번째값으로 입력됩니다. \n\n";
    }
    else
    {
        int num = 0;
        cout << "몇번째에 삽입하시겠습니까? : ";
        cin >> num;
 
        // 1번째에 삽입하면 새로운데이터가 Head가 되야함
        if (num == 1)
        {
            pNewData->pNext = pHead;
            pHead = pNewData;
        }
        // 아니라면 탐색하면서 중간에 삽입
        else
        {
            Data* temp = pHead;
            // 시작이 헤드(1)이므로 2번째칸에 넣고싶으면 1뒤에 넣으면됨(1~2사이니까 결국 1뒤)
            // 그렇기 때문에 2를 입력받으면 head 바로 뒤에 삽입하면 되므로 n-2
            for (int i = 0; i < num - 2; i++)
            {
                temp = temp->pNext;
            }
            // 기존 next값을 새값에 넣어주고 기존값의 next를 새값으로 바꿈
            pNewData->pNext = temp->pNext;
            temp->pNext = pNewData;
        }
    cout << "입력값이 삽입되었습니다 \n\n";
    }
}

삽입은 입력과 마찬가지로 새 데이터를 생성하고 Head가 비어있다면 입력과 마찬가지로 Head를 새값으로.

아니면 중간에 데이터를 연결해준다.

중간에 데이터를 삽입하려면 위의 그림처럼 next의 값을 newData의 next값에 넣어주고(빨간색 화살표)

기존데이터의 next에 newData의 주소를 넣어주면 가운데에 삽입이 될 것이다. (주황색 화살표)

그렇게되면 녹색화살표와 같은 순서대로 List가 연결된다.

4. 삭제

else if (menu == 4)
{
    // t1 = 현재주소값, t2 = 삭제를 위해 다음으로 먼저 넘어갈값
    Data* t1 = pHead;
    Data* t2 = pHead;
    if (pHead == NULL)
        cout << "입력된 값이 없습니다. \n\n";
    else
    {
        int deletedata;
        cout << "삭제할 값을 입력하세요 : ";
        cin >> deletedata;
 
        // Head를 삭제하면 Head를 다음으로 넘겨줌
        if (pHead->value == deletedata)
        {
            pHead = pHead->pNext;
            delete t1;
        }
        else
        {
            // 마지막까지 검색
            while (t2->pNext != NULL)
            {
                // t2를 앞으로 보내 삭제할 값이면 데이터를 연결하고 삭제
                t2 = t1->pNext;
                if (t2->value == deletedata)
                {
                    t1->pNext = t2->pNext;
                    delete t2;
                    break;
                }
                // 삭제할 값이 아니면 t1도 따라서 앞으로 넘어옴
                else
                    t1 = t1->pNext;            
            }
        }
        if (t2->pNext == NULL)
            cout << "해당 값을 찾지 못하였습니다. \n\n";
        else
            cout << "해당 값을 삭제하였습니다. \n\n";
    }
}

삭제는 검색할 때에 temp가 2개가 필요하다.

중간에 찾아버리고 삭제하면 List가 끊기기때문에 앞이랑 뒤를 연결해야 하므로 하나씩 따로 움직인다.

만약 삭제할 값이 Head면 삭제할 시 Head가 없어지므로 Head를 다음값(next)로 넘겨주고 데이터를 삭제.

아닌경우에는 t2가 먼저 넘어가서 삭제할값인지 확인하고,

맞다면 t1의 next에 t2의 next를 넣어 다음값으로 연결해 준 뒤 t2를 삭제하면 된다.

(이제 그림없어도 이해하실듯)

5. 종료

Data* t1 = pHead;
Data* t2 = pHead;
 
if (pHead != NULL)
{
    // 한칸 넘어가고 이전거 삭제 반복
    if (t2->pNext != NULL)
    {
        t2 = t1->pNext;
        delete t1;
        t1 = t2;
    }
    // 마지막도 
    delete t2;
}

우리는 구조체를 동적할당했기 때문에 프로그램이 종료되면 할당한 메모리를 다시 돌려주고 종료한다.