https://www.youtube.com/watch?v=MDeAbo_LP1U&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=8

📌 배열과 리스트

◾ 배열

• 연속된 공간에 값이 채워져있는 형태의 자료 구조
• 인덱스를 통해 값에 바로 접근 가능 ex) A[3]
• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.
  → 값 삽입/삭제 시 해당 인덱스 주변 값을 이동 시키는 과정 필요
  ex)
  {1,2,3}이 들어 있는 배열에서 2를 삭제하는 경우 2를 삭제 후 3을 2자리로 옮겨주어야 함.
  반대로 2의 자리에 4를 삽입 하는 경우에도 2,3을 뒤로 한 칸씩 미뤄준 뒤 4를 넣어주어야 함.
  
• 배열의 크기는 선언할 때 지정
  → 한번 선언하면 수정 불가
• 간단한 구조로 코딩 테스트에서 많이 사용

◾ 리스트

• 값과 포인터를 묶은 노드라는 포인터로 연결한 자료구조
• 인덱스가 없어 값에 접근하려면 Head 포인터부터 순서대로 접근
  → 접근 속도 ↓
• 삽입 및 삭제하는 연산속도가 빠르다.
  ex)
  {40, 50} 에서 가운데 30을 넣고 싶은 경우 40이 가르키고 있는 포인터의 위치를 30으로 변경하고 30이 가르키고 있는 포인터를 50으로 지정
• 선언할 때 크기를 지정하지 않아도 된다.
  → 크기가 정해져 있지 않아 크기 변경이 가능하다
• 포인터를 조정할 공간이 필요해 배열보다 구조가 복잡하다.

◾ 코딩테스트에서 적절한 사용을 하려면

• 배열 : 크기가 정해져있고, 데이터에 접근하는 경우가 않은 경우 사용
• 리스트 : 크기가 변하는 데이터를 다루고 데이터의 삽입/삭제가 많은 경우 사용