[자료구조] 단방향 연결리스트

요즘 회사 면접을 보며 느끼는 것은 신입에게 기본기가 참 중요하다는 것이었다.

알고리즘, 자료구조, 기본적인 구현 능력 등등...

 

어느 순간부터 기본기를 조금이라도 꼬아서 내면 대답을 어물쩡하는 나자신을 발견할 수 있었다

 

"연결리스트를 역으로 출력하려면 어떻게 해야하나요?"

"엄.... 이전 주소값을 저장해서 리스트의 값들을 타고 올라가면 되지 않을까요?" (자신감 없음)

 

 

그래서 부끄러움을 무릅쓰고!! 태초마을로 돌아갔다는 심정으로!

자료구조를 하나하나 구현해보기로 했다. ai의 도움 없이 자료구조를 직접 구현해보는 것이다

 

오늘은 단방향 연결리스트를 구현해보았다.

 

---

 

#include <iostream>
#include <stack>
using namespace std;

struct Node
{
    int value;
    Node* next;
};
Node* node = NULL;


void addNode(int m)
{
    if (node == NULL)
    {
        node = new Node();
        node->value = m;
        node->next = NULL;
    }
    else
    {
        Node* end = node;
        while(end->next != NULL)
        {
            end = end->next;
        }

        Node* newNode = new Node();
        newNode->value = m;
        newNode->next = NULL;
        end->next = newNode;
    }
}

void deleteNode(int d)
{
    Node* target = node;
    Node* prev = NULL;
    
    if (target == NULL) 
    {
        cout << "\n노드가 비어있습니다.\n";
        return;
    }
    
    while(target != NULL && target->value != d)
    {
        prev = target;
        target = target->next;
    }

    if (target == NULL) 
    {
        cout << "\n삭제할 값을 찾지 못했습니다.\n";
        return;
    }

    if (prev == NULL)
    {
        // 지울 값이 첫번째 노드였을 경우
        node = node->next;
    }
    else
    {
        prev->next = target->next;
    }

    delete target;
}


void print()
{
    Node* print = node;
    cout << "현재 노드: ";

    while(print != NULL)
    {
        cout << print->value << " ";
        print = print->next;
    }
}


// 연결 리스트를 거꾸로 출력하는 방법 1. 스택 활용
void printReverse1()
{
    Node* print = node;
    stack<int> s;
    
    while(print != NULL)
    {
        s.push(print->value);
        print = print->next;
    }
    
    while(!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
}


// 연결 리스트를 거꾸로 출력하는 방법 2. 재귀 활용
void printReverse2(Node* node)
{
    if (node ==  NULL) return;
    printReverse2(node->next);
    cout << node->value << " ";
}


int main() 
{
    int N;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        int M;
        cin >> M;
        addNode(M);
    }

    cout << "완성된 노드\n";
    print();
    
    int D;
    cout << "\n\n어떤 요소를 지우시겠습니까? ";
    cin >> D;
    deleteNode(D);

    cout << "\n지우고 난 후의 노드\n";
    print();

    cout << "\n\n스택을 활용해 거꾸로 출력\n";
    printReverse1();
    cout << "\n\n재귀를 이용해 거꾸로 출력\n";
    printReverse2(node);
    
    return 0;
}

 

<입력>
6
5 6 84 2 8 9
84

<출력> 
완성된 노드
현재 노드: 5 6 84 2 8 9 

어떤 요소를 지우시겠습니까? 
지우고 난 후의 노드
현재 노드: 5 6 2 8 9 

스택을 활용해 거꾸로 출력
9 8 2 6 5 

재귀를 이용해 거꾸로 출력
9 8 2 6 5

 

간단하게 구현해본 단방향 연결 리스트이다.

연결 리스트가 배열과 비교했을 때 어떤 차이점이 있는지 직접 구현해보며 알 수 있었다. 책으로 외우는 것보다 역시 직접 쳐보며 어떻게 구성되어 있는지 아는 것이 중요함을 깨닫았다

 

1) 연결 리스트는 왜 검색 시간이 O(N)일까?

이는 addNode와 deleteNode 함수 내부 while문을 보면 알 수 있다.

 

addNode 함수는 노드 내 값이 이미 존재할 경우, 끝값 뒤에 노드를 추가하기 위해 계속해서 끝값 탐색을 진행한다. 사람으로 치면 저 맛집의 줄이 어디까지 이어져 있는지를 훑어보는 것이다.

deleteNode 또한 입력받은 수의 값을 가진 노드를 찾기 위해 계속해서 value 값을 비교하는 것으로 찾고 있다.

 

배열은 인덱스로 빠르게 접근하지만, 연결 리스트는 주소를 따라서 요소를 찾는다.

 

 

2) 연결 리스트는 어떻게 거꾸로 출력할까?

// 연결 리스트를 거꾸로 출력하는 방법 1. 스택 활용
void printReverse1()
{
    Node* print = node;
    stack<int> s;
    
    while(print != NULL)
    {
        s.push(print->value);
        print = print->next;
    }
    
    while(!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
}


// 연결 리스트를 거꾸로 출력하는 방법 2. 재귀 활용
void printReverse2(Node* node)
{
    if (node ==  NULL) return;
    printReverse2(node->next);
    cout << node->value << " ";
}

 

이 스택과 재귀를 활용하는 방법 두 가지로 나뉜다.

나중에 들어가는 것이 먼저 나오는 스택과, 계속해서 함수가 반복되어 실행하다 기본 조건문에 의해 탈출하는 재귀 함수의 원리를 이용하면 된다!

 

내 생각엔 스택은 구조가 단순하니 재귀 함수 쪽으로 답변하는게 면접에서 좋아할 것 같지만,,,

 

 

---

 

 

이제 그 다음은 양뱡향 연결 리스트, 이중 연결 리스트를 만들어보기로 한다.

 

단순하게 Node 구조체에 prev 값을 추가하면 되는거 아니야? 싶지만,, (더보기)