Sorted list and Unsorted list

Linear relationship: Each element except the first has a unique predecessor, and each element except sthe last has a unique successor

Unsorted list A list in which data items are placed in no particular order; the only relationship between data elements is the list predecessor and successor relationships.

Sorted list A list that is sorted by the value in the key; there is a semantic relationship among the keys of the items in the list.

Key The attributes that are used to determine the logical order of the list.

Unsorted list는 순서 없이 element들이 list안에 들어있다.

Sorted list는 key에 의해서 element들이 정렬되어있다.

ADT Unsorted list Operations

class constructor

class constructor는 object가 정의될 때 암묵적으로 호출되는 special member function이다.

값을 return할 수 없으며 여러개가 존재할 수 있고 컴파일러가 parameter에 따라서 맞는 constructor를 선택해서 실행한다. parameter가 없는 constructor는 default constructor이다.

item을 넣을때 length위치에 들어가며 length는 1증가한다.

RetrieveItem은 location이 length보다 작을 동안 루프를 돌며 item을 찾고 찾으면 found = true;

GetNextItem은 다음 item을 가져오는 method로 현재 위치에서 1을 더한 위치의 값을 item에 할당함.

element를 넣거나 삭제할때마다 length를 늘리고 줄인다.

deleteItem을 수행할때 중간에 있는 item을 삭제하면 뒤에 있는 요소들을 앞으로 한칸씩 당겨야하는데 연산이 많아지므로 unsorted의 특성을 활용해서 삭제할 위치에 마지막 요소의 값을 넣고 마지막 요소를 삭제하면 된다.

void UnsortedType::RetrieveItem(ItemType &item, bool &found)
// Pre: Key member of item is initialized.
// Post: If found, item’s key matches an element’s key in the list
// and a copy of that element has been stored in item;
// otherwise, item is unchanged.
{
    bool moreToSearch;
    int location = 0;
    found = false;
    moreToSearch = (location < length);
    while (moreToSearch && !found) {
        switch (item.ComparedTo(info[location])) {
        case LESS:
        case GREATER:
            location++;
            moreToSearch = (location < length);
            break;
        case EQUAL:
            found = true;
            item = info[location];
            break;
        }
    }
}

void UnsortedType::GetNextItem(ItemType &item)
// Pre: List has been initialized. Current position is defined.
// Element at current position is not last in list.
// Post: Current position is updated to next position.
// item is a copy of element at current position.
{
    currentPos++;
    item = info[currentPos];
}

void UnsortedType::DeleteItem(ItemType item)
// Pre: item’s key has been inititalized.
// An element in the list has a key that matches item’s.
// Post: No element in the list has a key that matches item’s.
{
    int location = 0;
    while (item.ComparedTo(info[location]) != EQUAL)
        location++;
    // move last element into position where item was located
    info[location] = info[length - 1];
    length--;
}