Java - ArrayList와 LinkedList

- Array(배열)

1. 초기 길이를 지정해야 한다.

2. 생성된 배열의 길이를 동적으로 변경하지 못한다.

 

 

 

- ArrayList

1. 내부적으로 배열의 형태를 지니고 있다.

2. 추가적으로 데이터를 삽입 또는 삭제하기 위해서 새로운 임시 배열을 생성하여 데이터를 복사하는 방법을 쓴다.

* 만약 새로운 값을 추가하려고 할 때, List의 크기가 생성되어 있는 배열의 size(생성시 따로 설정하지 않았다면 size = 10인 배열이 생성된다)보다 커지게 되면, 이전 크기의 2배가 되는 배열을 생성해 배열 전체를 복사하여 새로운 배열에 복사하고 제일 뒤에 값을 추가해야 한다.

3. 데이터 검색은 o(1)의 시간복잡도를 지니지만, 추가와 삭제에는 o(n)의 시간복잡도를 지닌다.

-> 대량의 자료를 추가/삭제하는 경우 그만큼 데이터의 복사가 많이 일어나 성능 저하를 일으킬 수 있다.

-> 각 데이터는 인덱스를 지니고 있기 때문에 데이터 검색에는 유리한 구현체이다.

 

 

 

- LiknedList

1. 데이터를 저장하는 각 노드가 이전 노드와 다음 노드 상태만 알고 있는 상태이다.

2. 데이터 검색 시 리스트의 시작이나 끝에서부터 해당 index까지 순차적으로 접근하여 값을 얻으므로 o(n)이라는 시간 복잡도를 지닌다.

3. 데이터 추가 시 일반적으로 원하는 인덱스에 접근해야 되므로 o(n) 시간 복잡도와 추가 시 발생하는 o(1)의 시간복잡도를 합친 o(n)의 시간 복잡도를 지닌다.

* 그러나 시작이나 끝 요소에 추가나 삭제를 할 시에는 원하는 인덱스를 찾을 필요가 없으므로 o(1)이라는 시간복잡도만 지닌다.

-> ArrayList와 다르게 데이터 추가, 삭제시 데이터의 복사가 필요 없다. 

-> 데이터 추가 삭제에 용이하나, 데이터 검색에는 불리하다.