ArrayList vs LinkedList

namkun·2023년 5월 29일
0

T-I-L

목록 보기
7/20

ArrayList

  • List + Array의 자료 구조
  • 크기가 가변적인 배열이라고 생각하는 것이 편하다.
  • 실제 내부도 배열로 구현
  • 데이터 접근 및 변경시 성능이 좋음 (o(1))
  • 데이터를 추가하거나 삭제하는 경우 시간 복잡도는 o(N)
    • 그 이유는 배열의 시간복잡도와 동일 (데이터를 밀거나 땡겨야하기에..)
    • 맨 긑에 추가하는 경우는 O(1) 이다. 하나만 추가하면 되니까!
  • 실제 내부도 배열로 이루어져있기에 빈 엘리먼트의 허용이 가능하다.

LinkedList

  • 양방향의 연결로 구현한 리스트
  • Data 접근시에 속도가 느리다. (o(N))
  • Data 삽입, 삭제시에 연결에서 참조하는 주소 값만 변경하면 된다. 이는 ArrayList와 비교했을 때 효율적이라고 할 수 있다.
  • 그래도 시간 복잡도는 O(N)이 소요된다.
  • 양방향의 연결로 이루어졌기에 빈 엘리먼트를 허용하지 않는다.
profile
개발하는 중국학과 사람

0개의 댓글