- toc {:toc}
List
-
List Definitions
-
List는 ADT이고, 구현된 것은 아니다.
-
Linear relationship : 첫 번째 요소를 제외한 각 요소들은 전임자를 갖고 마지막 요소를 제외한 각 요소들은 후임자를 갖는다.
-
Length : 리스트에서 요소의 수. 언제든 길이는 달라질 수 있다.
-
Class Constructor
-
클래스의 특별한 멤버 함수로 클래스 객체가 정의될 때 암묵적으로 호출된다.
-
사용자가 정의한 생성자가 있다면 해당 생성자가 호출되고, 그렇지 않다면 기본 생성자가 호출된다.
-
Class Constructor Rules
- 생성자는 함수값을 반환하지 않는다.
- 클래스는 여러 개의 생성자를 가질 수 있다. 컴파일러는 입력되는 파라미터의 타입과 수에 의해 적절한 생성자를 선택해 사용한다.
- 생성자 파라미터들은 클래스 객체의 선언에서 파라미터가 전달된다.
- 파라미터가 없다면 기본 생성자를 사용한다.
- 만약 클래스가 적어도 하나의 생성자를 갖고, 클래스 객체 배열이 선언된다면 배열에서 각 요소를 호출하는 생성자들 중 하나는 반드시 기본 생성자이다.
-
Generic Data Type : 데이터 형식에 의존하지 않고 하나의 값이 여러 데이터 타입을 가질 수 있도록 하여 재사용성을 높인다.
-
Unsorted list : 특정한 순서 없이 요소들이 위치해 있는 리스트
-
데이터 요소들 사이의 유일한 관계는 전임자와 후임자 관계 뿐이다.
-
ADT
- Transformers
- MakeEmpty
- InsertItem : 맨 뒤에 가져다 붙인다.
- DeleteItem : 처음부터 비교하면서 지울 요소를 찾고 찾으면 마지막 요소를 지울 요소에 덮어쓴다. length—
- Observers
- IsFull : length가 MAX_ITEMS와 같다면 Full
- LengthIs : length를 반환
- RetrieveItem : 처음부터 순차적으로 비교하면서 찾으면 item에 저장해 반환
- Iterators
- ResetList : 현재 위치, 인덱스를 -1로 지정한다. O(1)
- GetNextItem : 현재 인덱스+1 하여 해당 인덱스 데이터를 item에 저장해 반
- Transformers
-
Sorted list : 리스트의 요소의 키 사이에서 의미적인 관계가 있고, 관계에 따라 정렬된 리스트
-
Key : 리스트의 논리적인 순서를 결정하는데 사용되는 속성
-
ADT
- Transformers
- MakeEmpty
- InsertItem : 삽입할 요소의 적절한 위치를 찾고 해당 위치에 넣기 위한 공간을 만들어 요소를 넣는다. length++
- DeleteItem : 처음부터 비교하며 지울 요소의 위치를 찾고 해당 위치 뒤의 요소들을 앞으로 당겨온다. length—
- Observers
- IsFull : length가 MAX_ITEMS와 같다면 Full
- LengthIs : length를 반환
- RetrieveItem : 처음부터 순차적으로 비교하면서 찾으면 item에 저장해 반환
- Iterators
- ResetList : 현재 위치, 인덱스를 -1로 지정한다. O(1)
- GetNextItem : 현재 인덱스+1 하여 해당 인덱스 데이터를 item에 저장해 반
- Transformers
-
RetrieveItem의 탐색 알고리즘을 향상시키는 방법 → 이진 탐색
-
알고리즘 비교(어떻게 최적의 알고리즘을 선택할 수 있을까?)
-
효율성을 위한 객관적인 측정 방법
- 실행 시간
- 실행 줄의 수
- 기본 연산 수
- Big-O notation → 최악의 경우 발생하는 복잡도를 효율성 측정
: bounded time : logarithmic time : linear time : time : quadratic time : exponential time