ArrayList VS LinkedList

https://velog.io/@eunbileeme/Java-ArrayList-vs-LinkedList

[Java] ArrayList vs LinkedList

 

ArrayList는 내부적으로 배열을 이용하는 리스트이다.

리스트와 배열의 큰 차이점은 크기가 가변적이라는 것이다..

 

리스트는 원소 접근시 순차적으로 접근하여야 하여 복잡도가 N이다. 하지만 어레이리스트는 내부적으로 배열로 구현되어 배열의 성질을 띈다. 그러므로 접근시 상수복잡도를 가진다.

반면에 링크드리스트는 연결방식으로 리스트를 이루기 때문에 순차접근을 해야한다.

 

순차적으로 데이터를 추가/삭제 하고 조회를 자주 할 경우에는 ArrayList를 사용하고, 처음, 중간 데이터를 추가/삭제하는 경우에는 LinkedList를 사용하는 것이 유리하다.

stack의 경우 ArrayList로 구현할 수 있다 하지만 queue의 경우 LinkedList로 구현하는 것이 유리하다.

중간에 삭제하는 경우 복잡도에서 차이가 나기 때문이다.

 

 

위 사진에서 LinkedList에서 add at given index 부분을 수정하여아한다.

링크드의 경우에는 맨 앞에 추가 하거나 수정할 경우에만 O(1)이고 뒤에 것은 순차 접근 하여야 해서 O(N)이다.

또한 삭제시에도 맨 앞에 것만 O(1)이고 뒤에 것은 O(N)이다.

 

참고로 ArrayList의 경우 맨뒤의 추가 및 삭제는 o(1)이다. 하지만 앞의 것들은 삭제시 뒤에 것들을 앞으로 떙겨야 하기에 O(N)이다.