Chapter03 연결 리스트(Linked List) 1

03-1 추상 자료형: Abstract Data Type

컴퓨터 공학에서의 추상 자료형(Abstract Data Type)

추상 자료형! 간단히 ADT라고 불린다.

자료구조에서의 추상 자료형

추상 자료형(ADT): 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것

연산의 종류를 결정하는 것도 자료형 정의의 일부로 보아야 하고, 이러한 연산의 종류가 결정되었을 때 자료형의 정의는 완성된다.

'자료형'의 정의에 '기능' 혹은 '연산'과 관련된 내용을 명시할 수 있다는 것이다. 따라서 추상 자료형이라 하여 그것에 기능 혹은 연산과 관련된 내용을 명시할 수 없다는 생각을 버리기 바란다.

자료구조의 학습에 ADT의 정의를 포함합니다.

학습순서

1. 리스트 자료구조의 ADT를 정의한다.
2. ADT를 근거로 리스트 자료구조를 활요하는 main함수를 정의한다.
3. ADT를 근거로 리스트를 구현한다.

모든 자료구조는 그 내부 구현을 알지 못해도 활용할 수 있도록 구현할 것이다. 그리고 그렇게 하기 위해서는 ADT의 정의가 필수이다.

03-1 배열을 이용한 리스트의 구현

리스트의 이해

리스트라는 자료구조는 구현 방법에 따라서 다음과 같이 크게 두 가지로 나뉜다.

순차리스트 - 배열을 기반으로 구현된 리스트

연결리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트

"리스트 자료구조는 데이터를 나란히 저장합니다. 그리고 중복된 데이터의 저장을 막지 않습니다."

리스트 ADT를 정의하는데 있어서 고려해야 할 유일한 요소이다.

배열의 장점과 단점! 그리고 연결 기반 리스트

배열 기반 리스트의 단점

- 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.

- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

배열 기반 리스트의 장점

- 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.

"배열도 각종 자료구조의 구현에 중요한 도구이고, 그 자체로도 훌륭한 자료구조이다."