[자료구조] Chapter 2. Unsorted/Sorted Lists

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

 

List Definitions

• List relationship
  
  • 모든 요소(첫 번째, 마지막 요소 제외)는 predecessor(전임자), successor(후임자)를 가진다.
  • first element -> predecessor X
  • last element -> successor X
• Length
  
  • list 내부 items의 개수
• Unsorted vs Sorted

 

Unsorted List

1. Unsorted List

• items의 특별한 순서가 없는 list
• ex) <list> in python

Basic ADT Operations
- Constructor: ADT의 new instance(object) 생성
- Tranformer: instance의 하나 혹은 더 많은 data instance의 상태를 change
-  Observer: 내부를 바꾸지 않고, data values의 상태를 관찰 

 

2. Unsorted List Operations - Logical Level

• constructor
  
  • [ClassName]()
  • class object가 생성될 때, 암시적으로 호출되는 memeber function
  • function value를 반환하지 못하고, value type 반환 불가능
  • different parameter sets를 가진 multiple contructors가 존재 가능
  • 파라미터가 없는 contructor -> default constructor
• transformer(change data) 
  • appendItem(value)
  • insertItem(pos, value)
  • removeItem(value)
  • updateItem(pos, new_value)
  • clear()
• observer(observe data)
  • size()
  • isFull()
  • isEmpty()
  • findItem(item)
  • getItem(pos)

// UnsortedType.h
typedef int ItemType;
class UnsortedType {
private:
    ItemType data[MAX_SIZE]; // Implemented using an array
    int length;
public:
    UnsortedType( );
    void appendItem(ItemType value);
    void insertItem(int pos, ItemType value);
    void removeItem(ItemType value);
    void updateItem(int pos, ItemType new_value);
    void clear( );
    int size( );
    bool isFull( );
    bool isEmpty( );
    bool findItem(ItemType item);
    ItemType getItem(int pos);
}

 

3. Unsorted List Operations - Implementation Level

- Constructor & size() & isFull() & isEmpty()

#include "UnshortedType.h"

UnsortedType::UnsortedType() {    //no return type
    length = 0;
}

int UnsortedType::size() {
    return length;
}

bool UnsortedType::isFull() {
    return (length == MAX_SIZE);
}

bool UnsortedType::isEmpty() {
    return (length == 0);
}

 

 

- appendItem() vs isertItem()

• appendItem -> 배열의 끝에 item 추가하는 구조
  
  • O(1)
• insertItem -> 원하는 index에 item 추가하는 구조 
  • 자리를 비우기 위해, 원래 아이템들 한 칸씩 뒤로 -> N개의 item -> O(N)
  • 해당 위치의 아이템을 맨 뒤로, 이후 삽입 -> O(1)

void UnsortedType::appendItem(ItemType value) {
    if(isFull()) {
        return;
    }
    
    data[length] = value;
    length++;
}

void UnsortedType::insertItem(int pos, ItemType value) {
    if(isFull()) {
        return;
    }
    
    for(int i = length; i > pos; i--) {
        data[i] = data[i - 1];
    }
    data[pos] = value;
    length++;
}

void UnsortedType::improved_insertItem(int pos, ItemType value) {
    data[length] = data[pos]
    data[pos] = value;
    length++;
}

 

- Time Complexity

• efficient algorithm/program -> smaller resources and takes a shorter time
  • more computations -> more time
  • computations 횟수를 추정 -> 효율적 알고리즘/프로그램 찾아낼 수 있음
• Big-O Theorems
  
  • theorem 1: ignore all coefficients - 계수 무시 -> O(2N) -> O(N)
  • theorem 2: ignore significantly smaller terms - O(N + 1) -> O(N)
• 순서
  • O(1)
  • O(logN) = O(log2N)
  • O(N)
  • O(NlogN) = O(N*log2N)
  • O(N^2)
  • O(2^N)
