이번 포스팅은 "트리와 이진 트리"에 대한 전반적인 이해도를 필요로 합니다. 트리와 이진 트리에 대해 잘 알지 못한다면 공부하고 그 후에 이 포스팅을 읽어주세요 여기에서 트리와 이진 트리에 대해서 공부할 수 있습니다. 이진 트리의 순회(Traversal) 이진 트리 또한 데이터를 저장하기 위한 자료구조입니다. 이진 트리를 순회한다는 것은 이진 트리에 있는 모든 노드를 방문하며 노드의 데이터를 목적에 맞게 처리하는 것을 의미합니다. 스택이나 큐, 연결 리스트 같은 선형 자료구조들은 데이터를 순차적으로 순회하는 방법은 하나뿐입니다. 그러나 계층적 구조를 가진 트리의 경우는 여러 가지 순서로 노드가 가진 데이터에 접근할 수 있습니다. 이진 트리를 순회하는 대표적인 방법으로는 "전위 순회", "중위 순회", "..

트리의 정의 우리가 여태 알아본 연결 리스트, 스택, 큐와 같은 자료구조들은 선형으로 나열된 선형 자료구조입니다. 반면 오늘 알아볼 "트리"는 대표적인 계층적 구조를 가진 자료구조입니다. 즉, 비선형 자료구조입니다. 비선형 자료구조는 자료들의 앞뒤 관계가 1:n 또는 n:n인 자료들을 구현하기에 적절합니다. "트리"는 이렇게 계층적인 구조를 표현하는데 아주 적합한 자료구조입니다. 트리 자료구조를 제대로 이해하기 위해서는 알아야 하는 용어들이 많습니다. 차근차근 살펴보도록 하겠습니다. 노드(Node): 트리의 구성 요소에 해당하는 A, B, C, D, E, F, G, H, I, J입니다. 루트(Root): 계층적인 구조에서 가장 높은 곳에 있는 노드(A)가 루트입니다. 서브트리(Sub-Tree): 기존의 ..

연결 리스트로 구현한 스택 (Linked Stack) 지난 스택에 관한 포스팅(여기)에서는 스택을 구현할 때, "배열"을 이용해서 구현했습니다. 이번 포스팅에서는 연결 리스트로 구현하고자 합니다. 어찌 되었든 스택을 구현하는 것이기에 배열을 이용하나, 연결 리스트를 이용하나 외부적으로 볼 때는 큰 차이가 없습니다. 그러나, 스택의 내부를 살펴보면 차이점이 있습니다. 바로 배열과 달리, 연결 리스트로 구현한 스택은 "크기에 제한을 받지 않는다는 것"입니다. 동적 메모리 할당을 통해 스택에 새로운 요소를 삽입할 수 있습니다. 다만, 삽입과 삭제 시에 동적 메모리 할당을 하고 해제해야 하기 때문에 시간이 조금 더 걸립니다. 연결된 스택(Linked Stack) 구현 C언어로 구현한 연결된 스택은 다음과 같습니..

이번 포스팅은 "단순 연결 리스트"를 이해했다는 전제 하에 내용을 진행합니다. 단순 연결 리스트에 대해 잘 알지 못한다면 이전 포스팅을 참고해주시고 그 후 이 포스팅을 읽어주세요 (단순 연결 리스트 공부하기) 원형 연결 리스트의 정의 원형 연결 리스트는 단순 연결 리스트와 달리 "마지막 노드가 첫 번째 노드를 가리키는 리스트"입니다. 즉, 마지막 노드가 NULL 값을 가지는 것이 아니라 첫 번째 노드 주소값을 가지는 것입니다. 원형 연결 리스트는 하나의 노드에서 모든 노드로의 접근이 가능하다는 장점을 가지고 있습니다. 링크를 따라가다가 보면 모든 노드에 접근한 후, 다시 처음으로 돌아오게 되는 것입니다. 이렇게 되면 노드의 삽입과 삭제 연산이 기존 단순 연결 리스트보다 더욱 단순해지게 됩니다. (삽입과 ..

연결 리스트의 정의 연결 리스트(Linked List)는 "노드(Node)"라고 불리우는 일종의 상자들의 집합이라 할 수 있습니다. 물리적으로 흩어져있는 자료들을 줄로 연결하여 하나로 묶는 자료구조 형태를 "연결 리스트"라고 합니다. 위의 그림과 같이 노드는 메모리의 어떤 위치에나 있을 수 있습니다. 노드는 "데이터 필드"와 "링크 필드"로 분류됩니다. 데이터 필드에는 우리가 저장하고자 하는 데이터가 들어갑니다. 그림과 같이, "Hi", "How" 등 문자열 자료가 들어갈 수도 있고, 정수와 같은 숫자가 들어갈 수도 있습니다. 링크 필드에는 다른 노드를 가리키는 줄이 저장됩니다. 각 노드를 연결하는 줄은 "포인터"로 구현할 수 있습니다. 이를 통해서 다음 노드로 갈 수 있습니다. 연결 리스트에서는 반드시..

큐의 정의 스택과 함께 큐도 프로그래밍에서 굉장히 자주 사용되는 자료구조입니다. 스택이 후입선출(LIFO) 형태를 따르는 자료구조라면, 큐는 반대로 선입선출(FIFO, First In First Out) 형태를 따르는 자료구조입니다. 선입선출의 예시로는 은행 업무를 보기 위해 기다리는 사람들의 대기열을 예시로 들 수 있습니다. 가장 먼저 대기표를 뽑은 사람이 가장 먼저 은행 업무를 보게 될 것입니다. 이처럼 큐는 "뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조"를 가지고 있습니다. 즉, 삽입과 삭제가 서로 다른 곳에서 일어납니다. 큐에서 삽입이 일어나는 곳(가장 뒤 부분)을 후단(Rear)이라고 하고, 큐에서 삭제가 일어나는 곳(가장 앞 부분)을 전단(Front)이라고 합니다. E..

스택의 정의 "스택"은 컴퓨터에서 굉장히 많이 사용하는 자료구조 중 하나입니다. 대표적으로 인터넷에서 뒤로 가기를 누르면 현재 진행되는 웹에서 이전에 수행되던 웹사이트로 돌아갑니다. 이것이 스택의 예시 중 하나입니다. 스택은 '쌓다, 더미'라는 뜻을 가지고 있는데, 이에 뜻에 걸맞게 스택은 데이터를 차곡차곡 쌓아올린 형태인 자료구조입니다. 창고에 쌓여있는 상자를 예시로 들어봅시다. 창고에 새로운 상자를 쌓을 때는 상자의 가장 윗 부분에 놓습니다. 그리고 필요하다면 상자더미에서 가장 위에 있는 상자를 꺼내게 됩니다. 그렇지 않고 상자더미의 가장 아래에 있는 상자를 꺼낸다면 상자더미는 붕괴될 것입니다. 이러한 형태를 후입선출(LIFO: Last-In First-Out)이라고 합니다. 스택 자료구조는 이러한 ..