Array
Array는 우리가 흔히 알고있는 배열로, 논리적인 저장순서와 물리적인 저장순서가 일치한다. 인덱스로 원소에 접근이 가능한데, 원소의 인덱스를 알면 O(1)의 시간 복잡도를 갖는다. 하지만 삭제 또는 삽입 과정에서 배열의 연속성을 지키기 위해 인덱스 shift가 발생할 수 있고, 이 과정에서 O(N)의 시간 복잡도를 갖는다.
또한 정적인 자료구조로 크기가 처음 정해진다.
ArrayList
ArrayList는 Array에서 동적인 특성을 갖는 자료구조이다.
ArrayList는 삽입 과정에서 기존의 크기를 초과한다면 기존의 크기 + 기존의 크기/2 만큼 늘어난 배열을 만든 후 기존 원소들을 copy한다.
LinkedList
LinkedList는 자기 자신 다음에 어떤 원소가 있는지 기억한다. 따라서 삽입과 삭제의 시간 복잡도가 O(1)이 된다. 하지만 논리적 저장순서와 물리적 저장순서가 다르기 때문에 원소를 찾을 때는 O(N)의 시간 복잡도를 갖는다.
강준우