이중 연결 리스트 : 노드를 연결하는 포인터가 2개다.

 보통 C++의 STL에서는 double list를 많이 쓰는데요. 노드를 가리키는 포인터가 2개입니다. 각각 이전 것과, 다음 것을 가리키고 있습니다. 실제로, 이전 것도 가지고 있으면, 삭제하거나, 들어가야 하는 위치를 안다고 했을 때, 빠르게 자료구조에서 데이터를 삭제하거나, insert를 할 수 있어요. 기준 위치로부터 이전 노드의 주소도 알고 있기 때문입니다. 오늘은 이중 연결 리스트를 구현 해 보도록 하겠습니다.

 

 

---

 먼저 node형 구조체는 다음과 같이 선언합니다.

 

 

 각각, data를 담아두는 필드와, 이전 것 prev, 그리고 next를 가리키는 요소를 저장하고 있습니다. 다음에 head와 tail이 있는데요. 이것은 각각 리스트의 시작 위치와 끝나는 위치를 나타냅니다.

 

 

 그러면 연결 리스트를 초기화를 해야 할 건데요. 저는 미리, head와 tail을 서로 가리키게끔 해 놓았습니다. 이 둘은 더미 노드로 쓸 건데요. 이는 List의 삽입, 삭제 연산을 쉽게 하기 위해서 그리 한 겁니다.

 

 

 이렇게 더미를 생성하면, 데이터를 리스트에 추가할 때도, 삭제할 때도 1가지 경우만 고려하면 됩니다.

 

 

---

 저는 입력 받은 데이터를 사전 순으로 정렬하고 싶어요. 그러면 어떻게 해야 할까요? 일단, cur를 head로 잡고, cur_n의 초기값을 head의 next 원소를 가리키게 합시다. 예를 들어, at, b, c 순서대로 이어져 있다고 해 봅시다. 이 때, d를 추가하려면 어떻게 해야 할까요?

 

 

 먼저 cur가 head를 가리키고 있다면 cur_n은 현재 at을 가리키고 있을 거에요.

 

 

 그러면 우리는 cur_n이 넣을려는 문자열보다 사전순으로 뒤에 있거나, tail에 있다면 멈춥니다. 그렇지 않다면 cur과 cur_n을 각각 한 칸씩 다음 원소로 이동시켜야 겠지요.

 

 

 

 여기에서는 cur_n이 tail에서 멈출 겁니다. 그러면 어떻게 추가를 할 거냐면, cur 다음에 새롭게 추가하는 노드가 오고, 다음에 새롭게 추가하는 노드 다음에 cur_n이 오게 할 거에요.

 

 

 그러면, 일단 새롭게 생성한 노드를 _new라고 하면 _new의 next에는 cur_n이 와야 하고, _new의 이전 것에는 cur가 와야 합니다. 72번째 줄까지 수행했다면, 다음과 같이 그림이 그려질 겁니다.

 

 

 그런데 뭔가 부족한 것 같지 않나요? c의 다음 원소는 새롭게 추가된 d여야 하는데 바로 tail을 가리키고 있어요. 그리고 tail의 이전 원소는 새롭게 추가된 d여야 하는데 c를 가리키고 있어요. 그러면 어떻게 해야 할까요? cur_n의 prev가 _new를 가리키고 cur의 next가 _new를 가리키게 해야 할 거에요.

 

 

 이것까지 해 주면 새롭게 추가하는 노드가 제대로 연결된다는 것을 알 수 있어요. 중복된 문자열은 리스트에 추가가 안 되는데요. 이 부분은 67번째 줄로 컨트롤 하였습니다. P 다음에 N이 오고, P와 N 사이에 C를 삽입한다 했을 때, P 다음이 C를 잇고, C 다음이 N을 잇게 합니다. 그리고 N의 이전이 C를 잇게 하고, C의 이전이 P를 잇게 하면 됩니다. 차근 차근 그려보시면 쉽게 이해가 가시리라 생각이 듭니다.

 

 

---

 이제 삭제를 해 봅시다.

 

 

 저는 여기서 'c'를 삭제할 거에요. 역시, 삭제할 친구는 cur_n이 가리키고 있는데요.

 

 

 cur_n의 next는 d를 가리키고 있을 겁니다. cur_n->next의 값을 우리는 new_cur_next로 저장합시다. 일단 임시로 저장을 해 놓습니다. 그러면 new_cur_next는 d를 가리키고 있습니다. 대략적으로 그림을 그려보면 요래 됩니다.

 

 

 그러면 우리는 cur->next에 new_cur_next의 값을 넣고 new_cur_next->prev에 cur의 값을 넣으면 될 거에요.

 

 

 다음에 보라색으로 칠한 부분인 cur_next의 next와 prev는 값을 가질 필요가 없어요. 따라서 NULL을 넣어 줍니다.

 

 

 이 일련의 과정을 48번째 if에 걸린 블럭 안에서 수행하고 있어요. 정리하면 삭제할 이전 원소랑, 다음 원소의 위치를 각각 P, N이라고 했을 때, P와 N을 서로 잇기만 하면 된다는 거에요.

 

 

---

 리스트를 순회하는 것 또한 꽤 중요한 연산입니다.

 

 

 처음에 cur_n이 head의 바로 뒤를 가리키게 한 다음에 하나의 원소를 탐색할 때 마다, 출력해 주고 cur_n의 값을 다음 원소로 옮겨주기만 하면 됩니다. cur_n이 tail을 가리킬 때 까지. 전체적인 소스 코드는 chogahui05의 깃허브에 올려놓았습니다. 물론 여기에도 올려 놓았지만 부족하시다면 거기에 있는 자료들을 참고해 봐도 좋을 듯 싶어요.

 

 다음 시간에는, 이것을 이용해서 백준 사이트에 있는 몇 가지 문제들을 풀어보도록 하겠습니다.