지난번에 연결 리스트에서 노드의 기본적인 것들을 알아보았다. (C언어) 연결 리스트(1) [자료구조] (C언어) 연결 리스트(1) [자료구조] 자료구조에서 매우 중요한 연결 리스트의 기본적인 구조에 대해 알아보자. 연결 리스트는 노드라고 부르는 아이템의 리스트이다. 그중 단일, 원형 연결 리스트는 하나의 링크 필드를 가지는 리 taco99.tistory.com 이전에 배웠던 것을 활용해서 연결 리스트에서 삽입과 삭제 연산을 구현해보자. ##삽입 연산 삽입 연산은 노드의 연결을 이용해 구현할 수 있다. 삽입연산은 리스트의 첫 부분에 새로운 노드를 추가하는 연산과, 리스트의 중간에 새로운 노드를 추가하는 연산을 구현해보겠다. 결국 같은 원리이지만 선행 노드 변수의 유무로 인해 코드상 약간의 차이가 생긴다. ..

자료구조에서 매우 중요한 연결 리스트의 기본적인 구조에 대해 알아보자. 연결 리스트는 노드라고 부르는 아이템의 리스트이다. 그중 단일, 원형 연결 리스트는 하나의 링크 필드를 가지는 리스트이고 두개의 링크 필드를 가지는 리스트는 이중 연결 리스트임을 이전에 배웠다. 2022.02.19 - [SW/Data structure] - [자료구조] 리스트(List) [자료구조] 리스트(List) 자료구조 리스트에 대해 알아보자. 우리가 흔히 일상생활에서 사용하는 리스트와 같다. (EX. 오늘 할 일, 장 볼 리스트 등등) 리스트는 순서의 개념이 없는 집합과는 다르게 순서, 위치를 가진다. taco99.tistory.com 연결 리스트의 구성요소는 다음과 같다. Head 포인터 : 연결리스트에서 첫 번째 노드의 주..

(C언어) 연결 리스트(1) [자료구조] (C언어) 연결 리스트(1) [자료구조] 자료구조에서 매우 중요한 연결 리스트의 기본적인 구조에 대해 알아보자. 연결 리스트는 노드라고 부르는 아이템의 리스트이다. 그중 단일, 원형 연결 리스트는 하나의 링크 필드를 가지는 리 taco99.tistory.com 연결 리스트로 이전에 배운 스택을 구현해 보자. 스택을 배열로 구현했을 때의 모습이다. 배열로 구현했기 때문에 구현은 간단했지만 크기가 제한됐었다. 우리가 배운 스택을 어떻게 연결 리스트로 구현할 수 있을까?? 위 그림처럼 연결 리스트로 구현한다면 외부적으로 스택과 완전히 일치한다. 연결 리스트의 장점인 동적으로 구현할 수 있다는 점을 이용해 크기에 제한받지 않고 스택을 구현할 수 있다. 하지만 동적 메모리..

자료구조 리스트에 대해 알아보자. 우리가 흔히 일상생활에서 사용하는 리스트와 같다. (EX. 오늘 할 일, 장 볼 리스트 등등) 리스트는 순서의 개념이 없는 집합과는 다르게 순서, 위치를 가진다. 스택, 큐 또한 크게 본다면 리스트라고도 볼 수 있다. 리스트는 구현 방법에 따라 배열로 구현하는 순차 리스트, 연결 리스트로 구현하는 여러 연결 리스트들이 있다. 연결 리스트들에는 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다. 각 리스트들에 대해 대략적으로 알아보자.(각 리스트의 코드적인 부분은 추후 포스팅할 예정) ##순차 리스트 순차 리스트는 배열로 구현한 리스트로서 구현이 쉽고 속도가 빠르다는 장점이 있다. 하지만 배열의 특성상 동적으로 크기를 줄이기 어렵다는 단점이 있다. [삽입] ..

(C언어) 연결 리스트(1) [자료구조] (C언어) 연결 리스트(1) [자료구조] 자료구조에서 매우 중요한 연결 리스트의 기본적인 구조에 대해 알아보자. 연결 리스트는 노드라고 부르는 아이템의 리스트이다. 그중 단일, 원형 연결 리스트는 하나의 링크 필드를 가지는 리 taco99.tistory.com 연결 리스트로 큐를 구현해 보자. 큐를 배열로 구현했을 때의 모습이다. 배열로 구현했기 때문에 크기가 제한됐었다. 연결 리스트로 큐를 구현해 본다면 어떤 모습일까?? 위와 같은 모습이 될 것이다. 쉽게 생각하면 단순 연결 리스트에다 Front, Rear 2개의 포인터를 추가한 것이다. Front는 삭제, Rear에는 추가 혹은 삽입이 관련된다. 이렇게 연결 리스트로 구현한다면 코드가 보다 복잡해지고 링크 필..

이번에는 스레드 이진 트리에 대해 공부해 보자. 보통 이진 트리를 순회할 때 순환 호출을 사용한다. 만약 이진 트리의 노드 개수가 많아지고 트리의 높이가 높아진다면 순환 호출은 상당히 비효율적이다. 그럼 순환 호출을 사용하지 않고 구현할 수 있는 다른 방법이 무엇일까? 먼저 위 이진 트리를 보자. 노드 개수 7개 (N) 총 링크의 개수(노드당 링크 2개) 14개 (2N) 다른 노드를 가리키는 링크의 수 6개 (N-1) NULL을 가리키는 링크의 수 8개 (N+1) 표와 같은 규칙을 가진다. NULL을 가리키는 링크는 N+1개나 존재하지만 사용하지 않는다. 스레드 이진 트리의 가장 큰 아이디어는 NULL을 가리키는 링크를 이용해 순환 호출 없이 트리의 노드들을 순회할 수 있도록 하는 것이다. NULL 링크..