반응형
array
-
Array vs LinkedListCS 지식/자료구조 2021. 1. 14. 15:45
Array vs LinkedList Array 논리 저장 순서랑 물리 저장 순서가 일치함 인덱스로 원소에 접근이 가능하기 때문에, O(1)로 엑세스 가능 삭제 or 삽입은 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 맨 뒤에 요소를 추가하는 것은 O(1)이지만, 원래 존재하던 요소의 앞쪽에 삽입한다면 뒤에 있는 요소들의 인덱스를 +1씩 해줘야함 삭제의 경우도 뒤에 있는 요소들을 한칸씩 땡겨줘야함 (인덱스 -1) 위의 두 경우 모두 O(n)의 작업이 추가적으로 필요하다 LinkedList 논리 저장 순서와 물리 저장 순서가 일치하지 않음 논리 저장에는 실제 저장되어있는 요소의 주소 값이 들어있다. 각 원소들은 자신의 다음 원소..