자료구조는 데이터를 효율적으로 저장, 관리, 그리고 접근하기 위해 사용되는 구조이다. 다양한 자료구조가 있으며, 그들은 각기 다른 용도와 장점을 가지고 있다.
배열 (Array), 연결 리스트 (Linked List), 스택 (Stack), 큐 (Queue), 트리 (Tree), 그래프 (Graph), 해시 테이블 (Hash Table), 힙 (Heap), 집합 (Set)
자료구조 특성상 검색, 삽입, 삭제를 주로 본다.
배열 끝에 추가 하는 것은 상관없지만(O(1)) 첫번째나 가운데에 삽입/삭제시 데이터를 밀거나 당겨 와야(O(n)) 한다.
endAdd 같은 경우에는 tail노드를 추가해서 frontAdd처럼 바로 추가 해줄 수 있고 더블 링크드리스트를 구현하게 되면 현재 노드에서 이전 값도 가지고 있기 때문에 remove할때 previous를 따로 관리해주지 않아도 된다.
양끝에 삽입/삭제는 빠르지만(O(1)) 특정 위치를 찾아가서(O(n)) 삭제를 할때는 접근을 처음부터 혹은 마지막부터 탐색해야 하기 때문에 느리다.
후입 선출로 괄호 짝을 맞출때 스택을 사용 가능하다.
스택에 하나씩 넣고 반대되는 괄호를 만났을때 하나씩 pop하면서 그 짝을 맞춰가는 방식으로 사용할수 있다. 첫번째로 만나는 반대와 가장 먼저 나오는 스택은 서로 짝이 맞기 때문이다.
스택은 재귀와 동일하게 사용할수 있다.
재귀함수를 통해 깊이 있게 들어가는 것은 스택도 마찬가지이다. DFS에서 둘다 활용 할수 있는데 메모리 사용 관점에서는 재귀에서는 새로운 스택 프레임을 매번 생성되기 때문에 깊이가 깊다면 스택 오버플로우가 발생할수 있지만 코드의 가독성이 좋다는점이고, 스택은 코드의 가독성 보다는 스택프레임을 생성하지 않기 때문에 메모리를 더 효율적으로 사용 할 수 있다.
선입 선출로 카드가 1,2,3,4가 있을때 1를 버리고 2를 가장 마지막에 두면 3,4,2를 만들때 활용할수 있다.
기존에는 rear,front를 -1로 두고 먼저 증가 시킨 다음에 arr.length와 비교해서 크거나 같다면 rear의 값을 재정의 했었는데 그럴 필요 없이 rear는 마지막 값 뒤에 포인터를 위치 시키고 값이 들어간 다음에 위치를 포인터로 가지고 있으면 조건문 없이도 간단하게 사용 가능 하다.
while문도 간단하게 변경이 가능하다.
코드 개선 전
코드 개선 후
전위 중위 후위는 그냥 프린트할 위치만 다르면 상관없는데 node는 클래스로 만들고 그 클래스들을 Map으로 관리해서 관계를 맺는 부분이 어려웠다.
노드가 계층적으로 구조되어있고 탐색시에 재귀로 했기 때문에 그 끝을 보고 다시 돌아와서 끝을 보는 형식으로 DFS와 유사하다.
단순히 트리만 설명할때 그 관계만 설정하면 그게 트리형태이고 이 트리형태를 어떤 조건으로 만들때 한쪽에만 치우친걸 편향 트리라고 한다.
이 편향트리를 해결 하기 위해서 AVL트리 레드블랙트리를 사용할수 있다.
AVL트리는 각노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1로 완전트리 형태를 가진다. 균형이 깨질때 마다 회전을 통해서 트리의 균형을 맞춘다. LL, RR, LR, RL 탐색시에는 항상 균형이 맞기 때문에 최악의 탐색시간 복잡도는 O(logN)이다. 하지만 삽입,삭제시 매번 여러번의 회전이 필요해서 성능이 떨어질수 있다.
레드 블랙 트리는 각 노드에 색깔을 부여하고 특정 조건을 유지한다. 트리의 균형이 완벽하진 않지만 삽입,삭제시 균형을 맞추기 위해서 최소한의 회전만 수행한다.
AVL만큼 균형 잡히진 않아 탐색 속도가 조금 부족 할뿐 최소 회전으로 삽입,삭제가 더 빠르다.
관계를 맺는 부분