Stack?C/C++에서 ‘스택’은 **호출 스택(Call stack)**을 의미하기도 하고, **LIFO 자료구조(Stack)**를 의미하기도 합니다. 이 글에서는 두 개를 구분해 설명한 뒤, 자료구조 Stack을 구현해 보겠습니다. 메모리의 영역의 Stack(스택)은 지역 변수와 매개변수가 저장되는 영역입니다. 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸하게 됩니다. 함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 저장됩니다. 이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(Stack Frame)이라고 합니다.보통 스레드마다 일정 크기의 스택이 할당되며(환경에 따라 다름), 과도한 재귀..

이중 연결 리스트(Double-Linked-List) 란?이전에 포스팅한 연결 리스트 유형 중 하나로 단일 연결 리스트는 현재 노드에서 다음 노드를 가리키는 주소를 가지고 있지만 이중 연결 리스트는 본인의 이전 노드의 주소까지 지니고 관리하는 연결 리스트입니다. 단일 연결 리스트와 마찬가지로 선형적인 구조를 가지고 있으며 단일 연결 리스트와의 차이점은 아래와 같습니다.단일 연결 리스트는 한 방향 (현재 노드 - 다음 노드) 이동만 가능하지만 이중 연결 리스트는 양 방향 이동이 가능하다 (이전 노드 - 현재 노드 - 다음 노드)단일 연결 리스트는 이전 노드에 대한 정보가 없으니 이전 노드로 가기 위해선 `head`에서부터 찾아야 하지만 이중 연결 리스트는 현재 노드의 뒤로 가기, 즉 이전 노드로 이동이 가..

연결 리스트(Linked-List)란?연결 리스트는 자료구조 중 선형 자료 구조로 데이터 요소들을 노드(Node)로 구성된 자료 구조입니다. 각 노드가 데이터와 다음 노드의 주소를 가리키고 있으며. 이름과 같이 데이터가 들어있는 현재 노드와 다음 노드를 연결하며 사슬처럼 선형적으로 서로 연결되어 있는 구조를 의미합니다.연결 리스트의 내부에 노드가 다음 노드를 가리킬 때에 포인터를 통해 가리키기 때문에, 연결 리스트는 동적 크기 조정이 용이하고 빠른 삽입과 삭제가 가능합니다, 하지만 노드의 크기에 비례하여 실행 시간이 증가하는 선형적인 탐색(O(n))이 필요하기 때문에 크기에 비례하여 접근 속도가 느릴 수 있습니다.삽입/삭제 자체는 O(1)의 속도로 가능하지만 위치(이전 노드, 삭제할 노드 등)에 대한 정..