minkg3532 님의 블로그

연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 주소(포인터)를 가지며, 이들이 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 선형 자료구조이다. 배열과 달리 메모리상에서 연속적으로 위치하지 않고 동적으로 할당된다. 연결 리스트 vs 배열(Array/Vector) 비교 비교 항목 배열 (Array / std::vector) 연결 리스트 (Linked List / std::list) 메모리 할당정적/동적 연속된 메모리 공간동적 비연속적인 메모리 공간 (필요할 때마다 할당)임의 접근 (Search by Index)$O(1)$ (인덱스로 바로 접근 가능)$O(N)$ (처음부터 차례대로 찾아가야 함)삽입/삭제 (Insertion/Deletion)$O(N)$ (데이터를 뒤로 ..

C++ 표준 템플릿 라이브러(STL)에서 제공하는 std::queue는 FIFO(First In, First Out - 선입선출) 구조를 구현한 컨테이너 어댑터(Container Adapter)이다. Queue의 핵심 개념FIFO (First In, First Out): 가장 먼저 들어간 데이터가 가장 먼저 나온다. (예: 줄 서기, 프린터 인쇄 대기열)제한된 접근: 데이터는 맨 뒤(Back)로만 추가되고, 맨 앞(Front)에서만 제거 및 조회할 수 있다. 스택과 마찬가지로 임의 접근(인덱스 조회) 및 반복자(Iterator)를 통한 중간 순회가 불가능하다. 주요 멤버 함수 및 시간 복잡도std::queue의 모든 주요 연산은 $O(1)$의 시간 복잡도를 가진다.push(val)큐의 맨 뒤(Back)에..

C++ 표준 템플릿 라이브러리(STL)에서 제공하는 std::stack은 LIFO(Last In, First Out - 후입선출) 구조를 구현한 컨테이너 어댑터(Container Adapter)이다. Stack의 핵심 개념LIFO (Last In, First Out): 가장 마지막에 들어간 데이터가 가장 먼저 나오게 됨제한된 접근: 중간에 있는 원소에 직접 접근할 수 없으며, 오직 가장 위에 있는 원소(Top)만 읽거나 제거할 수 있음. 임의 접근(인덱스 조회) 및 반복자(Iterator)를 통한 순회가 불가능함 주요 멤버 함수 및 시간 복잡도std::stack의 모든 주요 연산은 $O(1)$의 시간 복잡도를 가진다. push(val)스택의 맨 위에 원소 val을 추가함.$O(1)$emplace(args..