1. Unsorted List

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

1-1. Remind : Basic ADT Operations

• Constructor(생성자)
• Transformer
• Observer

• insertItem(pos, value)
• removeItem(value)
• updateItem(pos, new_value)
• clear() | | Observer (observe data) | - size()
• isFull()
• isEmpty()
• findItem(value)
• getItem(pos) |

1-2. Transformer’s Time complexity

• appendItem() → $O(N)$

• insertItem() → $O(N)$

  • improved!!! ( 원하는 위치에 있는 데이터 맨 뒤로 보내기 + 그 자리에 넣기)

    → $O(1)$

• removeItem() → $O(N)$

  • improved!!( data find + 마지막에 있는 데이터를 그 자리에 넣기 + length- -)

    → $O(N)$ 동일!

2. Sorted List

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

2-1. Operations

• insertItem(pos, value)
• removeItem(value) - updateItem(pos, new_value)
• clear() | | Observer (observe data) | - size()
• isFull()
• isEmpty()
• findItem(value)
• getItem(pos) |

2-2. Transformer’s Time Complexity

• insertItem() → $O(N)$
  • improved 사용 불가!!!! (정렬되어 있기 때문)
• removeItem() → $O(N)$