[자료구조 및 알고리즘] CH3. Array and Linked list

 

Array란?

• 선형자료구조 + 모든 item 같은 자료형 + item들이 메모리 상의 countinuous하게 저장

Array의 문제점

• 특정 위치 insert, delete가 불편(모든 item 위치 재배치해야함)
• 만약 얼마나 많은 item을 저장해야 하는지 모르는 상황이면 최대한 많은 메모리를 할당해야 함(waste)

Linked list란?

• data part + link part(다음 item의 주소 가리킴)로 구성
• 모든 item이 다음 item과 연결되어있는 item sequence
• array와 달리 메모리 상에 꼭 continuous하게 저장되지 않음(consecutive일수도 있고 아닐수도 있다)

Linked list의 장단점

• 장점
  • 삽입, 삭제가 array에 비해 쉽다
  • 메모리 낭비 최소화(필요한 item만큼 노드 생성)
• 단점
  • data access가 느리다
  • pointer를 위한 memory overhead