이중 연결 리스트(Double Linked List) - Class 이용

Class를 이용한 이중 연결 리스트

기능 (삽입, 삭제, 탐색, 출력, 종료)

삽입 : 앞에서 부터 삽입하는 방식

삭제 : 삭제하고 싶은 값이 있는 노드를 찾아 삭제

탐색 : 탐색하고 싶은 노드가 몇 번째 위치에 있는지 확인

출력 : first -> last순으로 출력

last -> first순으로 출력 두가지 방식

<main.cpp>

#include "header.h"
 
int main()
{
    int n;
    int value;
 
    linkedList list;
 
    while (1)
    {
        cout << "1. 삽입 2. 삭제 3. 처음부터 출력 4. 마지막부터 출력 5. 탐색 6. 종료" << endl;
        cout << "원하는 번호를 입력하세요 :: ";
        cin >> n;
 
 
        switch (n)
        {
        case 1: cout << "값을 입력하세요 :: "; cin >> value; list.insert(value); cout << endl;
            break;
 
        case 2: cout << "값을 입력하세요 :: "; cin >> value; list.del(value); cout << endl;
            break;
 
        case 3: list.firstPrint(); cout <<"\n"<< endl;
            break;
 
        case 4: list.lastPrint(); cout << "\n" << endl;
            break;
 
        case 5: cout << "값을 입력하세요 :: "; cin >> value; list.search(value); cout  << endl;
            break;
 
        case 6:
            return 0;
        }
    }
 
}

<func.cpp>

#include "header.h"
 
// 생성자
linkedList::linkedList()
{
    /*
        처음에는 first, last가 NULL을 가리키게 한다.
    */
 
    first = NULL;
    last = NULL;
}
 
void linkedList::insert(int data)
{
    node *newNode = new node;
 
    // 처음 삽입 되는 노드라면
    if (first == NULL)
    {
        first = newNode;
        last = newNode;
 
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
    }
 
    else if(first != NULL)
    {
        // newNode에 data입력, 그리고 last의 right가 newNode를 가리키게 한다.
        // 그다음 left는 현재 last가 가리키고 있는것을 가리키고 right는 NULL을 가리키도록한다. 
        // 마지막으로 last가 newNode를 가리키도록 하는 순서로 한다.
 
        newNode->data = data;
        last->right = newNode;
        newNode->left = last;
        newNode->right = NULL;
        last = newNode;
        cout << "first :: " << first->data << " " << "last :: " << last->data << " " << endl;
    }
 
}
 
int linkedList::del(int data)
{
    // 아무 노드도 없는 상태에서 삭제를 하려고 시도하면
    if (first == NULL)
    {
        cout << "노드가 존재하지 않습니다." << endl;
        return 0;
    }
 
    int key = first->data;
    node *cur = first;
 
    while (1)
    {
 
        if (key == data)
        {
            /*
                값을 찾았다면 이때 현재 노드의 오른쪽 노드는 현재 노드의 왼쪽 노드를 가리키도록,
                현재 노드의 왼쪽 노드는 현재 노드의 오른쪽 노드를 가리키도록.
            */
            
            if(cur->right != NULL)
            cur->right->left = cur->left;
 
            if (cur->left != NULL)
            cur->left->right = cur->right;
 
            cout << cur->data << " 의 값을 가진 노드를 삭제 합니다." << endl;
 
            // 삭제 하려던 값이 마지막 first가 가리키던 값이었다면 first를 한칸 right 해준다.
            if (cur == first)
            {
                if (cur->right == NULL)
                    first = NULL;
                
                else
                    first = cur->right;
            }
 
            // 삭제 하려던 값이 마지막 last가 가리키던 값이었다면 last를 한칸 left 해준다.
            if (cur == last)
            {
                if (cur->left == NULL)
                    last = NULL;
                else
                    last = cur->left;
            }
 
            delete cur;
            break;
        }
 
        else
        {
            // 현재 위치가 마지막 노드일 때
            if (cur == last)
            {
                cout << "삭제 할 노드가 존재하지 않습니다." << endl;
                break;
            }
             
            else
            { 
                // 다음 노드를 가리키고, 다음 데이터를 가지도록 한다.
                cur = cur->right;
                key = cur->data;
            }
        }
    }
}
 
 
 
int linkedList::firstPrint()
{
    if (first == NULL)
    {
        cout << "노드가 존재하지 않습니다." << endl;
        return 0;
    }
    node *cur = first;
    int key = cur->data;
 
    while (cur != NULL)
    {
        cout << cur->data << " ";
        cur = cur->right;
    }
}
 
 
int linkedList::lastPrint()
{
    if (first == NULL)
    {
        cout << "노드가 존재하지 않습니다." << endl;
        return 0;
    }
    node *cur = last;
    int key = cur->data;
 
    while (cur != NULL)
    {
        cout << cur->data << " ";
        cur = cur->left;
    }
}
 
int linkedList::search(int data)
{
    if (first == NULL)
    {
        cout << "노드가 존재하지 않습니다." << endl;
        return 0;
    }
 
    node *cur = first;
    int key = cur->data;
    int count = 1;
    while (cur != NULL)
    {
        if (key == data)
        {
            cout << "탐색한 " << cur->data << " 값은 " << count << " 번째에 있습니다" << endl;
            return 1;
        }
 
        else
        {
            cur = cur->right;
            if(cur == NULL)
            {
                cout << "값이 존재하지 않습니다." << endl;
                return 0;
            }
 
            key = cur->data;
            count++;
        }
    }
 
 
}

<header.h>

#pragma once
 
#include <iostream>
 
using namespace std;
 
class node
{
    friend class linkedList;
 
private:
    int data;
    node *left;
    node *right;
};
 
class linkedList
{
private:
    node *first;
    node *last;
 
public:
    linkedList();
 
    void insert(int data);
    int del(int data);
    int search(int data);
    int firstPrint();
    int lastPrint();
 
};

결과 화면