주제내용ArrayList vs LinkedListArrayList조회 시 O(1)의 시간 복잡도삽입/삭제 시 시간 복잡도LinkedList조회 시 O(N)의 시간 복잡도빠른 삽입/삭제 속도ArrayList의 구현 자세히 들여다보기
주제
ArrayList와 LinkedList에 대해서 알아봅니다.
내용
ArrayList vs LinkedList
ArrayList
List 인터페이스의 구현체 중 하나로 배열과 상당히 유사합니다. 대신 다른점은 동적으로 크기가 조정된다는 점에서 다릅니다.
조회 시 O(1)의 시간 복잡도
배열의 특성과 같이 인덱스로 접근할 수 있어 조회 성능이 우수합니다.
삽입/삭제 시 시간 복잡도
- 순차적 삽입 시 시간 복잡도는 O(1)
리스트의 맨 끝에 삽입하는 것은 데이터의 이동이 없으므로 바로 삽입이 가능합니다.
- 중간 삽입/삭제시 문제
a부터 z까지의 ArrayList가 있다고 쳤을 때 중간에 “hello”라는 데이터를 추가하게 된다면
데이터가 많은 경우에 새로운 데이터를 중간에 삽입,삭제 시 데이터의 이동이 발생 해 데이터가 많은 경우에는 많은 오버헤드가 발생하는 단점을 갖고 있습니다. 데이터가 많으면 많을수록 더 많은 이동이 발생하게 될 것 입니다.
LinkedList
List의 구현체 중 하나로 이중 연결 리스트로 구성되어있습니다. 그러므로 순방향, 역방향 순회가 모두 가능합니다.
조회 시 O(N)의 시간 복잡도
LinkedList는 첫번째, 마지막 데이터를 조회하는 것은 이중 연결리스트로 구현되어 있기 때문에 성능상 문제가 없습니다.
하지만, 중간의 데이터를 조회하고자하면 인덱스로 접근하는 것이 아니라 하나하나 차례대로 순회해야하는 성질을 갖고 있습니다. 그러므로 n번째 데이터를 찾으려면 첫 데이터부터 n번째 데이터까지 하나하나 순회를 하며 조회해야 한다는 단점을 가지고 있습니다.
빠른 삽입/삭제 속도
ArrayList, 배열의 단점은 비순차적인 삽입과 삭제에 있습니다. 데이터 이동이 발생하기 때문에 느리다는 단점이 있는데요. LinkedList는 연결 리스트로 구성되기 때문에 삽입 삭제시 참조하는 노드만 다시 이어주면 되므로 ArrayList와는 다르게 별도의 데이터 이동이 필요 없이 자유롭습니다.
ArrayList의 구현 자세히 들여다보기
ArrayList는 동적으로 데이터를 삽입/삭제 할 수 있는 배열인데요, 데이터를 추가할 시에 단순히 데이터를 추가해주는 것만이 아니고 내부 코드를 들여다보면 배열의 크기 조정에 있어 나름의 알고리즘이 있습니다.
먼저 아래의 코드를 들여다보면 ArrayList를 생성 시 빈 배열을 할당합니다.
그리고 add 연산을 할 때에는 현재의 배열이 꽉 찼을 경우에 배열의 크기를 늘립니다.
처음에는(oldCapacity == 0) 10의 사이즈로 grow해줍니다.
10이 넘어갈 경우에는 다음과 같은 알고리즘에 의해 배열의 크기가 늘어납니다
기본적으로 새로운 배열의 크기 = 기존의 크기 + (기존의 크기 / 2)가 됩니다
(10에서 꽉차서 grow해야 한다면 다음 크기는 10 + (10 / 2) = 15
