연결 리스트(Linked List)

■ 추상화 자료형(ADT : Abstract Data Type)

- 자료형(개념)과 기본연산 유형의 집합으로 기본연산을 문제해결 프로그램의 구현과 분리하여 모듈화 프로그래밍을 가능하게 하여 디버깅, 공동 프로그래밍, 시스템 확장 등이 용이함.
- 사례 : 리스트(list) 일련의 순서가 있는 자료(node)들의 집합
            (기본연산 : find, insert, delete, make_empty, print_list 등)

  추상화자료형은 모듈화 설계의 확장으로 볼 수 있으며, 일련의 연산형태를 모아 놓은 것으로 그러한 연산의 구현방법과 분리해 좋은 것이다. 정수나 실수를 자료형이라고 부르듯이 리스트, 집합, 그래프를 추상화자료형이라고 부른다. 정수나 실수를 가지고 덧셈과 곱셈을 하듯이 추상화자료형도 기본연산이 있다. 예를 들면 집합(set) 추상화자료형에서 집합의 통합(union), 요소의 탐색(find) 등을 기본연산으로 볼 수 있다. 자료추상화의 기본개념은 이러한 기본연산을 모듈화하여 프로그램하면 다른 곳에서는 도다시 프로그램하지 않고 함수호출에 의하여 불러 쓰도록 한다는 것이다. 따라서 프로그램 수정시 최소한의 노력만 필요하게 된다. 추상화자료형을 규정할 때에는 기본연산을 함께 규정하는데 어떠한 연산들을 기본연산으로 할 것이냐는 정해진 규칙이 없으며 설계자의 의도에 따라 달라진다. 요약하면 추상화자료형이란 자료형과 기본연산의 유형을 함께 규정하고 연산의 구현은 분리함으로써 모듈화 프로그램을 가능하게 하는 것이다.