03. ADTs Unsorted List and Sorted List

리스트 (List)

• 각 요소가 유일한 전임자(predecessor)와 후임자(successor)를 갖는 데이터 요소의 집합
  • 단 첫 번째 요소는 전임자가 없고, 마지막 요소는 후임자가 없다.
  • 데이터 요소들은 선형의 관계(linear relationship)를 갖는다. (전임, 후임)

• 종류
  • 비정렬 리스트 (Unsorted List)
    ? 데이터 요소 (item) 사이에 특정 순서가 없는 리스트
  • 정렬 리스트 (Sorted List)
    ? 데이터 요소가 어떤 수/ 알파벳/ 키에 의해 정렬된 리스트

    ✏️ Key
    ? 리스트의 논리적인 순서를 결정하는 attribute (값이 아닌 속성)으로, 리스트의 모든 요소를 유일하게 정의할 수 있어야 한다

---

비정렬 리스트(Unsorted List)의 연산

• 생성자 (Constructor)
  : 리스트의 길이 0으로 초기화

  void UnsortedType::UnsortedType()
  // pre: none, post: list is empty.
  {
     length = 0;
  }

• 변환자 (Transformer)
  • MakeEmpty
  • InsertItem
    : 리스트의 마지막 인덱스에 item 삽입

    void UnsortedType::InsertItem(ItemType item)
    // pre: list has been initialized & list is not full.
    {
       info[length] = item;
       length++;
    }

  • DeleteItem
    : 리스트에서 특정 아이템 삭제
    (삭제하려는 아이템이 여러 개 있어도 최초의 하나만 삭제한다.)

    void UnsortedType::DeleteItem(ItemType item)
    // pre: key member of item has been initialized.
    // pre: an element in the list has a key that matches item's. (삭제하려는 아이템이 list에 존재해야 한다.)
    {
       int location = 0;
       
       while (item.ComparedTo(info[location]) != EQUAL)
       {
       	  location++;
       }
       
       info[location] = info[length-1];
       length--;
    }

    ✏️ 비정렬 리스트이므로 요소의 순서 상관 x
    → 마지막 아이템을 해당 위치에 덮어 씌우고, 길이 -1 (실제로 메모리에 저장된 데이터 값을 지우는 것이 아니라, 인덱스를 조정함으로써 나중에 덮어쓸 수 있게 하여 마치 삭제된 것처럼 표현)

