[자료구조] 선형 자료구조와 비선형 자료구조

작성중 ..

선형 vs 비선형

1. 선형구조 : 자료를 순차적으로 나열한 형태 (스택, 큐, 배열, 연결리스트)
2. 비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 (트리, 그래프)

배열 vs 동적배열 vs 연결리스트 (호텔에 비유)

• 배열
  • 사용할 방 개수를 고정해서 계약 (절대 변경 불가)
  • 연속된 방을 배정받아 사용
  • 장점 : 연속된 방
  • 단점 : 방 추가/축소 불가
• 동적배열 (C++ 에서의 vector)
  • 사용할 방 개수를 유동적으로 계약
  • 연속된 방으로 배정받아 사용
  • 방 할당 정책 : 실제로 사용할 방 보다 많이, 여유분을 두고(대략 1.5배에서 2배) 예약 후 이사. -> 이사 횟수 최소화를 위함.
  • 장점 : 유동적인 계약 (이사 횟수 최소화)
  • 단점 : 중간 삽입/삭제 (배열도 마찬가지임)
• 연결리스트
  • 연속되지 않은 방을 사용
  • 장점 : 중간 삽입/삭제 이점 
  • 단점 : n 번째 방을 바로 찾을 수 없음 (random access 불가), 따라서 중간 삽입/삭제의 이점을 최대한 활용하기 어려움. (iterator 사용 필요)