리스트의 종류
- Unsorted List: 특정 순서 없이 데이터가 배치됨, 그저 predecessor / successor 관계만 존재
- Sorted List: Key를 통해 값이 정렬되어 있음.
Key: 리스트의 논리적 순서를 결정하는 데 쓰이는 애트리뷰트
Unsorted List
-
Insert
1) 넣고자 하는 아이템을 length location에 넣음
2) length++
▶ O(1) -
Retrieve
변수 moreToSearch (bool) / found (bool) / location (int)
moreToSearch = ( location < length )
while(moreToSearch && !found)문을 돌림
▶ O(n) -
Delete
1) 원하는 아이템을 지움
2) 해당 아이템에 가장 마지막 아이템을 넣음
3) length--
▶ O(1)
Sorted List
-
Insert
1) Moving down하면서 적절한 위치를 찾아 넣음
2) length++
▶ O(n) -
Delete
1) 지우고자 하는 element의 위치를 찾음
2) 해당 element 뒤에 위치한 element들을 moving up하여, 지우고자 했던 element를 지움
3) length--
▶ O(n)
Sorted List에서는, Binary Search를 이용하여 Search 알고리즘을 쉽게 할 수 있음.
- Retrieve
=> linear Search 이용
▶ O(n)
=> Binary Search 이용
▶ O(log n)
