List 인터페이스를 구현한 ArrayList, LinkedList에 대해 정리해보았다.

배열과 ArrayList의 차이

• 배열 : String[] weeks = new String[10]; // 크기 없으면 컴파일 에러
• ArrayList : ArrayList list = new ArrayList(); // 크기 없어도 되고 있어도 됨

배열과 ArrayList의 차이점은 크기가 고정적/가변적이라는 점이다.

ArrayList는 선언시에 크기를 정해줄 수 있지만, 원소를 추가하면서 해당 크기가 넘을 경우 동적으로 크기를 늘려준다. (ArrayList는 선언시에 크기를 안 정해주어도 된다.)

참고 → 실제로는 가지고 있던 용량이 꽉 찼을 때, 용량이 기존의 1.5배를 늘린 새로운 배열에 기존 배열을 copy하는 것이다.

LinkedList vs ArrayList

• ArrayList : 확장 가능한 배열 (순서가 있는 자료 구조)
• LinkedList : 노드가 데이터와 포인터를 가지고 있고 양방향(앞/뒤 노드)으로 가리키는 연결 리스트이다.

ArrayList는 (동적으로 확장가능한) 배열이다. 따라서 조회시 인덱스로 접근한다. 즉, 조회는 O(1)이다. 반면 삭제나 삽입은 복잡해진다. ArrayList는 순서가 있는 배열이다. 만약 어떤 노드를 삭제하면, 뒤의 노드들을 한 칸씩 앞으로 shift해주야 한다. 새로운 노드를 중간에 삽입하면, 뒤의 노드들을 한칸씩 뒤로 shift 해주어야 한다. 따라서 삽입/삭제 시 O(n)이 걸린다.

LinkedList는 중간에 데이터를 삽입/삭제할 때 유리하다.(O(1)) 순서가 있지 않고 각 노드들이 앞/뒤 노드를 가리키기 때문이다. 한 노드를 삭제/삽입하면 해당 노드의 앞/뒤 노드들의 포인터를 수정해주면 된다. 반면 조회는 느리다. 인덱스로 접근하는 배열구조가 아니기에, 앞에서 부터 순차적으로 접근해주어야 하기 때문이다. (O(n))

단! LinkedList는 삽입/삭제 자체는 O(1)가 맞지만, 데이터를 조회 후 삽입/삭제해야된다면 시간복잡도는 달라진다. 그때는 조회 시의 시간복잡도를 그대로 가져간다. (O(n)) 즉, LinkedList는 맨 앞 데이터를 삽입/삭제 할 경우에만 O(1)이다.

결론적으로 조회가 많고 순차적으로 데이터를 삽입/삭제할 경우, ArrayList를 사용하고 중간 순서에 삽입/삭제가 많을 경우, LinkedList를 사용해주는 게 좋다.