연결 리스트로 큐를 구현해 보자. 큐를 배열로 구현했을 때의 모습이다. 배열로 구현했기 때문에 크기가 제한됐었다. 연결 리스트로 큐를 구현해 본다면 어떤 모습일까?? 위와 같은 모습이 될 것이다. 쉽게 생각하면 단순 연결 리스트에다 Front, Rear 2개의 포인터를 추가한 것이다. Front는 삭제, Rear에는 추가 혹은 삽입이 관련된다. 이렇게 연결 리스트로 구현한다면 코드가 보다 복잡해지고 링크 필드로 인해 메모리 공간 차지가 클 수 있다. C언어로 직접 구현해 보자. ##함수 1. 리스트 구조체의 선언 -> 큐의 특성에 맞게 Front, Rear 포인터를 추가하여 노드를 선언 2. init ->큐의 초기화 함수 3. is_empty -> 큐가 비어있는.......
이번에는 스레드 이진 트리에 대해 공부해보자. 보통 이진트리를 순회할때 순환 호출을 사용한다. 만약 이진 트리의 노드 개수가 많아지고 트리의 높이가 높아진다면 순환호출은 상당히 비효율적이다. 그럼 순환호출을 사용하지 않고 구현할 수 있는 다른 방법이 무엇일까? 먼저 위 이진트리를 보자. 표와 같은 규칙을 가진다. NULL을 가리키는 링크는 N+1개나 존재하지만 사용하지 않는다. 스레드 이진트리의 가장 큰 아이디어는 NULL을 가리키는 링크를 이용해 순환호출 없이 트리의 노드들을 순회할 수 있도록 하는 것이다. NULL 링크에 중위 순회시에 후속 노드인 중위 후속자를 저장시켜 놓아 순회시 NULL을 가리키는 링크로 가더라도 순회.......
요즘 '인문학 습관'이라는 책을 읽다가 이런 구절을 보았다. 내 머릿속에 들어온 한 가지 생각을 질문으로 바꿔서 그 궁금증이 풀릴 때까지 세상 모든 지식과 연결하는 것, 그리고 잠시 사유의 시간을 보낸 뒤 행동으로 나만의 답을 만들어 마침표를 찍어내는 과정, 이것이 진짜 고수들의 생각법입니다. 근래 공부하면서 다짐했던 부분이 있었다. '내가 배운 지식을 죽은 지식으로 두지 말자' 죽은 지식이란 말은 그 순간에만 배움을 익히고 전혀 활용하지 못하고 어디 쓰이지는 지도 모른 채 생각도 안 나는 머릿속 저 뒤편으로 사라지는 것을 말한다. 과거 나의 배움에 대한 태도였다. 공부하면서도 스스로 밑빠진 독에 물.......
[C언어로 원형 연결 리스트로 원형 큐 구현해 보기] 배열로 큐를 구현했던 이전과는 다르게 원형 연결 리스트를 통해 동적으로 원형큐를 구현해 보자 배열로 구현한 원형큐의 모습이다. 위 구조적인 모습을 원형 연결 리스트로 구현해 보겠다. 이전 원형 연결 리스트 포스팅과 같이 마지막 노드와 첫 번째 노드의 접근성을 용이하기 위해 마지막 노드를 헤드 노드로 선언한다. 그렇기 때문에 원형 연결 리스트의 헤드 노드가 원형큐에서의 Rear 노드가 된다. 위 구조는 원형큐의 형태를 갖추면서 동적이다. 구현하기 위한 함수들을 생각해 보자. ##함수 1. 리스트 구조체 선언 -> 리스트의 형태를 갖추기 위한 구조체 선언 2. print_queue() -.......
자료구조의 리스트에 대해 알아보자. 우리가 흔히 일상생활에서 사용하는 리스트와 같다. (EX. 오늘 할 일, 장 볼 리스트 등등) 리스트는 순서의 개념이 없는 집합과는 다르게 순서, 위치를 가진다. 스택, 큐 또한 크게 본다면 리스트라고도 볼 수 있다. 리스트는 구현 방법에 따라 배열로 구현하는 순차 리스트, 연결 리스트로 구현하는 여러 연결 리스트들이 있다. 연결 리스트들에는 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다. 각 리스트들에 대해 대략적으로 알아보자.(각 리스트의 코드적인 부분은 추후 포스팅할 예정) ## 순차 리스트 순차 리스트는 배열로 구현한 리스트로서 구현이 쉽고 속도가 빠르다는 장점이 있.......
연결 리스트로 이전에 배운 스택을 구현해 보자. 스택을 배열로 구현했을 때의 모습이다. 배열로 구현했기 때문에 구현은 간단했지만 크기가 제한됐었다. 우리가 배운 스택을 어떻게 연결 리스트로 구현할 수 있을까?? 위 그림처럼 연결 리스트로 구현한다면 외부적으로 스택과 완전히 일치한다. 연결 리스트의 장점인 동적으로 구현할 수 있다는 점을 이용해 크기에 제한받지 않고 스택을 구현할 수 있다. 하지만 동적 메모리 할당과 해제 부분에서 삽입이나 삭제 시간은 배열로 구현한 스택보다 느릴 수 있다. C언어로 직접 구현해 보자. ## 함수 1. 리스트의 구조체 선언 -> 스택에 특성에 맞게 top 포인터를 추가하여 노드를 선언 2. init.......