자료구조

• 자료구조
  • 선형구조
    • 선형 리스트
      • 배열(Array), 행렬, 레코드
    • 연결 리스트
      • 단순 연결 리스트(Linked List), 이중 연결리스트, 원형 연결 리스트
    • 스택
    • 큐
    • 데크(Deque)
      • 출력 제한 데크, 입력 제한 데크
  • 비선형구조
    • 트리
      • 일반 트리, 이진 트리
    • 그래프
      • 방향 그래프, 무방향 그래프
  • 파일구조
    • 직접 파일
    • 순차 파일
    • 색인 순차 파일

---

List와 Array의 차이점?

Array는 메모리 상에 데이터가 연속적으로 저장되고, List는 메모리 상에 데이터가 비연속적으로 저장된다.
(Array와 List의 차이를 묻는 것은 보통 Array 와 LinkedList의 차이를 묻는 것으로 통용된다.)

어떠한 자료를 표현할 때 자료구조는 프로그램의 성능을 높이기 위해 적절히 사용되어야 한다.

List(리스트) - 조회

리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고, 빈틈없는 데이터의 적재라는 장점을 취한 인터페이스이다.
데이터가 메모리 상에 연속적으로 저장되진 않기 때문에 순차 리스트가 아닌 연결 리스트라고 부른다.

List의 특징

• 배열은 크기가 정해져 있고 메모리 상에 데이터가 연속적으로 있어야 하기 때문에 메모리 낭비가 발생할 수 있다.
  ↔ 리스트는 빈 공간을 허용하지 않기 때문에 이러한 메모리의 낭비는 없다.
• 데이터들이 순차적으로 구성된 집합이지만, 일반적으로 데이터가 메모리 상에 연속적으로 존재하지 않는다. (실제 메모리 주소는 랜덤이다.)
  ⇒ Cache Hit Ratio가 낮다.
• 크기가 가변적이다.
• 원소에 접글할 때 O(N)의 시간 복잡도를 가진다.
• 삽입과 삭제의 경우 O(N)의 시간 복잡도를 가진다.
• 삽입, 삭제, 크기 등 해당 리스트를 사영하기 위한 다양한 속성과 메서드가 존재한다.

Array(배열) - 삽입/삭제

배열은 같은 성질을 갖는 원소들이 순서대로 구성된 집합이다.
순차적으로 저장된 데이터를 참조하는데에는 Index가 사용된다.

Array의 특징

• 고정된 크기를 갖는다.
  → 메모리 낭비 가능성 有: 배열의 크기를 10으로 지정할 경우, 내부에 데이터가 5개만 있어도 실제 배열의 크기는 10이다.
• 논리적 저장 순서 == 물리적 저장 순서
  ⇒ Cache Hit Ratio가 높다.
• 삽입과 삭제의 경우 O(N)의 시간 복잡도를 가진다.
• 원소에 접근할 때는 O(1)의 시간 복잡도를 갖는다.

Cache Hit Ratio?

Cache Hit Ratio란, CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우를 의미한다.

이 비율이 높을 수록 좋은 성능을 가지고 있으며 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성인 공간 지역성 덕분에 Array는 해당 비율이 높다.

---

Array VS. ArrayList VS. LinkedList

Array	ArrayList	LinkedList
선형	선형	선형
순차	순차	연결
크기 고정	크기 가변	크기 가변
빈 엘리먼트 허용 O	O	X