[C++] Container - List

저번에 알아봤던 vector에 이어 오늘은 list에 대하여 알아보자.

 

우선, list는 자료구조 시간에 배웠던 Linked List이다. 

 

Linked List(연결 리스트)?

 

우리는 앞서 배열이 연속된 메모리 공간을 할당 받는다는 사실을 공부했다.

 

그럼 List는 어떨까?

 

List의 경우 연속된 공간으로 메모리 공간을 할당받지 않는다. 즉, 메모리에 접근하기 위해서 인덱스 값을 가지고 접근할 수 없다. 그러면 어떻게 되어 있을까?

 

List의 그림

대략 이런 구조로 되어 있다. 그림이 개판이긴 하지만, 현재 List는 양방향 연결리스트를 표현 한 것이다. 리스트를 처음본 사람들은 이해할 수 없을 것이다. 그 이유는, "어라? 앞서 배운 배열과 달리 접근하려면 인덱스가 아닌 현재 객체의 다음 객체를 가리키는 포인터를 이용해서 접근해야 하는데, 이렇게 불편한 자료구조를 도대체 왜 사용하는 것이지?" 나도 처음에 배울 때는 그렇게 생각했었다. 하지만, 리스트의 핵심은 접근이 아니라 추가/제거이다. 즉, 객체를 자주 추가/제거 하는 경우에 많이 쓰인다. 왜 자주 추가제거하는데 리스트가 편리한가?

 

>> 이유는 다음과 같다. 배열의 경우 연속된 메모리 공간을 할당해야 하기 때문에, 배열의 크기를 늘리기 위해서는 재할당을 계속해서 해줘야 하고, 이는 추가/제거에 용이하지 않음을 의미하는데, 리스트의 경우, 메모리가 연속된 공간이 아니라, 그냥 마지막 객체에 연결만 해주면 끝이 난다. 즉, 재할당을 해줄 필요가 없다는 것이다.

 

리스트의 추가 제거의 과정에 대해 살펴보자.

추가 과정

그림을 보면 왼쪽이 원래 리스트이고, 오른쪽이 6이라는 요소를 추가한 모습이다.

그림으로만 봐도 정말 심플하지 않은가? 그저 맨 마지막 요소인 5의 다음번 포인터를 새로운 요소인 6에게 붙여준 뒤, 6의 이전포인터를 5로 설정했다. 정말 추가는 이게 끝이다. 너무 너무 간단하다. 배열에서의 재할당과 같은 부분은 전혀 필요없다. 하지만, 제거의 경우는 살짝 복잡하다.

삭제하는 그림

리스트를 제거하는 과정이다. 5번을 삭제하게 되면, 4번은 더이상 6번에 접근할 수 없다. 그러므로, 5번을 삭제할 경우 6번과 4번을 이어주는 과정 또한 필요하다. 이어서 리스트의 사용법에 대해 알아보고 직접 코드를 짜볼 것이다.

 

list의 사용 예

이 코드에서는 1 2 3 4 5를 추가한 후에 3을 삭제시키고 요소를 모두 출력하였다.

여기서 사용한 remove라는 함수는 인자로 들어가는 요소와 같은 모든 요소를 리스트에서 삭제시킨다. 이와 달리 erase라는 함수가 있는데, erase는 iterator를 받아 해당 iterator를 삭제하는 함수이다. 이는 아직 반복자에 대하여 모르기 때문에, 나중에 iterator를 공부할 때에 다시 보는 것으로 한다. 그리고 이 list를 직접 구현해 봤다.

 

-- 직접 구현

 

클래스 선언부

보면 일단, List를 Template으로 선언하고, 데이터를 삽입하는 push_back함수와 같은 값을 모두 삭제하는 remove함수를 구현하였다. 그리고 위에서는 반복자를 사용하여 리스트안의 모든 데이터를 뽑아냈지만, 반복자를 구현할 생각은 없으므로 ShowAll이라는 함수를 따로 만들었다.

 

사실 핵심은 Node 부분이다. 보면 next와 prev가 있다. 이는 양방향 연결리스트를 구현하기 위한 포인터이다. 그림으로 보는게 좋을듯 싶다.

