주제
- ArrayList와 LinkedList의 차이 ‼️
목차
- ArrayList, LinkedList 간략 설명
- 어떻게 다르고 왜 그런가?
내용
What💨 [그들은 무엇인가]
How, why diff❓ [어떻게 왜 다른가]
두 자료구조에 대한 결정적 차이
- 데이터 조회
ArrayList > LinkedList- 왜일까 ❓
- 배열 기반과 리스트 특성의 차이 떄문이다.
배열은 인덱스 기반으로 값을 접근하기 때문에 시간복잡도 1을 갖는다. 하지만 리스트의 경우 맨 처음 값은 1로 접근할 수 있지만 마지막에서 3번째라고 가정했을 때? 결국 약 n번 정도를 순회해야 한다. 그렇기 떄문에 조회 속도는 ArrayList가 월등하다 ‼️
- 데이터의 삽입과 삭제
ArrayList < LinkedList- 왜일까 ❓
- 삽입 일 때 [배열기반] - (삭제일 때도 유사한 그림)
- 링크드 리스트를 보자 보자 어디보자‼️
생각해보면 배열은 삽입과 삭제시 그 뒤에 있는 원소들 또한 옆으로 밀리거나 땡겨오는 액션을 취하는 것을 볼 수 있다. 그렇기 떄문에 결국 최대 n-1번의 액션이 취해지므로 링크드 리스트에 비해 효율이 좋지 못하다‼️
다음 대상 혹은 이전의 참조를 갈아끼면 되므로 그 뒤나 앞에 있는 원소들이 땡겨오거나 밀리는 액션을 취할 필요가 없기 때문에 배열에 비해 상당히 효율적이다.