[C++] 연결리스트 직접 구현해보기

리스트

 

리스트는 데이터를 순서대로 나열한 자료구조이다.

리스트의 데이터는 노드(node) 혹은 요소(element)라고 하며,

가장 단순한 구조를 가진 리스트에는  선형 리스트(linear list)와 연결 리스트(linked list)가 있다.

 

오늘 나는 연결리스트를 직접 구현해 볼 예정이다.

연결리스트의 노드들은 다음 노드의 포인터만 가지고 있어서 1번 노드에서 3번노드에게 가려면 2번을 거쳐가야한다.

 

---

[LinekdList.h - 선언]

 

struct Node
{
	int data;
	Node* nextNode;
};

struct List
{
	Node* headNode;
	Node* curNode;
};

일단 값과 다음 노드의 포인터를 가지고있는 Node라는 구조체와 

headNode(리스트의 맨 앞 노드) 포인터, 현재 노드 포인터가 있는 List 구조체를 만들어주었다.

 

class LinkedList
{

public:

	List* list;

	LinkedList(); //생성자
	void InitList(); //리스트 초기화

	Node* Find(List* list,Node* node); //같은 노드 찾기
	void InsertHeadNode(int value); //맨 앞에 노드 삽입
	void InsertTailNode(int value); //맨 끝에 노드 삽입
	void RemoveHeadNode(); // 맨 앞 노드 삭제
	void RemoveTailNode(); // 맨 끝 노드 삭제
	void RemoveCurNode(); // 현재 선택한 노드 삭제
	void Clear(); // List 지우기
	void PrintCurNode(); // 현재 선택노드 출력
	void PrintAllNode(); //모든 노드 출력

};

 

List 포인터 변수와 연결리스트의 기능을 담당할 많은 함수들을 선언해주었다.

 

---

[LinkedList.cpp - 정의]

 

생성자와 초기화 함수

LinkedList::LinkedList()
{
    InitList();
}

void LinkedList::InitList()
{
    list = new List();
    list->curNode = nullptr;
    list->headNode = nullptr;
}

 

초기화 함수에서는 리스트를 생성하고 리스트의 노드변수들에 nullptr을 담아주었다.

그리고 생성자에서 초기화 함수를 호출했다.

 

 

 

---

 

노드 출력 함수들

void LinkedList::PrintCurNode()
{
    if (list->curNode != nullptr) 
    {
        std::cout << "현재 노드 : " << list->curNode->data << std::endl;
    }
    else //현재 노드가 없다면
    {
        std::cout << "프린트curNode 함수 - 현재 노드가 없습니다!" << std::endl;
    }
}

void LinkedList::PrintAllNode()
{

    if (list->headNode == nullptr) //노드가 하나도 없다면
    {
        std::cout << "프린트AllNode 함수 - 현재 노드가 하나도 없습니다!" << std::endl;
        return;
    }
        
    Node* tempNode = list->headNode;

    std::cout << "========= 전체노드 출력 시작 ==========" << std::endl;

    while (tempNode != nullptr)
    {
        std::cout << tempNode->data << std::endl;
        tempNode = tempNode->nextNode;
    }

    std::cout << "========= 전체노드 출력 끝 ==========" << std::endl;
}

현재 노드를 출력하는 함수에서는 리스트의 curNode를 검사해서 출력해주기만 했고,

 

모든 노드를 출력해야하는 PrintAllNode 함수에서는 반복할때마다 다음 노드를 tempNode에 대입해서 끝까지 반복하며 출력하게 만들었다.

 

---

노드 삽입 함수들

void LinkedList::InsertHeadNode(int value)
{
    Node* newNode = new Node();
    newNode->data = value;

    newNode->nextNode = list->headNode;
    list->headNode = list->curNode = newNode;
}

void LinkedList::InsertTailNode(int value)
{
    Node* newNode = new Node();
    newNode->data = value;

    if (list->headNode == nullptr)
    {
        list->headNode = newNode;
        list->curNode = newNode;
    }
    else
    {
        Node* tempNode = list->headNode;

        while (true)
        {
            if (tempNode->nextNode == nullptr)
            {
                tempNode->nextNode = newNode;
                list->curNode = newNode;
                 
                break;
            }

            tempNode = tempNode->nextNode;
        }
    }
}

 

맨앞 노드 삽입 함수 InsertHeadNode 함수에는 노드를 생성해서 다음 노드에 현재 맨앞 노드를 넣어주고,

리스트의 현재 노드와 맨 앞노드에 생성한 노드를 넣어주었다.

 

꼬리 노드 삽입 함수 InsertTailNode 함수에는 노드를 생성해서 현재 노드가 하나도없다면 맨 앞에 넣어주고,

아니라면 끝을 찾기위한 반복문을 돌리는 코드를 작성했다.

 

 

 

꼬리 삽입 1 => 전체 [ 1 ]

꼬리 삽입 2 => 전체 [ 1 , 2 ]

헤드 삽입 3 => 전체 [ 3, 1, 2 ]

헤드 삽입 4 => 전체 [ 4, 3, 1, 2  ]

 

순서대로 잘 나오고, 현재 노드 = 마지막 헤드 삽입(4) 까지 잘 나온다.

 

---

삭제 함수들

