I'm taehee.won.

 지금까지 만든 원형 연결 리스트가 올바르게 동작하는지 확인하기 위한 출력 함수를 구현하였다.

 함수의 종료를 판단하는 기준을 제외하면, 이중 연결 리스트와 동일하다.

 원형 연결 리스트의 선언부이다.(CircularDoubleLinkedList.h)

 노드의 생성과 관련된 함수(ifCreateCDLL), 소멸과 관련된 함수(ifDestroyCDLL, ifDestroyAllCDLL), 리스트로의 연결과 관련된 함수(vfAppendCDLL, vfInsertAfterCDLL), 탐색과 관련된 함수(pstfSearchLocationCDLL), 리스트에서의 연결 해제와 관련된 함수(ifRemoveCDLL) 로 이루어져 있다. 필요에 따라 함수를 수정, 추가, 구현하여 사용할 수 있다. 노드의 자료형을 추가한 후, 노드 생성함수를 수정하여 사용하거나, 리스트의 노드 중, 특정 노드 앞에 노드를 추가하는 함수를 추가, 구현할 수 있다.

 원형 연결 리스트의 구현부 이다.(CircularDoubleLinkedList.c)

 마지막으로 그 동안 구현한 원형 연결 리스트의 함수들을 사용하는 예제이다.

 vfPrintAllCDLL 함수가 호출되는 시점을 기준으로 다음과 같이 4 단계로 나눌 수 있다.

1 단계 : "1, 2, 3, 4, 5, 6, 7, 8" 의 자료를 가지는 노드를 각각 만들어 리스트에 연결

2 단계 : 리스트의 4 번째 노드를 찾아서, 리스트에서의 연결을 제거하고 소멸

3 단계 : 리스트의 5 번째 노드를 찾아서, 리스트에서의 연결을 제거한 후, 리스트의 처음 노드의 뒤에 연결

4 단계 : 리스트 전체 소멸

 위와 같은 결과가 출력된다. 조금 자세히 보면, 아래와 같이 4 번째 노드가 삭제되고, 5 번째 노드가 리스트의 처음 노드 뒤로 이동한 것을 확인할 수 있다.

  노드를 리스트에 추가하는 함수, 첫번째 노드부터 특정 위치에 있는 노드를 찾는 함수, 특정 노드의 다음 위치에 새로운 노드를 연결하는 함수이다.

 이중 연결 리스트와 비교하여 노드를 리스트에 추가하는 함수가 다르다. 단순 연결 리스트에 비해 이중 연결 리스트가 노드를 리스트에서 삭제할 때에 추가적인 연산이 필요없듯, 이중 연결 리스트에 비해 원형 연결 리스트는 노드를 리스트에 추가할 때에 추가적인 연산이 필요없다.

 아래 그림과 같이 단순 연결 리스트와 이중 연결 리스트에서는 노드를 리스트에 추가하기 위해서 리스트의 마지막 노드를 찾는 O(n) 의 추가적인 연산이 필요하다.

 하지만, 원형 연결 리스트는 아래 그림과 같이, 리스트의 첫번째 노드의 앞 노드를 가리키는 포인터가 이미 리스트의 마지막 노드를 가리키고 있으므로, 이를 찾는 연산이 필요없다. 이는 원형 연결 리스트의 장점이다.

 위의 세개의 함수를 사용하는 예제이다.

 먼저, 3개의 노드를 생성한 후에, pstSearchLocationCDLL, ifCreateCDLL, vfInsertAfterCDLL 순서로 수행하여, "1, 2, 4, 3" 의 자료를 가지는 리스트가 만들어진다.

 노드를 리스트에서 삭제하는 함수이다.

 이중 연결 리스트와 동일하다.

 원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

