CS : Data Structure : ArrayList & LinkedList

ArrayList

 

1.

일반적인 배열과 유사하다.

중복을 허용하고, 순서를 유지하며, 인덱스로 원소를 관리한다.

 

2.

배열은 선언 시 크기가 고정되지만, ArrayList는 선언 후 추가, 삭제가 가능하다.

 

3.

단, ArrayList에 데이터를 추가할 경우, 추가할 때마다 동적으로 크기가 증가하는 것이 아니라, 용량이 꽉 찼을 경우(= default_capacity를 초과할 경우) 더 큰 용량의 배열을 만들어 옮기는 작업을 한다.

 

4.

초기 용량을 예상하여, default_capacity를 조절하는 것이 좋다.

 

 

---

 

LinkedList

 

1.

크기를 변경할 수 없고, 데이터의 추가, 삭제에 시간이 많이 걸린다는 일반적인 배열의 단점을 보완하기 위해 등장한 개념이다.

 

2.

다음 원소의 메모리 주소만 연결시켜 주면 되기 때문에, 추가와 삭제 시 ArrayList보다 빠르고 용이하다.

 

3.

단순 LinkedList의 경우, 단방향성을 가지기 때문에, index를 이용하여 자료를 '검색'하는 상황에서는 적합하지 않다.

또한, 참조의 지역성(한번 참조된 곳의 인근의 데이터를 참조할 가능성이 높다는 것) 때문에 순차접근 시 ArrayList가 더 효율적이다.

 

4.

초기 용량을 예상하여, default_capacity를 조절하는 것이 좋다.

 

 

---

 

ArrayList와 LinkedList 비교