[C++] 단방향 리스트 구현

1. 이것은 무엇인가?

- STL에서 제공하며, 노드 기반 자료구조로 사용을 하는 리스트를 이해하기 위해 직접 구현해보았다.

 

2. 단방향 리스트 구조

- 아래의 글은 이 블로그의 'list 템플릿 클래스' 글에서 가져온 것이다.

- list는 다수의 node라는 데이터 구조로 이루어져있다.

- node는 값을 저장하는 data와 그 다음 노드의 주소값을 저장할 next로 이루어져있다.(여기서 이름은 임의로 지정한 것이다.)

- node는 그 다음 노드의 주소를 가리켜서 그 다음 노드를 접근할 수 있다.

- 그렇게 연속적으로 접근하면 가장 마지막 노드까지 접근할 수 있을 것이다.

- 이런 접근으로 데이터를 저장하고 다루는 것이 list이다.

- head는 가장 앞에 있는 노드이며 특정한 data를 지니지 않고 가장 앞 노드라는 의미를 지니기 위해 쓰는 노드이다.

- head의 다음 노드는 실질적 데이터를 저장할 첫 요소가 될 것이다.

- tail은 가장 마지막에 있는 노드이며 특정한 data를 지니지 않고 가장 마지막 노드라른 의미를 지니기 위해 쓰는 노드이다.

- tail을 이용해 이 tail 노드를 다음 주소값으로 가리키는 노드는 실질적 데이터를 지니는 마지막 노드임을 알 수 있다.

 

3. 요구 사항

- 리스트의 노드 추가(head와 tail로 통한 추가)

- 리스트의 노드 제거(head와 tail로 통한 제거)

- 리스트의 특정 데이터 제거

- 리스트 내의 특정 데이터 탐색

- 리스트 내의 모든 데이터 출력

 

4. 함수에 대한 설명

 4-1. Push_front(int)

void List::Push_front(int data)
{
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->Set_pNext(m_pHead->Get_pNext());
    m_pHead->Set_pNext(newNode);
}

- 새 노드를 생성해서 포인터로 저장한다.

- 생성한 노드의 데이터에 매개변수를 대입한다.

- 새 노드가 가리키는 다음 주소값에 head가 가리키는 주소값을 대입한다.

- head의 다음 주소값을 새 노드의 주소값으로 대입한다.

 

 4-2. Push_back(int)

void List::Push_back(int data)
{
    Node* last = m_pHead->Get_pNext();
    if (m_pHead->Get_pNext() == m_pTail)
    {
        last = m_pHead;
    }
    else
    {
        while (last->Get_pNext() != m_pTail)
            last = last->Get_pNext();
    }
        
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->Set_pNext(m_pTail);
    last->Set_pNext(newNode);
}

- tail이 아닌 실질적 데이터를 지니는 가장 마지막 노드를 저장할 노드 포인터를 만든다.

- 그 노드 포인터는 head의 다음 주소값을 저장한다. 즉, 노드 포인터는 실질적 데이터를 지닌 가장 맨 앞의 노드가 된다.

- head의 다음 주소값이 tail이면, 그 리스트는 실질적 데이터가 없다는 말이다.

- 그래서 노드 포인터에 head의 주소값을 저장한다. 왜냐면 조건문 다음 구문들은 새 노드를 생성해서 가장 마지막 노드와 tail 사이에 놓으려고 하는데, 가장 마지막 노드가 없으니 head와 tail 사이에 노드를 놓기 위해 이렇게 한다.

- 그 리스트에 값이 있다면 반복문을 돌린다. 조건은 노드 포인터의 다음 주소값이 tail이 아니면 노드 포인터는 그 다음 노드의 주소값을 가지면서 계속 마지막 노드를 찾으러 가는 것이다.

- 마지막 노드를 찾으면 Push_front와 비슷하게 새 노드를 생성해서 data를 대입하고 다음 주소값을 tail로 저장하고 가장 마지막 노드가 새 노드의 주소값을 가지게 하면 된다.

 

 4-3. Pop_front()

int List::Pop_front()
{
    Node* delNode = m_pHead->Get_pNext();
    Node* nextNode = m_pHead->Get_pNext();
    int delVal = delNode->GetData();
    if (delNode == m_pTail)
    {
        cout << "No Pop Front. Empty List." << endl;
        return 0;
    }
    else
    {
        while (delNode->Get_pNext() != nextNode)
            nextNode = nextNode->Get_pNext();

        m_pHead->Set_pNext(nextNode);
        delete delNode;
    }

    return delVal;
}

- 삭제할 노드를 저장할 노드 포인터(삭제 포인터), 삭제할 노드의 다음 노드를 저장할 노드 포인터(next 포인터)를 만든다. 동일하게 head의 다음 주소값을 저장한다.

- 만약 삭제 포인터가 tail과 같다면 그 리스트는 실질적 값이 없는 것이므로 함수를 종료한다.

- 그것이 아니라면 next 포인터가 삭제할 노드의 다음 주소값을 갖도록 한다.

- 그리고 head의 다음 주소값을 next 포인터를 저장하게 하고 아무도 가리키지 않는 삭제 포인터를 delete한다.

