📚 Array
가장 기본적인 자료구조인 배열(Array) 자료구조는 논리적 저장 순서와 물리적 저장 순서가 일치한다.
따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있으며, 찾고자 하는 원소의 인덱스를 알고 있다면 O(1)에 해당 원소로 접근할 수 있다.
즉, Random Access가 가능하다는 장점이 있다.
하지만, 배열은 선언할 때 크기와 데이터 타입을 지정해야 하므로 계속 데이터가 늘어나는 경우 최대 사이즈를 미리 알지 못한다면 사용하기 부적합하다.
삽입, 삭제
배열은 데이터를 삽입하거나 삭제할 때도 매우 비효율적이다.
만약 해당 원소에 접근하여 삽입 또는 삭제 작업을 완료했다면O(1), 또 한가지 작업을 추가적으로 해줘야 하기 때문에 시간이 더 걸린다.
새로운 값을 삽입해야 한다면, 원래 값들을 뒤로 밀어내며 해당 인덱스에 덮어 씌워야 한다O(n). 기본적으로 크기를 정해놓은 배열에서는 값들을 뒤로 밀어내는 것은 어렵다.
어떤 값을 삭제했다면, 빈 공간이 생겨 배열의 연속적인 특성이 깨지게 된다. 따라서 값들을 쉬프트(shift) 해줘야 하는 비용이 발생한다O(n).
따라서 배열에서의 삭제에 대한 시간 복잡도는 최악의 경우 O(n)이다.
📚 ArrayList
배열의 단점을 해결하기 위해 나온 것이 리스트(List)이다.
장점
-
배열처럼 크기가 정해져 있지 않기 때문에, 중간에 데이터를 삽입하거나 삭제하더라도 크기가 정해져있던 배열에서의 문제점을 해결할 수 있다.
-
인덱스를 갖고 있어 검색도 빠르다.
단점
- 리스트의 크기가 int의 최대치로 제한되어 있으며, int 범위를 넘어갈 경우에는 OutOfMemoryError가 발생한다.
- 데이터의 삽입/삭제를 위해서는 내부 배열을 생성하고 복제한다. 또한, 리스트의 크기를 쉬프트 연산을 통해 조정하기 때문에 시간이 오래걸린다.
📚 LinkedList
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
노드의 포인터는 다음이나 이전 노드와의 연결을 담당한다. 뒤에 노드만 가리키는 단일, 앞뒤 노드를 가리키는 다중 LinkedList가 있다.
장점
- 데이터의 중간에 삽입 및 삭제를 하더라도 전체를 살펴보지 않고 이전값과 다음값이 가르켰던 주소값만 수정하면 된다
O(1).
단점
- Array와 달리 인덱스가 없기 때문에 원하는 위치에 삽입/삭제를 위해서는 첫번 째 원소부터 확인해야 한다
O(n).
❓ 비교
데이터 검색
- Array, ArrayList : 인덱스를 사용하므로 O(1)
- LinkedList : 처음부터 순차적으로 접근하므로 O(N)
데이터 삽입
- Array : 쉬프트 연산 때문에 O(N)
- ArrayList : 쉬프트 연산, 배열 복사 때문에 O(N)
- LinkedList : 위치를 찾는 과정 O(N), 삽입 O(1)
데이터 삭제
- Array : 쉬프트 연산 때문에 O(N)
- ArrayList : 쉬프트 연산, 배열 복사 때문에 O(N)
- LinkedList : 위치를 찾는 과정 O(N), 삭제 O(1)
💡 결론
- 데이터에 접근하는 것이 중요하다면 Array, ArrayList
- 삽입/삭제가 자주 일어난다면 LinkedList
ArrayList는 배열의 형태로 데이터를 저장하는 자료구조이다. 인덱스를 이용하여 데이터 검색이 빠르지만 삽입, 삭제가 느리다.
LinkedList는 데이터가 노드 형태로 연결되어있는 구조이다. 노드의 연결만 수정해주면 되기 때문에 데이터 삽입, 삭제가 빠르지만, 검색은 느리다.
[참고]
