Array

  • 여러 개의 데이터를 하나로 묶어서 표현하는 자료형

Memory

  • 메모리상의 연속적인 공간에 저장됨
  • 연속되기 때문에 array의 길이를 length로 표현

Random Access

  • 임의 데이터에 접근 시 array의 맨 앞의 주소로부터 데이터의 위치를 계산해서 알 수 있으므로, index를 이용해 데이터에 바로 접근할 수 있음(a[0], a[1])

Update

  • 데이터의 수 만큼 연속된 메모리 공간이 확보되어야 하므로 임의 데이터를 중간에 추가하거나 삭제할 때 시간이 소요됨.
  • n번째 위치에 데이터 추가
    1. Array의 끝에 공간을 하나 추가
    2. n번째 위치부터 데이터들을 모두 한칸씩 뒤로 이동
    3. n번째 위치에 데이터 저장
  • n번째 위치에 데이터 삭제
    1. Array에서 n번째 데이터 삭제
    2. n번째 이후 데이터들을 모두 한칸씩 앞으로 이동
    3. Array 맨 끝에 남는 공간을 제거

Linked List

  • Array와 같이 여러 개의 데이터를 하나로 묶어 표현하는 자료형

image.png

Memory

  • 데이터들이 순서에 상관없이 메모리상에 흩어져서 저장됨
  • 흩어져 있는 각각의 메모리 영역을 세는 것이므로 list의 길이를 count로 표현

Random Access

  • 흩어져 있는 데이터들을 연결하기 위해 포인터를 사용. 각 데이터들은 다음 데이터의 메모리 주소를 함께 갖고 있음
  • 원하는 데이터에 접근하려면 처음부터 포인터를 따라가면서 찾아야함

Update

  • 데이터의 순서가 포인터에 의해 정해지므로, 중간에 새로운 데이터를 추가하거나 삭제하기 쉬움
  • n번째 위치에 데이터 추가
    1. n-1번째 데이터의 포인터가 가리키는 주소를 새로운 데이터의 포인터에 복사
    2. n-1번째 데이터의 포인터가 가리키는 주소를 새로운 데이터의 메모리 주소로 변경
  • n번째 위치에 데이터 삭제
    1. n번째 데이터의 포인터가 가리키는 주소를 n-1번째 데이터의 포인터에 복사
    2. n번째 데이터 삭제

Double Linked List

  • List에서 이전과 다음 데이터의 메모리 주소를 모두 가짐
  • Next, Previous 포인터를 함께 저장

image.png

Summary

  • 저장할 데이터 개수가 계속 바뀌고 임시로 저장하는 목적인 경우 List를 사용
  • 저장된 데이터가 바뀌지 않으면서 데이터에 접근해서 사용하기만 한다면 Array를 사용