• Constructor

  • 리턴값 없음
  • 여러 개 있을 수 있음
  • 파라미터 없는 게 기본

• Unsorted List Definition

typedef int ItemType;
class UnsortedType
{
private:
	Itemtype data[MAX_SIZE];
	int length;
	
public:
	UnsortedType(); // 생성자, 리턴 타입 없음
	
	// Transformer
	void appendItem(ItemType value);
	void insertItem(int pos, ItemType value);
	void updateItem(int pos, ItemType new_value);
	
	void clear();
	
	// Observer
	int size();
	bool isFull();
	bool isEmpty();
	
	bool findItem(Itemtype &item);
	ItemType getItem(int pos);
}

1. insertItem()

   #include "UnsortedType.h"
   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 ++;
   }
   

   insertItem의 worst case : pos가 작을 때 / 리스트가 길 때

• Time Complexity (Big - O)
  1. 계수 무시
  2. 작은 것들 무시. 큰 것만 고려

• List vs Array
  • 같은 것은 아님.
  • 둘 다 linear structure
  • list : ADT
  • array : CDT