I'm taehee.won.

 연결 리스트는 배열과 같이 크기가 정해져 있는 자료구조와 달리 메모리를 동적으로 사용할 수 있다는 장점이 있다. 반면, 다음 노드를 가리키는 포인터를 저장할 메모리를 사용해야 하기 때문에, 정적인 메모리 사용에 비해 메모리가 추가적으로 필요하다. 이와 같이 장점, 단점을 중심으로 연결 리스트를 비교 분석하려 한다.

 1. 배열 vs 연결 리스트

 아래와 같이 배열은 처음에 할당받은 메모리만큼 사용 할 수 있다. 실제 메모리 주소는 예로 든 그림과 다르지만 이해를 돕기 위해서 그려보았다. 아래와 같이 0x1000 부터 0x1006 까지 할당을 받게 되면, 7개의 영역을 사용할 수 있게 되며, 7개의 영역을 모두 사용하게 되면, 더 이상 메모리를 사용할 수 없게 된다.

 하지만 아래와 같이 메모리를 필요할 때 마다 할당을 받으면, 컴퓨터의 전체 메모리가 허락하는 한 계속해서 자료를 저장할 수 있게 된다. 사용하는 방법은, 0x1000 에 자료 "1" 을 저장하고, 0x1001 에 다음 자료가 저장되는 메모리 주소인 0x1002 를 저장한다. 이와 같은 방식으로 반복해서 메모리를 할당받아 자료를 저장한다.

 위와 같이 연결 리스트는 동적으로 메모리를 사용할 수 있다는 장점이 있지만, 자료를 저장하는 공간 이외에 다음 자료가 저장되는 메모리 주소를 저장함으로써 메모리를 추가적으로 사용한다는 단점이 있다.

 2. 단순 연결 리스트 vs 이중 연결 리스트

 단순 연결 리스트와 이중 연결 리스트는 메모리 주소를 하나 가지고 있느냐, 두개 가지고 있느냐의 차이가 있다. 이로 인해서 나타나는 차이는 노드를 리스트에서 삭제할 때 나타난다.

 위와 같이 단순 연결 리스트에서는 pstSLL_Temp_1 이 가리키는 노드를 삭제하기 위해서는, 리스트의 첫번째 노드에서 부터 탐색하여 pstSLL_Temp_1 의 앞 노드, 그림에서의 pstDLL_Temp_2 를 찾아야한다. 이는 그림에서의 하늘색 포인터를 다시 연결해주어야 하기 때문이다. 이 탐색은 최대 O(n-1) 의 시간을 소비하게 된다.(리스트의 마지막 노드를 삭제할 경우)

 반면, 아래 그림과 같이 이중 연결 리스트는 pstSLL_Temp_1 이 가리키는 노드를 삭제하기 위해 찾아야 하는 pstSLL_Temp_2 를 단 한번만에 찾을 수 있다. 이는 각각의 노드가 리스트에서 자신의 앞 노드를 가리키는 포인터를 가지고 있기 때문이다.

 위와 같이 이중 연결 리스트는 단순 연결 리스트에 비해 리스트에서 노드를 삭제할 때 효율적이라는 장점이 있지만, 하나의 포인터 메모리 공간이 더 사용하기 때문에, 메모리를 추가적으로 사용한다는 단점이 있다.

 3. 이중 연결 리스트 vs 원형 연결 리스트

 이중 연결 리스트와 원형 연결 리스트는 메모리의 사용에서 약간의 차이가 있을 뿐, 기본적인 구조는 차이가 없다. 하지만, 사용의 차이로 인해 리스트에 노드를 추가할 때에 효율이 차이가 나게 된다.

 위와 같이 이중 연결 리스트에서 리스트에 노드를 추가하기 위해서는 리스트의 마지막 노드를 찾아야하고, 이 탐색은 O(n) 의 시간을 소비하게 된다

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

 위와 같이 원형 연결 리스트는 구현하는 데에 있어서 조금 어려워진다는 단점 이외에는 리스트에 노드를 추가할 때에 효율적이다.

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

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

 단순 연결 리스트의 선언부이다.(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" 의 자료를 가지는 리스트가 만들어진다.

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

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

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

 단순 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

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

 단순 연결 리스트는 "연결 리스트 (Linked List) 정의" 에서 예로 든 것과 같이 꼬리에 꼬리를 무는 방식으로 메모리를 활용하여 데이터를 저장하는 방식이다.

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

 다음과 같이 단순 연결 리스트의 구조체를 선언하였다.

 단순 연결 리스트는 자료 공간과 한 개의 포인터 공간으로 나누어 생각할 수 있는데, 여기에서는 단순하게 자료 공간은 정수형(int) 자료 공간 하나만을 가지고 구현하고, 설명한다. DATA_TYPE unData 는 정수형 자료 공간을 가지게 되며, SLL *pstNextSLL 은 다음 노드를 가리킬 포인터 공간이다.

 가장 먼저 노드의 생성 함수를 만들었다.

 ifCreateSLL 함수는 return "i"(Integer) "f"(Function) "Create" "SLL"(Single Linked List) 이라는 의미로 명명하였다. 저장하고자 하는 데이터를 받아와서, 한개의 노드에 필요한 메모리를 할당한 후, 데이터를 저장하고, 생성한 노드의 주소를 저장한다. 사용할 때는 다음과 같이 포인터 변수를 선언하고, 함수에 포인터의 주소와 데이터를 매개변수로 넘기면 새로운 만들어진 노드의 주소가 매개변수로 넘긴 포인터에 저장된다.

 다음으로는 메모리를 할당한 노드의 사용이 끝났을 때, 해당 메모리를 반환하는 함수이다.

 ifDestorySLL 함수는 return "i"(Integer) "f"(Function) "Destory" "SLL" 이라는 의미로 명명하였다. free 함수는 포인터가 가리키고 있는 메모리 영역을 다시 힙 영역으로 돌리는 역할을 한다. 한번 메모리 영역을 되돌리면 다시 사용할 수 없다.

 다음은 마지막으로 단순 연결 리스트로 연결된 모든 노드의 메모리를 반환하는 함수이다.

 가장 처음 노드(Head) 부터, 꼬리에 꼬리를 무는 방식으로 연결된 모든 노드의 메모리를 반환한다. 다음 노드의 포인터를 계속해서 임시로 저장해가며, 노드들의 메모리를 반환한다.

 리스트는 배열과 달리 동적으로 메모리를 할당하여 사용할 수 있다는 장점이 있는 대신에, 사용하는 메모리를 효율적으로 사용하고, 반환해야할 필요성이 생긴다. 프로그램에서 메모리를 할당하고, 사용하지 않는 메모리를 반환하지 않는다면, 지속적으로 메모리 누수가 생겨 시스템이 더 이상 동작할 수 없게 될 수도 있다.