Notice
Recent Posts
Recent Comments
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
Archives
Today
Total
관리 메뉴

SYDev

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

3학년 2학기 전공/자료구조

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

시데브 2024. 9. 17. 13:59
경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

 

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를 구현하는 데에 사용됨