I'm taehee.won.

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

(참고 : 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)" 에 대하여 다루어 보도록 하겠다.

 전산학에서 자료 구조(資料構造, 영어: data structure)는 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상적 자료구조의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.

 자료 구조에는 여러 종류가 있으며, 이러한 각각의 자료구조는 각자의 연산 및 목적에 맞추어져 있다. 예를 들어 B-트리는 데이터베이스에 효율적이며, 라우팅 테이블은 네트워크(인터넷, 인트라넷)에 일반적이다.

 다양한 프로그램을 설계할 때, 어떠한 자료 구조를 선택할지는 가장 우선적으로 고려되어야 한다. 이는 큰 시스템을 제작할 때 구현의 난이도나 최종 결과물의 성능이 자료 구조에 크게 의존한다는 것을 많은 경험이 뒷받침하기 때문이다. 일단 자료구조가 선택되면 적용할 알고리즘은 상대적으로 명확해지기 마련이다. 때로는 반대 순서로 정해지기도 하는데, 이는 목표로 하는 연산이 특정한 알고리즘을 반드시 필요로 하며, 해당 알고리즘은 특정 자료구조에서 가장 나은 성능을 발휘할 때와 같은 경우이다. 어떠한 경우든, 적절한 자료 구조의 선택은 필수적이다.

 이러한 관점은 알고리즘보다 자료 구조가 보다 중요한 요소로 적용되는 많은 정형화된 개발론 그리고 프로그래밍 언어의 개발을 촉발시켰다. 대부분의 언어는 일정 수준의 모듈개념을 가지고 있으며, 이는 자료구조가 검증된 구현은 감춘 채 인터페이스만을 이용하여 다양한 프로그램에서 사용되는 것을 가능하게 해준다. C++, C나 자바와 같은 객체지향 프로그래밍 언어는 특별히 이러한 목적으로 객체를 사용한다.

 이러한 자료 구조의 중요성으로 말미암아, 최근의 프로그래밍 언어 및 개발 환경은 다양한 표준 라이브러리를 제공하고 있다. 예로, C++의 표준 템플릿 라이브러리나 자바의 자바 API, 마이크로소프트 .NET과 같은 것을 들 수 있다.

자료 구조에서 가장 기초적인 단위는 행렬, 레코드, 유니온, 참조와 같은 것이다. 예를들어, Nullable 참조는 참조와 유니온의 조합으로 나타낼 수 있으며, 가장 단순한 자료 구조 가운데 하나인 연결 리스트는 레코드와 Nullable 참조로 나타낼 수 있다.

(참고 : http://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

 사용자의 요구 분석을 하여, 설계, 구현, 테스트를 통하여 프로그램을 만들어내게 된다. 같은 요구 사항에 있어 같은 프로그램을 만들었다고 하더라도, 그 설계와 구현에 따라서 시스템, 곧 프로그램의 성능은 천차만별이다. 여기서 나는 많이 알려진 몇몇의 자료구조는 물론, 내가 프로그래밍을 하는데에 있어서 사용한 자료구조 형태에 대하여 이야기를 해보려 한다. 간단하게는 배열, 리스트는 물론, 특정 프로그램을 개발하기 위해 생각한 자료구조들도 함께 이야기 하려 한다. 내가 생각하고 설계한 자료구조가 최고의 선택이라고 말할 수 없듯, 어떻게 하면 효율적으로 설계를 할 것인가는 언제까지나 프로그래머에게 숙제로 남겨질 것이다.