• example
  • O(3N^2 + 12logN) -> O(N^2)
  • O(5NlogN + 4N^2 + 7N + 6) -> O(N^2)
  • O(5N + 3M^2) -> O(N + M^2)
  • array A를 Array B로 복사(A의 길이 N) -> O(N)
  • 길이가 N인 array C의 item 찾기 -> O(N)
  • 길이가 N인 array D 정렬 -> O(N^2) (selection sort)
  • Fibonacci series의 N번째 item 찾기( Fibo(N) = Fibo(N-1) + Fibo(N-2)) -> O(2^N)

- improved_removeItem(), update, clear, get, find

void UnsortedType::improved_removeItem(ItemType value) {
    if(isEmpty()) {
        return;
    }
    
    for(int i = 0; i < length; i++) {
        if(data[i] == value) {
            data[i] == data[length - 1];
            length--;
            break;
        }
    }
}

void UnsortedType::updateItem(int pos, ItemType new_value) {
    if(pos >= length) {
        return;
    }
    
    data[pos] = new_value;
}

void UnsortedType::clear() {
    length = 0;
}

ItemType UnsortedType::getItem(int pos) {
    if(pos >= length) {
        throw std::out_of_range("Error");
    }
    
    return data[pos]
}

bool UnsortedType::findItem(ItemType item) {
    int location = 0;
    
    while(location < length) {
        if(data[location] == item) {
            return true;
        }
        location++;
    }
    return false;
}

• removeItem()
  • item 탐색 - N computation -> O(N)
• updateItem()
  • O(1)
• clear() 
  • O(1)
• getItem()
  • O(1)
• findItem()
  • O(N)

 

Sorted List

1. Sorted List Operations - Logical Level

• key에 의해 values가 정렬된 list -> items의 keys 사이에는 semantic relationship이 존재
• key: list의 logical order를 결정하는 attributes -> name, birth, gpa, ...

 

typedef int ItemType;

class SortedType {
private:
    ItemType data[MAX_SIZE];
    int length;
public:
    SortedType();
    void insertItem(ItemType value);
    void removeItem(ItemType value);
    void updateItem(ItemType old_value, ItemType new_value);
    void clear();
    
    bool size();
    bool isFull();
    bool isEmpty();
    bool findItem(ItemType item);
    Itemtype getItem(int pos);
};

 

 

2. Sorted List Operations - Implementation Level

void SortedType::insertItem(ItemType value) {
    if(isFull()) return;
    int location = 0;
    while(loation < length) {
        if(value > data[location]) {
            location++;
        }
        else {
            break;
        }
    }
    for(int i = length; i < location; i--) {
        data[i] = data[i - 1];
    }
    data[location] = value;
    length++;
}

void SortedType::removeItem(ItemType value) {
    if(isEmpty()) return;
    int location = 0;
    while(location < length) {
        if(value > data[location]) {
            location++;
        }
        else {
            break;
        }
    }
    for(int i = location + 1; i < length; i++) {
        data[i - 1] = data[i];
    }
    length--;
}

bool SortedType::findItem(ItemType item) {
    int location = 0;
    while(location < length) {
        if(data[location] == item) {
            item = data[location];
            return true;
        }
        else if(data[location] > item) {
            return false;
        }
        location++;
   	}
   	return false;
}

bool SortedType::findItemBinary(ItemType item) {
    int mid;
    int first = 0;
    int last = length - 1;
    while(first <= last) {
        mid = (first + last) / 2;
        if(item < data[mid]) {
            last = mid - 1;
        }
        else if(item > data[mid]) {
            first = mid + 1;
        }
        else {
            item = data[mid];
            return true;
        }
    return false;
}

 

3. Big-O COmparison of List Operations

 

 

4. List vs. Array 

• List와 Array는 같은가? - No
• Linear Structure라느 점에서는 매우 유사
• List: Abstract Data Type(ADT) -> 리스트는 array 없이 구현 가능 (ex. linked list)
• Array:Concrete Data Type -> 다른 ADTs를 구현하는 데에 사용됨