ArrayList vs LinkedList

ArrayList

장점:

1. 요소 접근이 빠르다. 인덱스를 사용하여 O(1)의 시간 복잡도로 요소에 접근할 수 있다.
2. 메모리 공간이 적게 필요하다. 요소가 추가되면 동적으로 메모리를 할당하지만 기본적으로는 요소 개수에 따라 고정 크기의 배열을 사용한다.

단점:

1. 요소 삽입/삭제가 느리다. 배열의 중간에 요소를 삽입하거나 삭제하는 경우 나머지 요소를 이동해야 하므로 O(n)의 시간 복잡도가 필요하다.
2. 요소 삽입/삭제 시 메모리 재할당이 필요하다. 동적으로 메모리를 할당하므로 요소를 추가하거나 삭제할 때마다 배열을 재할당해야 한다.

LinkedList

장점:

1. 요소 삽입/삭제가 빠르다. 요소를 삽입하거나 삭제할 때 O(1)의 시간 복잡도가 필요하다.

단점:

1. 요소 접근이 느리다. 인덱스가 없으므로 요소에 접근하려면 처음부터 차례대로 탐색해야 하므로 O(n)의 시간 복잡도가 필요하다.
2. 메모리 공간이 많이 필요하다. 각 요소마다 다음 요소를 가리키는 포인터가 필요하므로 고정 크기의 배열 대비 메모리 공간을 더 사용한다.

결론

따라서 요소 접근이 많이 필요한 경우 ArrayList를, 요소 삽입/삭제가 많이 필요한 경우 LinkedList를 사용하는 것이 적절하다.
하지만 무방향 그래프에서는 인접 리스트에 포함된 간선의 개수가 상대적으로 적으므로 더 자주 사용되는 연산에 따라 선택하는 것이 좋다.