- 만약 삭제할 노드의 데이터 값이 필요할 상황이 있을 수 있어 delVal을 통해 반환하도록 했다.

 

 4-4. Pop_back()

int List::Pop_back()
{
    Node* delNode = m_pHead->Get_pNext();
    Node* tempNode = m_pHead->Get_pNext();
    if (delNode == m_pTail)
    {
        cout << "No Pop Back. Empty List" << endl;
        return 0;
    }
    else
    {
        if (delNode->Get_pNext() == m_pTail)
        {
            tempNode = m_pHead;
        }
        else
        {
            while (delNode->Get_pNext() != m_pTail)
                delNode = delNode->Get_pNext();

            while (tempNode->Get_pNext() != delNode)
                tempNode = tempNode->Get_pNext();
        }
    }
    
    tempNode->Set_pNext(m_pTail);
    int delVal = delNode->GetData();
    delete delNode;
    
    return delVal;
}

- 위와 동일하게 삭제 포인터를 만들고 head의 다음 주소값을 저장한다.

- 그리고 삭제할 노드의 앞 노드의 주소를 저장할 노드 포인터를 만든다. 이를 임시 포인터라고 하겠다.

- 만약 삭제 포인터가 tail이면 리스트에 실질적인 값이 없다는 이야기이므로 함수를 종료한다.

- 그것이 아니라면 다음 조건문을 진행한다. 만약 head의 다음 주소값을 저장한 삭제 포인터의 다음 주소값이 tail이라면 삭제 포인터의 앞 노드는 head이므로 임시 포인터에 head 주소값을 넣는다.

- 그것이 아니면, 리스트 가장 끝에 있을 삭제할 노드를 찾기 위해 반복문을 수행한다. 원리는 위 함수들과 동일하다.

- 그 다음 삭제할 노드의 앞 노드의 주소를 알기 위해 반복문을 수행한다. 원리는 위 함수들과 동일하다.

- 앞 노드를 저장하고 있는 임시 포인터의 다음 주소를 tail로 대입한다.

- 그리고 아무도 가리키지 않는 삭제 포인터를 delete한다.

- 만약 삭제할 노드의 데이터 값이 필요할 상황이 있을 수 있어 delVal을 통해 반환하도록 했다.

 

 4-5. Remove(int)

void List::Remove(int data)
{
    Node* SearchNode = m_pHead;
    if (SearchNode->Get_pNext() == m_pTail)
    {
        cout << "No Remove. Empty List." << endl;
    }
    else
    {
        while (SearchNode->Get_pNext() != m_pTail)
        {
            if (SearchNode->Get_pNext()->GetData() == data)
            {
                Node* delNode = SearchNode->Get_pNext();
                SearchNode->Set_pNext(delNode->Get_pNext());
                delete delNode;
                return;
            }
            SearchNode = SearchNode->Get_pNext();
        }
        cout << "No Remove. No data." << endl;
    }
}

- 찾아서 삭제할 노드를 저장하기 위한 노드 포인터를 만들어 head 주소값을 저장한다. 이를 서치 포인터라고 하자.

- 서치 포인터의 다음 주소값이 tail이라는 것은 리스트에 데이터가 없다는 뜻이다. 이 경우 함수를 종료한다.

- 그것이 아니라면 반복문을 수행한다. 서치 포인터의 다음 주소값이 tail이 아니라면 계속 반복문을 수행할 것이다.

- 반복문 내에는 조건문이 있다. 서치 포인터의 다음 주소값의 데이터가 찾고 있는 데이터라면, 삭제포인터를 만들어 서치 포인터의 다음 주소값을 저장한다.

- 서치 포인터의 다음 주소값을 삭제 포인터의 다음 주소값으로 대입한다.

- 그리고 삭제 포인터를 delete하고 함수를 종료한다.

- 만약 찾지 못했다면 지정한 출력문을 출력한다.

 

 4-6. Search(int)

bool List::Search(int data)
{
    Node* SearchNode = m_pHead;
    if (SearchNode->Get_pNext() == m_pTail)
    {
        cout << "No Search. Empty List." << endl;
    }
    else
    {
        while (SearchNode->Get_pNext() != m_pTail)
        {
            if (SearchNode->Get_pNext()->GetData() == data)
            {
                return true;
            }
            SearchNode = SearchNode->Get_pNext();
        }
    }
    return false;
}

 - Remove(int) 함수의 원리를 그대로 이용한 것이다. 설명은 따로 하지 않겠다.

 

 4-7. Print()

void List::Print()
{
    Node* SearchNode = m_pHead->Get_pNext();
    if (SearchNode == m_pTail)
    {
        cout << "No Print. Empty List." << endl;
    }
    else
    {
        while (SearchNode->Get_pNext() != m_pTail->Get_pNext())
        {
            cout << SearchNode->GetData() << " ";
            SearchNode = SearchNode->Get_pNext();
        }
    }
    cout << endl;
}

- 노드 하나씩 주소값을 저장하면서 데이터를 출력할 노드를 만들어 head의 다음 주소값을 저장한다. 이를 서치 포인터라고 하자.

