기본 추상자료형.md

리스트

• 가장 단순, 가장 기초적
• 연속적인 임의의 개체 모델링
• 공간복잡도 O(n)
• get set size empty : O(1)
• add remove : O(n)

연결리스트

• 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조
• 각 노드 = 데이터+ 다음 노드에 대한 참조
• 공간복잡도 O(n)
• size, empty, addFirst, removeFirst O(1)
• get set add remove O(n)

Array VS ArrayList VS LinkedList

Array

• index로 빠르게 값 찾을수 있음
• 선언 시 크기와 데이터 타입 지정해야함

LinkedList

• 데이터의 삽입 및 삭제가 빠름
• 검색 비효율적

ArrayList

• 데이터 찾는데 빠르지만, 삽입 및 삭제 느림
• index를 가지고 있지만 크기가 정해져있지 않음

스택

• LIFO 후입선출
• 배열 또는 연결리스트로 구현
• 공간복잡도 O(n)
• 시간복잡도 O(1)

큐

• FIFO 선입선출
• 배열 또는 연결리스트로 구현
• 순차큐/원형큐 존재
• 공간복잡도 O(n)
• 시간복잡도 O(1)

트리

• 선형 구조가 아닌 계층 구조
• 최악의 경우 깊이/높이구하는거 O(n)

깊이 : 루트특정 노드, 높이 : 루트깊이가 가장 긴 노드

이진트리

• 순서트리를 모델링함
• 기초작업 O(1)

분리집합

• Disjoint Set
• 분리집합간의 중복원소 없으므로 교집합이나 차집합 의미없음
• Union Find
• 리스트로 구현 시 : Find 빠르지만 Union 느림 , Find O(1) Union O(log n)
• 트리로 구현 시 : Union 빠르지만 Find 느림 , Find O(n) Union O(1)

힙

• 완전이진트리이면서 key(부모)<=key(자식)을 만족하는 이진트리
• 삽입 삭제 : O(log N)

사전

• unordered dictionary / ordered dictionary 두 종류 존재
• 가장 중요한 목적 : 탐색
• 무순사전 : 삽입O(1), 탐색O(n)
• 순서사전 : 삽입/삭제 : O(n), 이진탐색시 O(log n)

이진탐색트리

• 중위순회 시 키가 증가하는 순서로 방문
• 공간 O(n)
• 시간 : 편향이진트리인경우 최악 O(n), 좌우대칭인경우 O(log n)

AVL 트리

• 높이균형 속성 : 자식들의 좌우 높이차이가 1을 넘지 않는 이진탐색트리
• AVL 트리 높이 : O(log n)
• 탐색 삽입 삭제 O(log n) (삽입 후 불균형 수정 O(1) + 트리를 올라가는데 O(log n))

스플레이 트리

• 노드를 탐색 후 스플레이함(루트로 옮김)
• 자기조정 이진탐색트리(self-adjusting)
• 탐색 삽입 삭제 O(log n) 상각실행시간
• splay 최악실행시간 O(h)

해시

• 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는것
• 해시 함수 구형
• 데이터가 많아지면 collision 생김

해시테이블

• 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 --> 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 관리 가능
• 최악의 경우 탐색,삽입,삭제 O(n) : 모든 키가 충돌할 경우
• 기대실행시간 O(1)
• 충돌해결방법 : 분리 연쇄법, 개방주소법(선형조사법, 2차 조사법, 이중해싱)