공부기록

선형, 비선형 자료구조 array, list, stack, queue는 모두 선형자료구조이고 graph, tree는 비선형 자료구조이다. Binary Tree? 먼저, 최대 2개의 자식노드를 가질 수 있는 노드들로 이루어진 트리를 이진트리라고 한다. 이진트리의 종류에는 아래와 같은 것이 있다. full binary tree 모든 leaf node가 같은 깊이를 가지고, 모든 non leaf node들은 2개의 자식을 가지는 트리 complete binray tree 가장 깊은 노드를 제외한 노드들은 가능한한 많은 자식을 가져야하고, 가장 깊은 레벨에서 모든 노드들은 왼쪽부터 채워져 있어야한다. Tree의 구현체 배열과 노드로 표현할 수 있다. 배열에서 root를 0 번지부터 시작하면 left child ..

이 게시물을 통하여 배열 (array)와 동적리스트 (linked list)의 차이점과 어느 상황에서 우세한지 비교하고자 한다. 무작위 접근 연산이 일어나면 배열을 쓴다. 링크드리스트는 무작위 접근연산이 일어나서 인덱스가 나오면 거기까지 움직여야 한다. O(N). 배열은 그냥 접근하면 된다. O(1) 커서에서 연산이 일어나면 링크드리스트를 쓴다. 연산이라 함은 insertion, deletion을 말한다. insertion의 경우 링크드리스트는 커서 다음에 새로운 노드를 삽입하고 포인터만 잘 설정해 주면 된다. 이때 O(1)이다. 배열의 경우 커서 다음에 현재 값을 삽입한다고 할 때 커서 다음의 비어있지 않은 공간을 다 뒤로 밀어줘야 된다. 이때 O(N)이다. deletion의 경우 링크드리스트는 포인터..