[C++]Single LinkedList 구현

LinkedList란
단어 그대로 다음 데이터의 위치가 연결되어 선형으로 저장하는 방식이다.
각 요소는 노드(Node)라고 불르며 노드는 데이터와 다음 위치를 가르키는 포인터 로 구성되어 있다.

 

 

연결 리스트는 3종류가 존재한다.

• 단일 연결 리스트 (Singly Linked List)
• 이중 연결 리스트 (Doubly Linked List)
• 원형 연결 리스트 (Circular Linked List)

이번 구현은 Singly Linked List로 다음 위치만 가리키는 단일 연결 리스트 이다.

먼저 헤더에 Node 구조체와 각 리스트를 관리할 함수들을 구현했다.

#pragma once
#include <iostream>

using namespace std;

struct Node
{
    int data_;
    Node* nextNode_;
};

먼저 노드는 데이터를 담고 있는 data_와 다음 주소를 가리키는 Node* 를 담고 있다.

 

헤더의 구현부는 다음과 같으며 제일 앞 노드를 항상 가리키는 head_를 선언하여

리스트의 첫노드를 항상 가리키게 만들어준다.

class LinkedList
{
private:
    Node* head_;

public:
    LinkedList() { head_ = nullptr; }

    void AddFrontNode(int data);
    void AddLastNode(int data);
    void InsertNode(int num, int data);
    void DeleteNode(int num);

    Node* GetHead() { return head_; }
    void Print();
};

 

다음은 노드를 제일 앞에 추가하는 코드이다.

void LinkedList::AddFrontNode(int data)
{
    Node* tempNode = new Node;

    tempNode->data_ = data;
    tempNode->nextNode_ = head_;
    head_ = tempNode;
}

• 새로운 노드를 생성
• 새로운 노드에 데이터를 삽입
• 제일 앞에 추가하는 것이기 때문에 새로운 노드가 가리키는 다음 노드를 현재 Head로 넣어준다
• head를 제일 앞 노드를 가리키게 변경

전체 구현부는 아래에 추가

#pragma once
#include <iostream>

using namespace std;

struct Node
{
    int data_;
    Node* nextNode_;
};

class LinkedList
{
private:
    Node* head_;

public:
    LinkedList() { head_ = nullptr; }

    void AddFrontNode(int data);
    void AddLastNode(int data);
    void InsertNode(int num, int data);
    void DeleteNode(int num);

    Node* GetHead() { return head_; }
    void Print();
};

void LinkedList::AddFrontNode(int data)
{
    Node* tempNode = new Node;

    tempNode->data_ = data;
    tempNode->nextNode_ = head_;
    head_ = tempNode;
}

void LinkedList::AddLastNode(int data)
{
    Node* tempNode = new Node;

    tempNode->data_ = data;
    tempNode->nextNode_ = nullptr;

    if (head_ == nullptr)
    {
        head_ = tempNode;
    }
    else
    {
        Node* temp = head_;
        while (temp->nextNode_) {
            temp = temp->nextNode_;
        }
        temp->nextNode_ = tempNode;
    }
}

void LinkedList::InsertNode(int num, int data)
{
    if (num == 0)
    {
        AddFrontNode(data);
    }
    else
    {
        Node* newNode = new Node;
        newNode->data_ = data;

        Node* targetNode = head_;
        for (int i = 0; i < num - 1 && targetNode; ++i)
        {
            targetNode = targetNode->nextNode_;
        }

        if (targetNode == nullptr)
        {
            cout << "Out Of Range" << endl;
            delete targetNode;
        }
        else
        {
            newNode->nextNode_ = targetNode->nextNode_;
            targetNode->nextNode_ = newNode;
        }
    }
}

void LinkedList::DeleteNode(int num)
{
    if (head_ == nullptr)
    {
        cout << "No Header" << endl;
        return;
    }

    if (num == 0)
    {
        Node* currentNode = head_;
        head_ = head_->nextNode_;
        delete currentNode;
    }
    else
    {
        Node* currentNode = head_;

        for (int i = 0; i < num - 1 && currentNode; ++i)
        {
            currentNode = currentNode->nextNode_;
        }

        if (currentNode == NULL)
        {
            cout << "Out of Range" << endl;
        }
        else
        {
            Node* temp = currentNode->nextNode_;

            if (temp)
            {
                currentNode->nextNode_ = currentNode->nextNode_->nextNode_;
                delete temp;
            }
            else
            {
                cout << "No Header" << endl;
                return;
            }
        }
    }
}

void LinkedList::Print()
{
    Node* temp = head_;
    while (temp) {
        cout << temp->data_ << " -> ";
        temp = temp->nextNode_;
    }
    cout << "null" << endl;
}

 

추가로 테스트를 진행한 C++코드도 첨부하였다.

#include <iostream>
#include "LinkedList.h"
using namespace std;

int main()
{
	LinkedList* list = new LinkedList();

	int input = 0;
	while (0 <= input)
	{
		cout << "==================================================" << endl;
		list->Print();
		cout << "==================================================" << endl;
		cout << "1.맨 앞 추가, 2.맨 뒤 추가, 3.삽입, 4.삭제, 5.종료, 0.화면 클리어" << endl;
		cin >> input;

		switch (input)
		{
		default:
		{
			cout << "잘못입력했습니다." << endl;
		}
		break;

		case 0:
		{
			std::system("cls");
		}
		break;

		case 1:
		{
			cout << "추가할 값을 입력해주세요." << endl;
			int AddData = 0;
			cin >> AddData;

			list->AddFrontNode(AddData);
			cout << "추가 완료되었습니다." << endl;
		}

		break;

		case 2:
		{
			cout << "추가할 값을 입력해주세요." << endl;
			int AddData = 0;
			cin >> AddData;

			list->AddLastNode(AddData);
			cout << "추가 완료되었습니다." << endl;
		}

		break;

		case 3:
		{
			cout << "추가할 순서 및 데이터를 입력해주세요." << endl;
			int insertNum = 0;
			int data = 0;
			cin >> insertNum >> data;

			list->InsertNode(insertNum, data);
		}

		break;

		case 4:
		{
			cout << "삭제할 번호를 입력해주세요." << endl;
			int deleteNum = 0;
			cin >> deleteNum;

			list->DeleteNode(deleteNum);
		}
		break;

		case 5:
		{
			cout << "프로그램을 종료합니다." << endl;
			input = -1;
		}
		break;
		cout << "==================================================" << endl;
		}
	}

	delete list;
}