노드 2(Node 2) timer 1초 memory 32MB

순서가 정해지지 않은 곳에 만들어진 (배열이 아닌 방식으로), 서로 연결된 자료구조를 연결 리스트 (Linked list) 라고 부른다.

이전 노드(Node) 문제에서 구현한 내용은 한쪽 방향으로만 연결되어 있기에, 단방향 연결 리스트 (Singly linked list)를 구현한 것이었다.

단, 이전 문제에서 살짝 이상한 점을 느낄 수 있는데, 데이터를 순서대로가 아닌, 역순으로 저장한다는 점이다.

만약 정방향으로 넣고 싶으면 어떻게 해야 할까?

아래 2가지 방식을 살펴보자.

• NULL (또는 None)을 활용한 예외 처리 방식

  노드가 하나도 없는 상황에서 예외 처리가 필요하다.

  

  노드가 없다면 p는 NULL을 가지고 있다. NULL은 특수한 값(0)으로, 존재하지 않는다는 의미를 가진다.

  여기서 노드가 추가된다면, 아래 그림과 같이 바뀐다.

  

  p의 값을 새로 만든 노드로 변경한다.

  이후 노드 추가는 p의 다음 노드를 가리키는 곳에 넣으면 된다.

• 더미(Dummy)노드를 활용한 방식 (추천)

  정보 분야에서 더미(Dummy)는 아무 정보가 없는 데이터를 의미한다.

  이 방식은 예외 처리를 없앨 수 있으며, 코드가 간결해진다.

  초기 상태는 아래와 같다.

  

  여기서 노드가 추가된다면, 아래 그림과 같이 바뀐다.

  

아래의 코드들은 위 그림의 과정이다.

NULL 방식의 예시 코드는 아래와 같다.

[C++]

struct Node{
    int data;
    Node* next;
    Node(int d){ data=d, next=nullptr; }
    Node(int d,Node*n){ data=d, next=n; }
};

int main(){
    Node*p = nullptr;
    if(p==nullptr){
        p = new Node(5);
    }
    else{
        p->next = new Node(5);
        p = p->next;
    }
    return 0;
}

[Python]

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

p = None
if p == None:
    p = Node(5)
else:
    p.next = Node(5)
    p = p.next

더미(Dummy)노드 방식의 예시 코드는 아래와 같다.

[C++]

struct Node{
    int data;
    Node* next;
    Node(int d){ data=d, next=nullptr; }
    Node(int d,Node*n){ data=d, next=n; }
};

int main(){
    Node*p = new Node(0); // Dummy node
    
    p->next = new Node(5);
    p = p->next;
    return 0;
}

[Python]

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

p = Node(0) # Dummy node

p.next = Node(5)
p = p.next

같은 식으로 노드를 계속 추가할 수 있다.

만약 여러 노드가 추가된다면 출력은 어떻게 해야 할까?

위 그림과 코드에서는 시작 위치를 놓치고 있는데, 이와 같이 된다면 출력할 수 없고, 지우기도 불가능하다.

이는 절대로 나와서는 안되는 심각한 상황이다. 이런 상황을 메모리 누수(Memory leak)라 부른다.

따라서 시작 위치를 따로 저장하면 된다. 이를 head라 부른다.

NULL 활용 방식은 최초로 노드가 추가되는 순간의 노드를 head로 저장하면 되고,

더미노드 방식은 더미노드를 head로 저장하면 된다.

[문제]

N개의 정수가 주어지면 연결 리스트에 저장 후 순서대로 출력하는 프로그램을 작성하시오. (1 \le N \le 10)