1. Unsorted List

• 데이터 요소들이 특정한 순서 없이 배치돼있음. → Python에서의 list

1-1.Operations

Constructor(생성자)

• [ClassName]()

Transformer(Change data)

• appnedItem(value)
• insertItem(pos, value)
• removeItem(value)
• updateItem(pos, new_value)
• clear()

Observer(Observer data)

• size()
• isFull()
• isEmpty()
• findItem(value)
• getItem(pos)

1-2. Transformer’s Time complexity

• appendItem() → $O(N)$
• insertItem() → $O(N)$
  • improved version!! ( 원하는 위치에 있는 데이터 맨 뒤로 보내기 + 그 자리에 넣기) → $O(1)$
    
• removeItem() → $O(N)$
  • improved version!!( data find + 마지막에 있는 데이터를 그 자리에 넣기 + length- -) → $O(N)$ 동일!
    

2. Sorted List

• key의 value값을 기준으로 정렬된 List

2-1. Operations

Constructor(생성자)

• [ClassName]()

Transformer(Change data)

• appnedItem(value) -> 순서가 있어서 항상 맨 뒤에 추가할 수는 없음
• insertItem(pos, value) -> 순서에 맞게 값을 insert하기 때문에 원하는 위치에 insert 불가
• removeItem(value)
• updateItem(pos, new_value) -> 값을 update하면 순서가 깨지기 때문에 불가능
• clear()

Observer(Observer data)

• size()
• isFull()
• isEmpty()
• findItem(value)
• getItem(pos)

2-2. Transformer’s Time Complexity

• insertItem() → $O(N)$
  • improved version 사용 불가!!!! (정렬되어 있기 때문)
• removeItem() → $O(N)$
• findItem() → Linear search 사용시 $O(N)$
  • improved!! → binary search

3. Binary Search

• First, Last, Mid 를 이용하여 범위를 좁혀가며 Search.
• findItem(64)??
  

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];
	}

→ Time complexity : $O(logN)$

4. List vs Array

• List랑 Array는 같지 않음.

• 공통점: 둘 다 Linear Structure!!

• List : Abstract Data Type (ADT)

  • List는 array를 쓰지 않고도 구현이 가능함(ex. Linked List)

• Array : Concrete Data Type(int array_int[10])

  • Array는 다른 ADT들을 구현할 때 쓰임(ex. Stack, Queue)