Introduction to Data Structures Using C
ADT 추상 자료형 : 구체적인 기능의 완성 과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것
사용자가 정의한 구조체도 자료구조의 일종인데 이에 대한 정의는 알 필요 없음, 기능을 묘사하고 있으면 됨. 즉 구조체를 사용할 때 구조체 내의 멤버가 어떻게 구성이 되어 있는지를 알 필요 없음, 알고 싶으면 그에 관련된 연산(기능)을 ADT에 추가하는 것이 맞음, 구조체의 멤버에 직접 접근 X
리스트
- 순차 리스트 : 배열을 기반으로 구현된 리스트
- 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트
리스트 자료구조는 데이터를 나란히 저장한다. 그리고 중복된 데이터의 저장을 막지 않는다.
p. 83
모든 자료구조는 내부적으로 다양한 정보를 담게 된다. 데이터뿐만 아니라 그 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담긴다. 따라서 이와 관련된 변수들의 초기화가 선행되어야 한다.
ListInit
리스트 내에서 '데이터의 참조 위치'를 기록함. 따라서 처음부터 참조를 새롭게 시작하기 위해서는 이 정보를 초기화해야 함. 이를 목적으로 LFirst 함수의 호출을 요구하는 것임
First → LNext → LNext → ...
typedef ArrayList List;
typedef LinkedList List;
typedef로 선언을 해 놓으면, List에 다른 이름을 부여하는 것만으로도 사용하는 리스트의 종류를 바꿀 수 있다.
p.98
일반적인 리스트는 메모리의 해제까지 책임을 지지 않는다. 리스트에 저장된 값이 주소 값인 경우, 그리고 그 주소 값이 동적 할당의 결과인 경우를 구분하여 메모리의 해제를 진행하도록 구현하는 것은 무리가 있다.
때문에 LRemove 함수처럼 데이터를 소멸하는 함수는, 소멸된 데이터를 반환하도록 정의해야 한다. 그래서 메모리 소멸의 기회를 줄 수 있어야 한다.
p.100
배열 기반 리스트
단점
- 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능
- 삭제의 과정에서 데이터의 이동(복사)이 매우 빈번히 일어난다.
장점
- 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.
댓글