Array
- 정적인 자료구조, 크기가 정해진다.
- 흔히 알고 있는 배열로, 논리적인 저장순서와 물리적인 저장순서가 일치한다.
- 데이터 접근은 O(1), 데이터의 추가/삭제는 최악의 경우 O(N)
- 배열 맨 앞쪽의 데이터를 추가/삭제 한다면 나머지 데이터들을 한칸씩 옮겨줘야 하기 때문
ArrayList
- Array와 다르게, ArrayList는 사이즈가 동적인 Array이다.
- 삽입의 경우, ArrayList가 기존의 크기를 초과한다면
기존크기+기존크기 1/2만큼 크기가 늘어난 배열을 새로 만들어, 기존 데이터들을 copy한다.
- 배열과 마찬가지로 데이터 접근은 O(1), 데이터의 추가/삭제는 최악의 경우 O(N)
LinkedList
- 논리적 저장순서와, 물리적 저장순서가 다르다.
- 한 노드에 연결될 노드의 포인터 위치를 가리키는 방
- 특정 요소 다음에 삽입을 추가/삭제하는데는 O(1)이지만, 어떤 원소를 삭제 또는 추가 하고자 했을 때 그 원소를 찾기 위해 O(n)이 추가적으로 발생한다.
- LinkedList는 Tree 구조의 근간이 되는 자료구조이다.
Share article
