자료구조 기초 정리

자료구조란

1. 선형 자료구조 (앞과 뒤가 있고, 순서가 있다)

배열(array)

-> 논리적인 순서와 물리적인 순서가 같음, 배열이 중간에 빌 수가 없음

배열의 장점: index 연산을 할 수 있어 검색이 빠름 O(1)

배열의 단점: insert , delete를 할 때 O(n)의 시간이 걸림

 

연결리스트(LinkedList)

-> 노드를 사용, 값이 추가할 때 마다 메모리를 할당 받고, 값은 서로 링크로 연결, 데이터의 물리적 위치와 논리적 위치가 다를 수 있음

장점 : 배열에 비해 insert, delete 가 빠름

단점 : index 연산이 불가능, 검색이 느림

 

스택 

-> 후입선출(LIFO, Last-In-First-Out) 구조로 마지막 데이터가 먼저 나오게 된다. 

 

큐 

-> 선입선출(FIFO, First in first out) 구조로, 들어온 순서대로 데이터가 나간다. 

 

 

2. 비선형 자료구조

힙  👀

-> 최대값 혹은 최소값을 빠르게 찾기 위한 구조

-> 최대힙, 최소힙이 있으면 최소힙 기준으로는 부모가 자식보다 항상 작아야 한다.🎈

-> 삭제와 삽입의 시간복잡도는 O(logN) 

 

이진 탐색 트리  

-> 자식노드가 2개 이하인 트리로 검색을 위한 자료 구조

-> 자료의 중복을 허용하지 않음

-> 왼쪽자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다. 😁

-> 삽입 , 검색의 시간복잡도는 O(logN) 

 

(jdk 클래스에서 TreeSet, TreeMap 등 Tree로 시작되는 클래스는 정렬을 지원함)

 

자가 균형 트리

-> 편향된 데이터 (ex. 부모보다 작은 데이터만 있어서 왼쪽으로만 뻗어나간 데이터) 인 경우 시간복잡도가 N이 되는데,

이러한 편향을 개선한 이진 탐색 트리이다. 😀

-> AVL 트리, Red Black 트리가 있다.

 

해시 👀

-> 검색을 위한 자료 구조

-> key, value 한쌍으로 되어 있고 key는 중복을 허용하지 안음

-> List에 N개의 데이터가 있다고 할 때, 검색 시간 복잡도는 O(N) 이다. (리스트를 돌면서 찾아야 하기 때문에)

해시는 시간 복잡도가 O(1) 이다. 😲

(1) key가 Hash Function 통해 hash 값으로 변경되어 value랑 매칭되어 저장된다.

(2) hash 값을 인덱스처럼 쓰기에 검색 시간 복잡도가 O(1) 이다

 

 

👏

👏