Day09

Day09

1. 자료구조의 종류

• 무엇을 고려해야 하는가?
• 자료구조는 일차원인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든 것이다
• 
• 선형 구조 : 한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다.
• 비선형 구조 : 원소 간 다대다 관계를 가지는 구조롤 계층적 구조나 망형 구조를 표현하기에 적절하다.

2. 시간 복잡도

• 빅오표기법(Big-O notation)
• 상수항은 무시, 가장 큰 항 외엔 무시
• 성능 측정하기 위해서 Date 객체 이용

3. 배열

• 특징

  • 고정된 크기를 가지며 동적으로 크기를 늘릴 수 없다.(단, 스크립트 언어는 가능하다)
  • 원하는 원소의 인덱스를 알면 O(1) 시간 내에 원소를 찾을 수 있다.
  • 원소를 삭제하면 해당 index에 빈자리가 생긴다.

• JavaScript에서 사용

  • 배열 생성
  • 배열 요소 추가, 삭제

4. 연결 리스트

• 특징

  • 각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다.
  • 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.
  • 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
  • 탐색은 O(n)이 소요된다.
  • 요소를 추가 제거할 때는 O(1)이 소요된다.
  • Singly Linked List, Doubly Linked List, Circular Linked List가 존재한다.

• 배열과의 차이점

  • 배열은 순차적인 자료구조이기에 메모리에 연속적인 영역을 사용함. 반면 연결 리스트는 순차적이지 않기 때문에 각 데이터가 퍼져있음.