- 만약 서치 포인터가 tail이라면 출력할 데이터를 가진 노드가 없기에 출력문을 출력하고 함수를 종료한다.

- 그것이 아니라면 반복문을 수행한다. 서치 포인터의 다음 주소값이 tail의 다음 주소값이 아닐 때까지 반복문을 수행한다. 만약 서치 포인터의 다음 주소값이 tail이 아닐 경우라고 하면 마지막 리스트 노드를 출력하지 못할 것이다.

- 반복문을 수행하며 서치포인터의 데이터를 출력하고 그 다음 주소값으로 저장한다.

 

5. 코드

 5-1. Header.h

#pragma once
#include<iostream>
using namespace std;

 5-2. Node.h

#pragma once
#include"Header.h"
class Node
{
private:
	int m_data;
	Node* m_pNext;
public:
	Node();

	int GetData() { return m_data; }
	Node* Get_pNext() { return m_pNext; }
	void SetData(int data) { m_data = data; }
	void Set_pNext(Node* pNext) { m_pNext = pNext; }
};

 5-3. Node.cpp

#include "Node.h"

Node::Node() : m_data(0)
{
	m_pNext = this;
}

 5-4. List.h

#pragma once
#include"Node.h"
class List
{
private:
	Node* m_pHead;
	Node* m_pTail;
public:
	List();

	void Push_back(int);
	void Push_front(int);

	int Pop_back();
	int Pop_front();

	void Remove(int);

	bool Search(int);
		
	void Print();
};

 5-5. List.cpp

#include "List.h"

List::List()
{
    m_pHead = new Node();
    m_pTail = new Node();
    m_pHead->Set_pNext(m_pTail);
    m_pTail->Set_pNext(nullptr);
}

void List::Push_front(int data)
{
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->Set_pNext(m_pHead->Get_pNext());
    m_pHead->Set_pNext(newNode);
}

void List::Push_back(int data)
{
    Node* last = m_pHead->Get_pNext();
    if (m_pHead->Get_pNext() == m_pTail)
    {
        last = m_pHead;
    }
    else
    {
        while (last->Get_pNext() != m_pTail)
            last = last->Get_pNext();
    }
        
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->Set_pNext(m_pTail);
    last->Set_pNext(newNode);
}

int List::Pop_back()
{
    Node* delNode = m_pHead->Get_pNext();
    Node* tempNode = m_pHead->Get_pNext();
    if (m_pHead->Get_pNext() == m_pTail)
    {
        cout << "No Pop Back. Empty List" << endl;
        return 0;
    }
    else
    {
        if (delNode->Get_pNext() == m_pTail)
        {
            tempNode = m_pHead;
        }
        else
        {
            while (delNode->Get_pNext() != m_pTail)
                delNode = delNode->Get_pNext();

            while (tempNode->Get_pNext() != delNode)
                tempNode = tempNode->Get_pNext();
        }
    }
    
    tempNode->Set_pNext(m_pTail);
    int delVal = delNode->GetData();
    delete delNode;
    
    return delVal;
}

int List::Pop_front()
{
    Node* delNode = m_pHead->Get_pNext();
    Node* nextNode = m_pHead->Get_pNext();
    int delVal = delNode->GetData();
    if (delNode == m_pTail)
    {
        cout << "No Pop Front. Empty List." << endl;
        return 0;
    }
    else
    {
        while (delNode->Get_pNext() != nextNode)
            nextNode = nextNode->Get_pNext();

        m_pHead->Set_pNext(nextNode);
        delete delNode;
    }

    return delVal;
}

void List::Remove(int data)
{
    Node* SearchNode = m_pHead;
    if (SearchNode->Get_pNext() == m_pTail)
    {
        cout << "No Remove. Empty List." << endl;
    }
    else
    {
        while (SearchNode->Get_pNext() != m_pTail)
        {
            if (SearchNode->Get_pNext()->GetData() == data)
            {
                Node* delNode = SearchNode->Get_pNext();
                SearchNode->Set_pNext(delNode->Get_pNext());
                delete delNode;
                return;
            }
            SearchNode = SearchNode->Get_pNext();
        }
        cout << "No Remove. No data." << endl;
    }
}

bool List::Search(int data)
{
    Node* SearchNode = m_pHead;
    if (SearchNode->Get_pNext() == m_pTail)
    {
        cout << "No Search. Empty List." << endl;
    }
    else
    {
        while (SearchNode->Get_pNext() != m_pTail)
        {
            if (SearchNode->Get_pNext()->GetData() == data)
            {
                return true;
            }
            SearchNode = SearchNode->Get_pNext();
        }
    }
    return false;
}

void List::Print()
{
    Node* SearchNode = m_pHead->Get_pNext();
    if (SearchNode == m_pTail)
    {
        cout << "No Print. Empty List." << endl;
    }
    else
    {
        while (SearchNode->Get_pNext() != m_pTail->Get_pNext())
        {
            cout << SearchNode->GetData() << " ";
            SearchNode = SearchNode->Get_pNext();
        }
    }
    cout << endl;
}