ArrayList, LinkedList의 특징과 차이

Moondy·2022년 5월 12일
2

ArrayList

  • 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 Array와 비슷
  • 하지만 ArrayList는 배열과 다르게 배열을 추가하고 삭제하는 메서드가 존재
  • 데이터 추가시 더 큰 용량의 임시 배열을 만들어 복사

LinkedList

  • 연결된 노드들의 집합인데, 각 노드는 데이터와 포인터(다음 노드를 가리키는) 로 이루어져 있다.
  • 데이터 추가시 새로운 데이터 노드를 만들고 이전 노트의 포인터를 새 노드를 가리키게 만든다
  • 즉, 각 노드는 앞 뒤의 노드의 위치를 저장한다.

어떨때 사용하면 좋을까

ArrayList

  • 인덱스 기반의 자료구조이기 때문에 get(int index)를 통해 무작위 접근 가능 → O(1)의 시간복잡도를 가짐

  • 삽입, 삭제시 배열을 임시배열에 복사하는 방식이기 때문에 O(N) 복잡도

  • 포인터를 저장하지 않아도 되는 배열 (연속된 메모리안에 저장)

LinkedList

  • 처음노드부터 찾으려는 노드까지 순차적으로 탐색해야하므로 최대 O(N)의 시간복잡도를 가짐

  • 삽입, 삭제시 이전노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문에 O(1)의 복잡도

  • 포인터의 사용으로 저장공간을 많이 차지한다

결론

  • 검색: ArrayList가 빠름

  • 삽입,삭제: LinkedList빠름

  • 공간복잡도는 LinkedList가 높다

데이터 검색을 자주한다면 ArrayList, 데이터 삽입 및 삭제를 많이 한다면 Linked List

ArrayList는 연속된 메모리안에 저장되고, 포인터를 저장할 필요가 없기 때문에 공간효율성 관점에서는 더 유리

profile
DevOps를 살짝 찍먹하는 BackEnd 개발자

1개의 댓글

comment-user-thumbnail
2022년 10월 16일

감사합니다

답글 달기