선형 자료구조 개요

선형 자료구조

• 선형 구조란 자료를 순차적으로 나열한 상태를 의미한다.

  • 배열
  • 연결 리스트
  • 스택 / 큐

• 반대로 비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태를 의미한다.

  • 트리
  • 그래프
    
    
    

배열

• 원소들이 메모리에 연속되어 배정된다.

• 고정된 메모리를 사용한다.

• 메모리 공간을 추가하거나 축소할 수 없다.

  
  
  

동적배열

• 원소들이 메모리에 연속되어 배정된다.

• 일반 배열과는 다르게 유동적으로 메모리 공간을 추가, 축소
  하여 더 큰 메모리 공간으로 이동이 가능하다.

• 새로운 메모리 공간으로 이동해야 하므로 추가적인 연산이
  요구된다.

• 이 문제점을 해결하기 위해 여유분을 추가로 예약하여
  메모리를 할당받는 방법을 사용하여 메모리 이동을 최소화한다.
  (Capacity가 size의 대략 1.5배~2배 가량의 크기를 갖는다.)
  
  
  두 배열 모두 중간 삽입, 중간 삭제가 비 효율적이다.
  
  
  

연결 리스트

• 원소들이 메모리에 연속되어 배정되지 않는다.

• 배열과는 달리 중간 삽입, 중간 삭제가 효율적이다.

• 임의 접근, Random Access가 불가능하다.