void LinkedList::RemoveHeadNode()
{
    if (list->headNode == nullptr)
    {
        std::cout << "RemoveHeadNode 함수 - 현재 노드가 하나도 없습니다!" << std::endl;
        return;
    }
    else
    {
        Node* tempNode = list->headNode;

        if (tempNode->nextNode != nullptr)
        {
            list->headNode = list->headNode->nextNode;
            list->curNode = list->headNode;

        }
        else
        {
            list->headNode = nullptr;
            list->curNode = nullptr;
        }
            
        delete tempNode;
    }
}

첫번째로 헤드를 지우는 RemoveHeadNode 함수다.

리스트에 노드가 있는지 검사를 해주고, tempNode함수에 현재 헤드 노드를 담아주었다.

 

만약 다음 노드가 있다면 그 노드를 헤드노드와 현재 노드로 만들어주고 지워버렸다.

다음 노드가 없다면 nullptr을 넣어주고 지운다.

 

 

 

void LinkedList::RemoveTailNode()
{
    if (list->headNode == nullptr)
    {
        std::cout << "RemoveTailNode 함수 - 현재 노드가 하나도 없습니다!" << std::endl;
        list->curNode = nullptr;
        return;
    }
        
    Node* preNode = nullptr;
    Node* tempNode = list->headNode;

    while (tempNode->nextNode != nullptr)
    {
        preNode = tempNode;
        tempNode = tempNode->nextNode;
    }

    if (preNode != nullptr)
        preNode->nextNode = nullptr;
    else //노드가 1개일경우
    {
        list->headNode = nullptr;
        list->curNode = nullptr;
    }

    delete tempNode;
}

두번째로 꼬리를 지우는 RemoveTailNode 함수다.

현재 노드가 있는지 검사해주고, tempNode에 현재 헤드노드(첫번째 노드)를 담아주었다.

while문으로 temp노드의 다음 노드가 없을때까지 반복문을 돌려서 다음 노드가 없는 노드를 찾아낸 후 지우면된다.

전 노드의 next노드를 지워줘야하기 떄문에, preNode 변수를 따로 선언해서 처리 해주었다.

 

 

void LinkedList::RemoveCurNode()
{
    if (list->curNode == nullptr)
    {
        std::cout << "RemoveCurNode 함수 - 현재 노드가 없습니다!" << std::endl;
        return;
    }
     
    Node* tempNode = list->headNode;

    if (tempNode == list->curNode)
    {
        RemoveHeadNode();
        return;
    }

    while (true)
    {
        if (tempNode->nextNode == list->curNode)
        {
            tempNode->nextNode = list->curNode->nextNode;
            delete list->curNode;
            list->curNode = tempNode;

            break;
        }

        tempNode = tempNode->nextNode;
    }
}

세번째는 현재 노드를 지우는 RemoveCurNode 함수다.

꼬리의 노드를 지우는 방법과 비슷한데, 일단 노드가 있는지 검사를 해준다.

그리고 현재 노드가 헤드 노드와 같다면 헤드 노드를 지운다.

 

위 조건에 걸리지 않았다면 tempNode변수에 헤드 노드(첫번째 노드)를 넣고 끝까지 반복하면서 NextNode가 CurNode인 경우를 찾아준다.

 

이렇게 찾는 이유는 list가 이전 노드의 포인터를 갖고있지 않기때문에, tempNode의 NextNode에 CurNode의 NextNode를 넣어주어야 하기 때문이다.

 

위의 조건을 찾았다면 tempNode의 다음 노드에 현재 노드의 다음 노드를 대입해주고, 현재 노드를 지워버린다.

그리고 현재 노드에 tempNode를 대입해준다.

 

 

void LinkedList::Clear()
{
    if (list->headNode == nullptr)
    {
        std::cout << "클리어 함수 - 현재 노드가 하나도 없습니다!" << std::endl;
        return;
    }
        
    Node* tempNode = list->headNode;

    while (tempNode != nullptr)
    {
        Node* deleteNode = tempNode;
        tempNode = tempNode->nextNode;

        delete deleteNode;
    }
    
    list->headNode = list->curNode = nullptr;
}

마지막은 list의 데이터를 다 지우는 Clear함수다.

그냥 위와같이 끝까지 탐색하며 다 지워버린다.

 

---

같은 값의 노드를 찾는 Find함수

Node* LinkedList::Find(List* list, Node* node)
{
    
    if (list->headNode == nullptr)
    {
        std::cout << "Find 함수 - 현재 노드가 하나도 없습니다!" << std::endl;
        return nullptr;
    }
        
    Node* tempNode = list->headNode;

    while (tempNode != nullptr)
    {
        if (tempNode != node && tempNode->data == node->data)
        {
            list->curNode = tempNode;

            return tempNode;
        }
        else
        {
            tempNode = tempNode->nextNode;
        }
    }

    return nullptr;
}

노드가 있는지 검사하고, 있다면 while문을 돌며 인자값으로 넘긴 노드와 같은 값을 가진 노드가 있는지 탐색한다.

값이 아니라 완전 같은 노드가 리턴되면 안되므로 조건을 따로 걸어주었다.

 

첫번째 노드(1) 과 같은 값을 탐색해서 6으로 바꿔주었다.

잘 작동한다.

 

---

금방 끝내지않을까 싶었는데 꽤나 애먹었다.

코드가 아쉬운 부분도 정말 많았지만 일단 기능만 구현하려고 억지로 막 만들었다..

그래도 공부 시작할때쯤엔 이해도 못했으니 대단한 발전이다.

꾸준히 공부를 해야겠다..