Programming Exercise: Lab #5

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

Exercise #1

Problems

• Implement the UNSORTED LIST using linked structure and ANSWER the time complexity questions in the code.
  • Destructor(): Deallocate (delete) all nodes in the list.
  • appendItem(item): Append the item to the list (with the best time complexity)
  • removeItem(item): Delete "item" in the list and Deallocate (delete) the deleted item.
  • getItem(pos): Return the item at "pos"-th position. (DO NOT remove ITEM). the first item of the list is 0th position. the second item of the list is 1st position. if "pos" is out of the list, return -1.

template <class ItemType>
UnsortedType<ItemType>::~UnsortedType()
{
    while (listData != nullptr) {
        removeItem(getItem(0));
    }
}

▶ ~UnsortedType()

template <class ItemType>
void UnsortedType<ItemType>::appendItem(ItemType item)
{
    // Time Complexity: O(1)
    
    NodeType<ItemType>* tempPtr = new NodeType<ItemType>;

    tempPtr->value = item;
    tempPtr->next = listData;
    listData = tempPtr;
    length++;
}

▶ appendItem()

template <class ItemType>
void UnsortedType<ItemType>::removeItem(ItemType item)
{   
    // Time Complexity: O(N)
    
    if (listData == nullptr) {
        return;
    }

    NodeType<ItemType>* tempPtr;
    NodeType<ItemType>* deallocPtr;
    tempPtr = listData;

    if (tempPtr->value == item) {
        deallocPtr = tempPtr;
        listData = tempPtr->next;
        delete deallocPtr;
        length--;
        return;
    }

    while (tempPtr->next != nullptr && (tempPtr->next)->value != item) {
        tempPtr = tempPtr->next;
    }

    if (tempPtr->next == nullptr) {
        return;
    }

    deallocPtr = tempPtr->next;
    tempPtr->next = (tempPtr->next)->next;
    delete deallocPtr;
    length--;
    return;
}

▶ removeItem()

template <class ItemType>
ItemType UnsortedType<ItemType>::getItem(int pos)
{
    // Time Complexity: O(N)
    
    if (pos < 0) {
        return - 1;
    }

    int index = 0;
    NodeType<ItemType>* tempPtr;
    tempPtr = listData;

    while (index != pos) {
        tempPtr = tempPtr->next;
        if (tempPtr == nullptr) {
            return -1;
        }
        index += 1;
    }

    return tempPtr->value;
}

▶ getItem()

Exercise #2

Problems

• Implement the SORTED LIST using linked structure and ANSWER the time complexity questions in the code.
  • Destructor(): Deallocate (delete) all nodes in the list.
  • insertItem(item): Insert the item to the proper position in the list.
  • removeItem(item): Delete "item" in the list and Deallocate (delete) the deleted item.
  • getItem(pos): Return the item at "pos"-th position. (DO NOT remove ITEM). the first item of the list is 0th position. the second item of the list is 1st position. if "pos" is out of the list, return -1.

template <class ItemType>
SortedType<ItemType>::~SortedType()
{
    while (listData != nullptr) {
        removeItem(getItem(0));
    }
}

▶ ~SortedType()

template <class ItemType>
void SortedType<ItemType>::insertItem(ItemType item)
{
    // Time Complexity: O(N)

    NodeType<ItemType>* tempPtr = listData;
    NodeType<ItemType>* newPtr = new NodeType<ItemType>;
    newPtr->value = item;

    if (tempPtr == nullptr || tempPtr->value >= item) {
     
        newPtr->next = listData;
        listData = newPtr;
        length++;
        return;
    }
           
    while (tempPtr->next != nullptr && (tempPtr->next)->value < item) {
        tempPtr = tempPtr->next;
    }
    
    newPtr->next = tempPtr->next;
    tempPtr->next = newPtr;
    length++;
    return;
}

▶ insertItem()

template <class ItemType>
void SortedType<ItemType>::removeItem(ItemType item)
{
    // Time Complexity: O(N)
    
    NodeType<ItemType>* tempPtr = listData;
    NodeType<ItemType>* deallocPtr;

    if (listData == nullptr) {
        return;
    }

    if (tempPtr->value == item) {
        deallocPtr = tempPtr;
        listData = tempPtr->next;
        delete deallocPtr;
        length--;
        return;
    }

    while (tempPtr->next != nullptr && (tempPtr->next)->value != item) {
        tempPtr = tempPtr->next;
    }

    if (tempPtr->next == nullptr) {
        return;
    }

    deallocPtr = tempPtr->next;
    tempPtr->next = (tempPtr->next)->next;
    delete deallocPtr;
    length--;
    return;
}

▶ removeItem()

template <class ItemType>
ItemType SortedType<ItemType>::getItem(int pos)
{
    if (pos < 0 || pos >= length) {
        return -1;
    }

    NodeType<ItemType>* tempPtr = listData;
    
    for (int i = 0; i < pos; i++) {
        tempPtr = tempPtr->next;
    }
    return tempPtr->value;
}

▶ getItem