C 로 구현한 알고리즘 - 2부 자료 구조, 5장 연결 리스트(linked list)

1부 준비가 끝나고 2부 자료구조의 시작이다.

알고리즘과 자료구조는 뗄 수 없는 관계니깐...

그 첫 번째로 연결 리스트(linked list)다.

연결 리스트라니.. 번역이 좀 그렇다.. 한글+영어가 좀 어색하네..

그냥 아래에서는 영문 그대로 적겠다.

솔직히 전산쪽 용어들은 오히려 그게 더 명확하니깐...

이 책에서 사용하는 소스코드들은

http://www.hanb.co.kr/exam/1063/

에서 다운받을 수 있다. 각 장에서 사용하는 소스파일 명은 중간중간 적어 두겠다.

링크드 리스트에는 다음과 같은 것들이 있다.

• 싱글 링크드 리스트 (single-linked list)

단일 연결 리스트. 각 항목들이 하나의 포인터로 연결된 가장 단순한 리스트.

(출처: http://en.wikipedia.org/wiki/Linked_list )

• 더블 링크드 리스트 (double-linked list) - 이중 연결 리스트

각 항목들이 두개의 포인터로 연결된 리스트. 양쪽 방향으로 포인터를 가지고 있다.

(출처: http://en.wikipedia.org/wiki/Linked_list )

• 서큘러 리스트 (circular list) - 원형 리스트

마지막 항목의 포인터가 NULL 대신에 첫 항목을 가리키는 연결 리스트. 리스트를 원형으로 순회할 수 있다.

(출처: http://en.wikipedia.org/wiki/Linked_list )

링크드 리스트를 사용하는 예에는 다음과 같은 것들이 있다.

메일링 리스트, 리스트(GUI 컴포넌트), 다항식, 메모리 관리(할당 가능한 메모리 영역 관리), LISP,

다른 자료구조들의 구현(스택, 큐, 집합, 해시 테이블, 그래프 등...)

예제 파일들
( list.h, list.c / dlist.h, dlist.c / clsit.h, clist.c )

상황에 따라 적절한 인터페이스가 추가/삭제가 될 수 있겠지만,

예제의 헤더 파일에서 기본적으로 필요한 인터페이스를 확인할 수 있다.

결론

책에서는 꽤 길게 설명을 해 두었지만,

링크드 리스트는 제일 쉬운 자료구조이다.

딱히 장황하게 적을 필요가 없다고 본다.

여기서부터 각 인터페이스에 대한 복잡도를 표시해 두었는데,

비단 링크드 리스트 뿐만 아니라, 다른 자료 구조에 대한

인터페이스의 복잡도도 알아두면 효율적으로 프로그램을 작성하는데 도움이 될 것이다.

Linked List 는 종종 Array 와 같은 다른 형태의 리스트와 비교되는데,

http://en.wikipedia.org/wiki/Linked_list

위 사이트의 글을 참고하면 되겠다.