자료구조 정리

스택 : 먼저 넣는 자료가 가장 마지막에 나오는 LIFO구조의 자료구조입니다.
큐 : 먼저 넣는 자료가 먼저 나오는 FIFO구조의 자료구조입니다.
트리 : 정점과 간선을 이용해, 사이클을 이루지 않도록 하는 Graph의 특수한 형태로, 계층이 있는 데이터를 표현하기 적합한 자료구조입니다.
힙 : 최대값, 최소값을 찾아내는 연산을 쉽게 하기위해 고안된 구조로, 각 노드의 키 값이 자식의 키값보다 작을 경우 최소힙, 작지않다면 최대힙입니다. 완전 이진트리의 형태를 나타냅니다.

우선순위 큐

우선순위 큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해서는 일반적으로 힙을 사용하며, 힙은 완전이진트리를 통해 구현되었으므로 삭제, 삽입의 시간복잡도는 O(logN)입니다. 다만, 탐색의 경우 root노드만을 확인하기 때문에 O(1)입니다.

해시테이블은 Key, Value의 형태로 데이터를 저장하는 자료구조중 하나입니다. 빠른 데이터 검색이 필요할때, 유용합니다. 해시테이블은 Key값에 해시함수를 적용해 고유 index를 생성하고, 그 index에 저장된 값을 꺼내오는 구조입니다.
해시테이블은 고유 index로 값을 조회하기 때문에 O(1)의 시간복잡도를 갖습니다.(평균적으로)

하지만 해시의 index값이 충돌한 경우, 충돌된 index값에 대해 연결된 데이터를 조회하여야 하기때문에O(N)까지 증가할 수 있습니다.

Array는 데이터의 논리적 순서와 물리적 저장순서가 일치하나, LinkedList는 다음 혹은 이전노드의 주소값을 기억하는 형태로 구현됩니다. 따라서 각각은 용도에 따라 장단을 가집니다.
Array는 랜덤액세스가 가능합니다. 즉, 원하는 데이터에 무작위로 접근할 수 있어 인덱스값을 알경우 조회는 O(1)의 시간복잡도를 갖습니다. 다만, 데이터의 추가 삭제의 경우 배열을 새로 할당하고, 복제하여야 합니다. 이때문에 O(N)만큼의 시간복잡도가 필요합니다.
반면 LinkedList는 탐색의 경우 루트노드부터 탐색하여야 하므로 O(N)만큼의 시간복잡도가 요구됩니다. 반면, 삽입과 삭제의 경우 리스트를 새로 할당하는 오버헤드없이, 상호간의 Link만 끊어주면 되기에 삭제연산은 O(1)의 시간복잡도를 갖습니다. 다만, 특정 원소를 삭제하기 위해서는 해당 원소를 탐색해야하기 때문에 삭제의 경우도 O(N)까지 갈 수 있습니다. 하지만, 배열을 새로 할당하는 등의 불필요한 오버헤드가 없기 때문에 삽입과 삭제연산에서 Array보다 효율적입니다.
메모리 할당의 경우 배열은 컴파일 타임에 메모리가 할당됩니다. (정적메모리 할당), 반면 Linked List는 새로운 요소가 추가될 때 런타임에 메모리가 할당되므로 동적메모리 할당방식으로 저장됩니다.

이진트리는 자식노드의 개수가 2개 이하인 트리를 뜻합니다. 반면 이진탐색트리는 이진트리의 개념과 더불어 자식노드가 부모노드보다 크면 반드시 오른쪽에, 부모보다 작으면 반드시 왼쪽 자식으로 위치해야하는 규칙을 갖고있습니다. 이진탐색트리는 이런 성질을 통해 이진탐색을 보장합니다. 또한, 이진탐색트리의 삽입, 삭제 모두 O(logN)이며, 트리가 편향될경우 O(N)까지 늘어납니다.