(참고 : http://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8)

 원형 연결 리스트는 메모리를 활용하여 데이터를 저장하는 방식이 이중 연결 리스트와 같다. 하지만, 이중 연결 리스트와 다른 점은 리스트의 첫번째 노드의 앞 노드를 가리키는 포인터가 마지막 노드를, 마지막 노드의 다음 노드를 가리키는 포인터가 첫번째 노드를 가리킨다는 점이다. 이는 이중 연결 리스트보다 이해하는 데에, 그리고 구현하는 데에 어려움을 준다. 반면, 리스트에 노드를 추가할 때의 수행 시간이 O(n) 에서 O(1) 로 줄어든다는 장점이 있다.

 그 밖에 메모리를 사용 등 모든 것은 이중 연결 리스트와 동일하다.

 다음은 원형 연결 리스트의 선언이다.

 이중 연결 리스트와 같다. 여기에서는 단순 연결 리스트를 설명할 때와 마찬가지로 자료 공간은 정수형(int) 자료 공간 하나만을 가지고 구현하고, 설명한다.

 다음은 노드의 생성 함수, 메모리를 할당한 노드의 사용이 끝났을 때, 해당 메모리를 반환하는 함수, 원형 연결 리스트로 연결된 모든 노드의 메모리를 반환하는 함수이다.

 이중 연결 리스트와 리스트로 연결된 모든 노드의 메모리를 반환하는 함수에서 다른 점이 있다. 이중 연결 리스트에서는 리스트의 마지막 노드의 다음 노드를 가리키는 포인터가 NULL 이었기 때문에, 함수의 끝이 명확하였지만, 원형 연결 리스트에서는 포인터가 항상 특정 메모리 주소를 가리키게 되기 때문에 함수의 끝이 명확하지 않다.

 포인터는 특정 주소를 가지고 있으므로, 이미 반환된 메모리라도, 주소값은 이전과 동일하다. 그러므로, pstInCDLL_Head 가 가리키고 있었던, 리스트의 첫번째 노드가 이미 메모리가 반환이 되었다고 해도, pstCDLL_Temp_1 != pstInCDLL_Head 와 같이 비교할 수 있다. 자세한 설명 및 사용에 관련된 사항은 이전 글 (링크 : [C] 단순 연결 리스트 (Single Linked List) 1. 정의 / 생성 / 소멸) 에서 확인할 수 있다.

 지금까지 만든 이중 연결 리스트가 올바르게 동작하는지 확인하기 위한 출력 함수를 구현하였다.

 첫번째 노드부터 순환하며, 리스트 내의 모든 노드의 데이터를 출력한다.

 이중 연결 리스트의 선언부이다.(DoubleLinkedList.h)

 노드의 생성과 관련된 함수(ifCreateDLL), 소멸과 관련된 함수(ifDestroyDLL, ifDestroyAllDLL), 리스트로의 연결과 관련된 함수(vfAppendDLL, vfInsertAfterDLL), 탐색과 관련된 함수(pstfSearchLocationDLL), 리스트에서의 연결 해제와 관련된 함수(ifRemoveDLL) 로 이루어져 있다. 필요에 따라 함수를 수정, 추가, 구현하여 사용할 수 있다. 노드의 자료형을 추가한 후, 노드 생성함수를 수정하여 사용하거나, 리스트의 노드 중, 특정 노드 앞에 노드를 추가하는 함수를 추가, 구현할 수 있다.

 이중 연결 리스트의 구현부 이다.(DoubleLinkedList.c)

 마지막으로 그 동안 구현한 이중 연결 리스트의 함수들을 사용하는 예제이다.

 vfPrintAllDLL 함수가 호출되는 시점을 기준으로 다음과 같이 4 단계로 나눌 수 있다.

1 단계 : "1, 2, 3, 4, 5, 6, 7, 8" 의 자료를 가지는 노드를 각각 만들어 리스트에 연결

2 단계 : 리스트의 4 번째 노드를 찾아서, 리스트에서의 연결을 제거하고 소멸

3 단계 : 리스트의 5 번째 노드를 찾아서, 리스트에서의 연결을 제거한 후, 리스트의 처음 노드의 뒤에 연결

4 단계 : 리스트 전체 소멸

 위와 같은 결과가 출력된다. 조금 자세히 보면, 아래와 같이 4 번째 노드가 삭제되고, 5 번째 노드가 리스트의 처음 노드 뒤로 이동한 것을 확인할 수 있다.

  노드를 리스트에 추가하는 함수, 첫번째 노드부터 특정 위치에 있는 노드를 찾는 함수, 특정 노드의 다음 위치에 새로운 노드를 연결하는 함수이다.

 단순 연결 리스트와 비교하여 다른 점은 리스트를 추가할 때에, 이전 노드를 가리키는 포인터를 연결하는 부분과, 특정 노드 다음 위치에 새로운 노드를 연결할 때에, 넣는 위치 앞, 뒤에 있는 노드의 다음, 이전 노드를 가리키는 포인터도 다시 새로 연결해주는 점이다. 단순 연결 리스트의 자세한 설명 및 사용에 관련된 사항은 이전 글 (링크 : [C] 단순 연결 리스트 (Single Linked List) 2. 추가 / 탐색 / 삽입 / 삭제) 에서 확인할 수 있다.

 위의 세개의 함수를 사용하는 예제이다.

 먼저, 3개의 노드를 생성한 후에, pstSearchLocationDLL, ifCreateDLL, vfInsertAfterDLL 순서로 수행하여, "1, 2, 4, 3" 의 자료를 가지는 리스트가 만들어진다.

 이전에 설명했던 단순 연결 리스트에 비하여 포인터를 하나 더 생각하고, 구현해야 한다는 점에서 어려움이 있다.

 노드를 리스트에서 삭제하는 함수이다.

 단순 연결 리스트와 달리 노드의 삭제를 위해 삭제할 노드를 가리키는 노드, 곧, 삭제할 노드의 앞 노드를 찾을 필요가 없다. 이중 연결 리스트는 삭제할 노드의 앞 노드를 가리키는 포인터 공간이 있기 때문이다. 이로 인해서 이중 연결 리스트의 장점인 리스트의 연결 제거시에 추가적인 연산 시간이 필요없다.

 이중 연결 리스트의 구조는 단순 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

(참고 : http://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8)

 이중 연결 리스트는 단순 연결 리스트에서와 같이 꼬리에 꼬리를 무는 방식으로 메모리를 활용하여 데이터를 저장하는 방식이다. 하지만, 단순 연결 리스트와 다른 점은 다음 노드에 대한 주소값 뿐 아니라, 이전 노드에 대한 주소값도 저장하고 있다는 점이다. 이는 이해하는 데에, 그리고 구현하는 데에 약간의 어려움을 주고, 하나의 노드가 생성될 때 마다, 단순 연결 리스트에 비하여 주소값을 저장할 메모리 공간을 더 쓰게 된다는 단점이 된다. 반면, 리스트에서의 삭제 수행 시간이 최대 O(n-1) 에서 O(1) 로 줄어든다는 장점이 있다.

 사용하는 메모리에 모두에 대한 주소값을 저장할 필요없이 가장 첫번째 노드(Head) 에 대한 주소값만 저장하고 있으면, 필요에 따라 꼬리에 꼬리를 물어가며 필요한 데이터를 찾을 수 있다는 점은 단순 연결리스트와 동일하다.

 다음은 이중 연결 리스트의 구조체의 선언이다.

 단순 연결 리스트의 구조체와 비슷하지만, 이전 노드를 가리킬 포인터 공간을 추가적으로 가지고 있다. 여기에서는 단순 연결 리스트를 설명할 때와 마찬가지로 자료 공간은 정수형(int) 자료 공간 하나만을 가지고 구현하고, 설명한다.

 다음은 노드의 생성 함수, 메모리를 할당한 노드의 사용이 끝났을 때, 해당 메모리를 반환하는 함수, 이중 연결 리스트로 연결된 모든 노드의 메모리를 반환하는 함수이다.

 이중 연결 리스트의 생성, 소멸과 관련된 함수는 단순 연결 리스트와 다른 점이 거의 없다. 이전 노드를 가리킬 포인터 공간에 대해 연산이 필요없기 때문이다. 자세한 설명 및 사용에 관련된 사항은 이전 글 (링크 : [C] 단순 연결 리스트 (Single Linked List) 1. 정의 / 생성 / 소멸) 에서 확인할 수 있다.

 프로그래밍을 하다보면, 글꼴에 따라서 개발 효율이 달라질 수 있다. 특히, 영문소문자 o(오), 영문대문자 O(오), 숫자 0(영), 영문소문자 l(엘), 영문대문자 I(아이) 를 구분하기 쉬운, 고정 폭 글꼴의 선택은 필수다. 글꼴의 선택에 관해서는 다음 글에서 이야기하도록 하고, 이 글에서는 글꼴을 바꾸는 방법에 대해 이야기 한다.

 다음은 이클립스에서 글꼴을 바꾸는 방법이다. 이클립스 메뉴 중 "Window" 의 "Preferences" 를 선택한다.

 Preferences 창이 열리면, 아래의 그림에 적혀있는 순서에 따라서 진행한다.

 1. "General" 카테고리 열기 -> 2. "Appearance" 카테고리 열기 -> 3. "Colors and Fonts" 선택 -> 4. "C/C++" 카테고리 열기 -> 5. "Editor" 카테고리 열기 -> 6. "C/C++ Editor Text Font" 선택 (Eclipse 에서 사용하는 모든 글꼴을 바꾸거나, 기타 창들의 글꼴을 바꾸고 싶을 경우, Basic, Debug 등의 다른 카테고리의 글꼴을 선택) -> 7. "Edit..." 선택

 원하는 글꼴, 글꼴 스타일, 크기 선택 후, "확인" 선택 -> 이전 창에서 "OK" 선택

 다음과 같이 글꼴이 바뀐 것을 확인할 수 있다.

 프로그래밍을 하다보면, 코드의 길이가 늘어나고, 그로 인해서 내가 확인하고자 하는 코드가 어디에 있는지, 현재 보고 있는 코드는 전체 코드 중 어디에 위치하는지 정확히 확인하고 싶을 때가 생긴다. 또, 컴파일 시 에러나 경고가 났을 때에 어디에 문제가 있는지 찾기 위해서는 코드의 줄 번호를 확인할 필요가 있다.

 다음은 이클립스에서 줄 번호를 확인하는 방법이다.

 이클립스 메뉴 중 "Window" 의 "Preferences" 를 선택한다.

 Preferences 창이 열리면, 아래의 그림에 적혀있는 순서에 따라서 진행한다.

 1. "General" 카테고리 열기 -> 2. "Editors" 카테고리 열기 -> 3. "Text Editors" 선택 -> 4. "Show line numbers" 체크박스 체크 -> 5. "OK" 선택

 다음과 같이 작성한 코드 왼쪽에 줄 번호가 보이는 것을 확인할 수 있다.

 지금까지 만든 단순 연결 리스트가 올바르게 동작하는지 확인하기 위한 출력 함수를 구현하였다.

 첫번째 노드부터 순환하며, 리스트 내의 모든 노드의 데이터를 출력한다.

 단순 연결 리스트의 선언부이다.(SingleLinkedList.h)

 노드의 생성과 관련된 함수(ifCreateSLL), 소멸과 관련된 함수(ifDestroySLL, ifDestroyAllSLL), 리스트로의 연결과 관련된 함수(vfAppendSLL, vfInsertAfterSLL), 탐색과 관련된 함수(pstfSearchLocationSLL), 리스트에서의 연결 해제와 관련된 함수(ifRemoveSLL) 로 이루어져 있다. 필요에 따라 함수를 수정, 추가, 구현하여 사용할 수 있다. 노드의 자료형을 추가한 후, 노드 생성함수를 수정하여 사용하거나, 리스트의 노드 중, 특정 노드 앞에 노드를 추가하는 함수를 추가, 구현할 수 있다.

 단순 연결 리스트의 구현부 이다.(SingleLinkedList.c)

 마지막으로 그 동안 구현한 단순 연결 리스트의 함수들을 사용하는 예제이다.

 vfPrintAllSLL 함수가 호출되는 시점을 기준으로 다음과 같이 4 단계로 나눌 수 있다.

1 단계 : "1, 2, 3, 4, 5, 6, 7, 8" 의 자료를 가지는 노드를 각각 만들어 리스트에 연결

2 단계 : 리스트의 4 번째 노드를 찾아서, 리스트에서의 연결을 제거하고 소멸

3 단계 : 리스트의 5 번째 노드를 찾아서, 리스트에서의 연결을 제거한 후, 리스트의 처음 노드의 뒤에 연결

4 단계 : 리스트 전체 소멸

 위와 같은 결과가 출력된다. 조금 자세히 보면, 아래와 같이 4 번째 노드가 삭제되고, 5 번째 노드가 리스트의 처음 노드 뒤로 이동한 것을 확인할 수 있다.

 노드를 리스트에 추가하는 함수이다.

 리스트의 첫번째 노드(Head) 와 연결될 노드(New) 를 매개변수로 받아와서, 리스트의 꼬리에 연결하는 역할을 한다. 이전에 모든 노드의 메모리를 반환하는 함수를 설명하면서, 첫번째 노드에서 다음 노드로 탐색하는 것을 설명하였으므로, 앞으로는 간단하게 설명을 붙이도록 하겠다.

 첫번째 노드가 없다면, 첫번째 노드가 새로운 노드를 가리키도록 한다. 첫번째 노드가 존재한다면, 현재 가리키고 있는 노드의 다음 노드가 있는지 계속해서 탐색해서, 다음 노드가 없는 노드, 곧, 꼬리 노드의 다음에 새로운 노드를 연결한다.

 다음은 첫번째 노드부터 특정 위치에 있는 노드를 찾는 함수이다.

 첫번째 노드부터 다음 노드를 탐색하는 루틴을 매개변수로 받아온만큼 하여, 해당 노드를 반환한다.

 다음은 특정 노드의 다음 위치에 새로운 노드를 연결하는 함수이다.

 위의 세개의 함수를 사용하는 예제를 간단하게 만들어 보았다.

 먼저, 3개의 노드를 생성한 후에, pstSearchLocationSLL, pstCreateSLL, vfInsertAfterSLL 순서로 수행하여, "1, 2, 4, 3" 의 자료를 가지는 리스트가 만들어진다.

 모든 노드를 생성하여 사용 후에는, 꼭 메모리를 반환하는 습관을 들여야 한다.

 노드를 리스트에서 삭제하는 함수이다.

 리스트에서 노드를 삭제하기 위해서는 삭제할 노드를 가리키는 노드, 곧, 삭제할 노드의 앞 노드를 찾아야한다. 앞 노드가 가리키는 다음 노드가 삭제할 노드의 다음 노드가 되면, 삭제하고자 하는 노드는 없어지더라도 리스트는 정상적으로 동작할 수 있다.