I'm taehee.won.

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

 리스트의 첫번째 노드(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) 부터, 꼬리에 꼬리를 무는 방식으로 연결된 모든 노드의 메모리를 반환한다. 다음 노드의 포인터를 계속해서 임시로 저장해가며, 노드들의 메모리를 반환한다.

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

 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 연결 리스트의 종류로는 단순 연결 리스트, 이중 연결 리스트 등이 있다.

 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.
(참고 : http://ko.wikipedia.org/wiki/%EB%A7%81%ED%81%AC%EB%93%9C_%EB%A6%AC%EC%8A%A4%ED%8A%B8)

 프로그래밍을 하는데에 있어서 대다수의 프로그래머가 자료구조라 하면 제일 먼저 생각하는 것을 꼽으면, 스택, 큐, 리스트 등을 들 수 있다. 그 중에서 리스트는 이론적으로, 논리적으로 생각했을 때에 이해하기가 쉽고, 이해하기 쉬운만큼 구현상에 어려움이 적다.

 메모리를 위의 그림과 같은 "노드" 라는 단위로 나누어 사용하게 되는데, 노드는 데이터를 가지고 있는 메모리와 다음 노드를 가리키는 포인터로 구성되게 된다. 정적으로 메모리를 할당하여 사용하는 방식과 다르게, 저장할 데이터가 동적으로 생성되어야 하는 경우에 리스트를 이용하면 손 쉽게 구현할 수 있다.

 저장되어야 하는 데이터가 있을 때 마다, 노드를 하나씩 메모리에 할당하여, 데이터를 저장하고, 생성된 노드들을 하나의 묶음으로 보관하게 된다.

 위의 위키백과에서 설명한 자료의 추가와 삭제가 O(1) 의 시간에 가능하다는 점은, 예를 들어, 위의 그림에서 링크드 리스트의 가장 앞에 데이터를 추가하려고 한다면, 추가적인 연산없이 바로 메모리를 할당하여 추가하면 된다는 것이다.

 특정 위치의 데이터를 검색해 내는데에 O(n) 의 시간이 걸리는 단점은, 예를 들어, 위의 그림에서 데이터 "3" 을 찾고 싶다면, 데이터 "1", "2" 를 가진 노드를 거쳐서 3번의 탐색을 해야 데이터 "3" 을 찾을 수 있으며, 이와 같이 최악의 경우의 링크드 리스트의 가장 마지막 노드까지 탐색을 하게 되어, 노드의 갯수인 n 번의 탐색이 필요하다는 것이다.

 링크드 리스트는 자료구조의 가장 기본이라고 볼 수 있는 만큼, 확실히 이해하고, 자유자재로 구현을 할 수 있도록 하여야 한다. 이후에 이야기하게 될 대다수의 자료구조는 링크드 리스트를 이용하여 구현을 하게 된다.

 연결 리스트 (Linked-List) 에서는 "리스트의 기본 연산들" 다룬 후, "단순 연결 리스트(Single Linked-List)", "이중 연결 리스트(Double Linked-List)", "원형 연결 리스트(Circular Linked-List)" 에 대하여 다루어 보도록 하겠다.