DS-L03

• toc {:toc}

List

• List Definitions

• List는 ADT이고, 구현된 것은 아니다.

• Linear relationship : 첫 번째 요소를 제외한 각 요소들은 전임자를 갖고 마지막 요소를 제외한 각 요소들은 후임자를 갖는다.

• Length : 리스트에서 요소의 수. 언제든 길이는 달라질 수 있다.

• Class Constructor

• 클래스의 특별한 멤버 함수로 클래스 객체가 정의될 때 암묵적으로 호출된다.

• 사용자가 정의한 생성자가 있다면 해당 생성자가 호출되고, 그렇지 않다면 기본 생성자가 호출된다.

• Class Constructor Rules

  1. 생성자는 함수값을 반환하지 않는다.
  2. 클래스는 여러 개의 생성자를 가질 수 있다. 컴파일러는 입력되는 파라미터의 타입과 수에 의해 적절한 생성자를 선택해 사용한다.
  3. 생성자 파라미터들은 클래스 객체의 선언에서 파라미터가 전달된다.
  4. 파라미터가 없다면 기본 생성자를 사용한다.
  5. 만약 클래스가 적어도 하나의 생성자를 갖고, 클래스 객체 배열이 선언된다면 배열에서 각 요소를 호출하는 생성자들 중 하나는 반드시 기본 생성자이다.

• 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에 저장해 반

• 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에 저장해 반

• RetrieveItem의 탐색 알고리즘을 향상시키는 방법 → 이진 탐색

• 알고리즘 비교(어떻게 최적의 알고리즘을 선택할 수 있을까?)

• 효율성을 위한 객관적인 측정 방법

  • 실행 시간
  • 실행 줄의 수
  • 기본 연산 수
  • Big-O notation → 최악의 경우 발생하는 복잡도를 효율성 측정
    • : bounded time
    • : logarithmic time
    • : linear time
    • : time
    • : quadratic time
    • : exponential time