• 관찰자 (Observer)
  • IsFull
    : 리스트가 가득 찼는지 아닌지 (boolean) 반환

    bool UnsortedType::IsFull()
    // pre: list has been initialized.
    {
    	return (length == MAX_ITEMS)
    }

  • LengthIs
    : 리스트에 있는 요소의 수 (int) 반환

    int UnsortedType::LengthIs()
    // pre: list has been initialized.
    {
    	return length;
    }

  • RetrieveItem

    bool UnsortedType::RetrieveItem(ItemType& item, bool& found)
    {
    	// pre: key member of item has been initialized.
       	int location = 0;
       	found = false;
       
       	while ((location < length)  && !found) {
       		switch (item.ComparedTo(info[location]) {
       			case LESS:
       			case GREATER:
       				location++;
       				break;
       			case EQUAL:
       				found = true;
       				item = info[location];
       				break;
             }
         }
     }

    ✏️ break문을 GREATER의 경우에만 적음
    → 찾으려는 아이템 값이 info[location]보다 LESS하거나 GREATER인 경우 모두에 대해 location을 하나 증가시킨다는 의미

• 반복자 (Iterator)
  • ResetList

    int UnsortedType::ResetList()
    // pre: list has been initialized.
    // post: currnet position is prior to first element in list.
    {
    	currentPos = -1;
    }

  • GetNextItem

    int UnsortedType::GetNextItem(ItemType& item)
    // pre: list has been initialized & current position is defined.
    //				(즉, 생성자와 ResetList()가 먼저 호출되어야 한다.)
    // pre: element at current position is not last in list.
    // post: currnet position is prior to first element in list.
    {
    	currentPos++;
    	item = info[currentPos];
    }

---

정렬 리스트(Sorted List)의 연산

• 리스트의 요소를 삽입 및 삭제할 때 정렬이 유지되어야 하기 때문에 DeleteItem과 InsertItem이 수정되어야 한다. 또한 정렬 리스트에서 요소를 검색할 경우 선형 검색이 아닌 다른 방식의 검색을 이용하므로 RetrieveItem 도 수정되어야 한다.
  그 외 함수는 비정렬리스트와 동일하다.

• 생성자 (Constructor)
  : 리스트의 길이 0으로 초기화

   void UnsortedType::SortedType()
   // pre: none, post: list is empty.
   {
   	length = 0;
   }

• 변환자 (Transformer)

  • MakeEmpty
  • InsertItem
    : 정렬 리스트 내에서 새로운 요소가 삽입될 적절한 index인 location을 찾는 것 (새로운 공간 생성)

    location

    • item보다 큰 요소가 처음으로 등장하는 위치
    • item이 삽입될 공간

    void SortedType::InsertItem(ItemType item)
    // pre: list has been initialized & list is not full.
    // pre: item is not in list & list is sorted by key member using function `ComparedTo`  (비정렬 리스트와의 차이점)
    // post: item is in the list. list is still sorted.
    {
       bool moreToSearch = (location < length)
       int location;
         	
       while (location < length) {
        	switch (item.ComparedTo(info[location]) {
         		case LESS:
         			moreToSearch = false;
         			break;
         		case GREATER:
         			location++;
         			moreToSearch = (location < length);
         			break;
         	}
       }
         	
       //make room for new element in sorted list
       for (int i = length; i > location; i--)
        	info[i] = info[i-1];
         	
       info[location] = item;
       length++;
    }

    ✏️ while문 안에 switch문을 사용할 때, break를 써도 while의 루프를 빠져나올 순 없다. break대신 return을 쓰면 루프를 빠져나올 순 있지만, 전체 함수가 종료된다.
    따라서 moreToSearch와 같은 bool을 사용하여 반복 조건을 설정하는 것이 좋다.

  • DeleteItem
    : 정렬 리스트로부터 삭제될 요소의 location을 찾는것 (차지된 공간 제거)

    location

    • 삭제할 item이 존재하는 인덱스

    void SortedType::DeleteItem(ItemType item)
    // pre: key member of item has been initialized.
    // pre: Exactly one element in the list has a key that matches item's. (삭제하려는 아이템이 list에 딱 하나만 존재해야 한다.)
    {
    	int location = 0;
    	
    	while (item.ComparedTo(info[location]) != EQUAL) 
    		location++;
    
    	//move up elements that follow deleted item in sorted list.
    	for (int i = location+1; i < length; i++) 
    		info[i-1] = info[i];
    	
    	length--;
    }

    
    

• 관찰자 (Observer)

  • IsFull
    : 리스트가 가득 찼는지 아닌지 (boolean) 반환

    bool SortedType::IsFull()
    // pre: list has been initialized.
    {
        return (length == MAX_ITEMS)
    }

  • LengthIs
    : 리스트에 있는 요소의 수 (int) 반환

    int SortedType::LengthIs()
    // pre: list has been initialized.
    {
        return length;
    }

  • RetrieveItem
    : 이진 검색 (binar search)를 이용해 정렬 리스트 내의 요소 검색

    bool SortedType::RetrieveItem(ItemType& item, bool& found)
    // pre: key member of item has been initialized.
    {
        int midPoint;
        int first = 0;
        int last = length-1;
        bool moreToSearch = (first <= last);
        	
        found = false;
        	
        while (moreToSearch && !found) {
        	midPoint = (first + last) / 2;
        	switch (item.ComparedTo(info[midPoint])) {
        		case LESS:
        			last = midPoint - 1;
        			moreToSearch = (first <= last);
        			break;
        		case GREATHER:
        			first = midPoint + 1;
        			moreToSearch = (first <= last);
        			break;
        		case EQUAL:
        			found = true;
        			item = info[midPoint];
        			break;
    }

• 반복자 (Iterator)
  • ResetList

    int SortedType::ResetList()
    // pre: list has been initialized.
    // post: currnet position is prior to first element in list.
    {
    	currentPos = -1;
    }

  • GetNextItem

    int SortedType::GetNextItem(ItemType& item)
    // pre: list has been initialized & current position is defined.
    // pre: element at current position is not last in list.
    // post: currnet position is prior to first element in list.
    {
    	currentPos++;
    	item = info[currentPos];
    }

---

리스트 연산의 Big-O 비교