[TIL] 배열과 리스트

배열과 리스트의 차이점이 있다는 사실은 알았지만, 구체적으로 알지 못했다. 이를 쉽게 설명한 유투브가 있어 참조하게 되었다.

• 아래 그림에서 array[0]과 list[0]의 값은 둘 다 동일하게 주소값을 찾아감

• 하지만, array[3]과 list[3]의 값을 찾아가는 과정은 어떨까?

  • array는 주소값이 순차적으로 지정되기 때문에 바로 주소를 찾아가면 됨

  • list는 주소값이 순차적으로 지정되어 있지 않기 때문에 맨 처음의 주소로 가서 저장되어있는 다음 주소값을 토대로 3번째 인덱스를 찾아나감

• 즉, list는 주소값을 하나하나 찾아가야 한다는 단점이 발생

• 그렇다면 굳이 왜 list를 쓰는 것일까? 당연히 장점도 있다!

• 1번째 인덱스 값인 8을 지웠다고 가정해볼 때,

  • array는 메모리 공간이 그대로 남아 있어 낭비가 발생함

  • 그러나, list는 다음 인덱스의 주소를 알려주는 포인터 값만 변경됨

• 즉, array에 비해 list가 더 효율적으로 메모리를 사용

각각의 장단점 정리

Array(순차리스트)

• 장점

  1. 원하는 인덱스에 빠른 접근이 가능
  2. 참조를 위한 추가적인 메모리 할당이 필요 없음

• 단점

  1. 중간에 자료를 삽입하기 위해서는 뒤에 빈 공간이 있어야 함
  2. 데이터를 삭제해도 공간이 남아있어 용량을 차지

  List(연결 리스트)

• 장점

  1. 포인터를 사용하기 때문에 삽입, 삭제 등의 연산이 간단하고 빠름
  2. 삽입, 삭제 등의 시행 시 노드만 만지면 되기 때문에 메모리 효율이 좋음

• 단점

  1. 포인터를 통해 인덱스에 접근하기 때문에 탐색 속도가 느림

[출처] https://www.youtube.com/watch?v=q41J1npj86M&t=18s