[자료구조] 배열, 링크드 리스트

배열과 링크드 리스트의 차이점을 아는 게 너무 중요하다고 한다!
면접에서도 자주 나오는 질문이라 해서, 정리해보려고 한닷

---

배열

• 데이터 접근
  • 데이터에 바로 접근할 수 있다.
  • 링크드 리스트보다 시간이 더 적게 걸린다.
  • O(1)의 시간으로 접근이 가능하다
• 데이터를 중간에 삽입/삭제
  • 중간에 삽입/삭제가 일어나면, 모든 원소의 자리를 옮겨주어야 한다.
  • 링크드리스트보다 시간이 더 걸린다.
  • O(N)의 시간이 걸린다.
• 이미 정해진 배열의 크기를 변동
  • 공간이 다 찼다면, 새로운 공간을 새로이 할당해야 한다

링크드 리스트

• 데이터 접근
  • 바로 접근할 수 없고, 링크를 따라 탐색하며 접근한다.
  • 배열보다 시간이 더 오래 걸린다.
  • O(N)의 시간으로 접근이 가능하다
• 데이터를 중간에 삽입/삭제
  • 중간에 삽입/삭제가 일어나면, 앞 뒤 링크만 변경하면 된다.
  • 배열보다 시간이 덜 걸린다.
  • O(1)의 시간이 걸린다.
• 이미 정해진 배열의 크기를 변동
  • 공간이 다 찼다면, 동적으로 뒤의 노드를 추가하면 된다

---

정리