양방향 포인터

노드는 서로를 연결하고 있다. 그러므로 다음 노드를 가리키는 next 노드와 이전 노드를 가리키는 prev노드를 필요로한다.

 

우리가 만들 리스트는 head와 tail을 가지고 있다. 이는 뭘 의미하는지 역시 그림으로 살펴보자

head, tail

head와 tail은 보는것처럼 처음과 마지막 노드를 가리키는 포인터 노드이다. 이 Head와 Tail이 필요한 이유는 뭘까?

- 1. 데이터의 추가/제거에 사용해야 하기 때문

- 2. 딱히 없어도 된다.

- 3. 그냥 head와 tail이 있으면 뭔가 있어보이니까

 

정답은 1번이다. 양방향 연결리스트를 구현하는데 있어서 head와 tail이 꼭 필요하다.

 

추가하는 모습을 그림으로 표현해보겠다.

추가 과정

처음에 아무노드도 추가하지 않았을 때 head와 tail이 있다.

이후 첫 노드가 추가되면 head의 next노드가 첫 노드를 가리키고, 첫 노드의 prev노드가 head를 가리키고, 첫 노드의 next 노드가 tail을 가리키고, tail의 prev노드가 첫 노드를 가리킨다.

여기까지 보면 head와 tail이 별로 의미가 없어 보일지도 모른다. 하지만, 3번째 노드를 추가하면서 중요성이 강조된다. 두번째 노드까지는 첫 번째 노드에 연결하면 된다. 하지만, 세 번째 노드는? 뭐 역시 두 번째 노드에서 연결하면 되긴 하지만, 두 번째 노드로 가기 위해 첫 번째의 next에 접근하고 뭐 이게 n번째까지 늘어나게 된다면 반복문을 매우 많이 돌려야 할 것이다. 하지만, 그렇게 하지 않고, tail노드를 가지고 있다면, 현재 tail 노드의 prev가 연결될 곳이니 새노드와 tail의 prev를 연결해주기만 하면 된다. 그러니, 반복문을 줄일 수 있다. 역시 말로 설명하는 것 보다는 코드를 보는 것이 이해가 더 빠를 것이다.

노드의 추가

코드를 보면, 맨 처음에는 head tail 모두 null이므로, 둘을 만들어 준다. 그리고, head와 tail에 새로운 노드를 연결한다.

else구문을 보면 위에서 했던 말이 이해가 갈 것이다. tail의 prev와 newNode를 연결해주는 과정이다. 이런 식으로 쭉 연결하면 리스트의 추가가 문제없이 구현될 것이다.

 

그럼 추가는 되었으니 이제 삭제는?

삭제도 역시 먼저 그림으로 그려서 나타내는 것이 좋을거 같다.

1번은 3개가 추가 되어있는 상태고 2번은 노드를 삭제하는 부분이다. 우리는 가운데에 있는 노드를 끊어버릴 것이다. 그러면 어떻게 해야할까? 바로, 가운데 노드의 전과 후를 서로 연결시켜주고, 가운데 노드가 가리키는게 없게 한 후에 가운데 노드를 삭제하면 된다. 코드로 확인하는 것이 훨씬 나을듯 싶다.

삭제

for문을 두개 사용한 이유는, 하나만 사용해서 reset할 경우 다음 노드에 접근할 수 없기 때문이다. 그래서 두개의 for문을 사용해 매개변수 data로 들어온 값을 모두 지울 수 있도록 하였다. 앞서 설명한 내용은 전부 코드로 확인할 수 있다.

 

ShowAll함수

그냥 리스트를 빙빙돌면서 모든 데이터를 출력해주는 함수이다.

 

그리하여 결과적으로 이렇게 구현해보았다.

완성

오늘은 list에 대하여 알아보았다. 길고 복잡할 수 있지만, 자료구조의 핵심이라고 봐도 될 정도로 매우 중요한 부분이다.

반복자를 공부할 때 좀 더 많은 부분을 살펴볼 예정이다. 오늘은 여기까지..