5-2. 선형 자료 구조 - 연결 리스트, 배열, 벡터, 스택, 큐

1. 연결 리스트

연결 리스트는 데이터와 포인트로 구성된 노드 단위로, 이를 연결하는 방식으로 데이터를 저장하는 선형 자료 구조이다. 메모리 상에 연속적으로 저장되지 않아도 되며, 포인터만 따라가면 전체 리스트를 순회할 수 있다.

 

- 싱글 연결 리스트 : next 포인터만 가지는 것

- 이중 연결 리스트 : next, prev 포인터를 가지는 것

- 원형 이중 연결 리스트 : 이중 연결 리스트의 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것

 

 

 

2. 배열

배열은 동일한 타입의 데이터를 연속된 메모리 공간에 할당하여 저장하는 가장 기본적인 자료 구조이다.

 

- 랜덤 접근 : 원하는 요소의 인덱스를 통해 주소를 알아내어 접근하는 것

- 순차 접근 : 데이터를 처음부터 순서대로 하나씩 차례로 읽는 것

구분	배열	연결 리스트
메모리 저장	연속적인 공간에 저장	비연속적인 공간에 포인터로 연결
특정 원소 접근	빠름 (O(1), 랜덤 접근)	느림 (O(n), 순차 접근)
삽입/삭제	느림 (O(n), 데이터 밀림/당김 발생)	빠름 (O(1), 포인터 변경)
메모리 사용	메모리 낭비 없음 (포인터 오버헤드 없음)	포인터 저장을 위한 추가 메모리(오버헤드) 필요

 

 

 

3. 벡터

C++의 STL에서 제공하는 자료 구조로, 크기가 동적으로 변하는 배열의 개념이다. 배열처럼 연속된 메모리에 저장되며, 랜덤 접근으로 특정 원소에 접근한다. 만약 데이터 추가 시 할당된 메모리 공간이 부족하다면, 자동으로 더 큰 새로운 메모리 공간을 할당하여 기존 데이터를 복사하고 이동한다.

 

 

 

4. 스택

스택은 데이터를 LIFO (Last-In, First-Out) 원칙에 따라 관리하는 선형 자료 구조이다. 즉, 가장 나중에 삽입된 원소가 가장 먼저 제거된다. Push, Pop 등의 연산을 통해 데이터를 삽입하고 삭제한다. 주로 재귀함수, 웹 브라우저 방문 기록, 역순 문자열 처리 등에 사용한다.

 

 

 

5. 큐

큐는 데이터를 FIFO (First-In, First-Out) 원칙에 따라 관리하는 선형 자료 구조이다. 즉, 가장 먼저 삽입된 원소가 가장 먼저 제거된다. Enqueue, Dequeue 등의 연산을 통해 데이터를 삽입하고 삭제한다. 주로 스케줄링 큐, 프린터 출력 순서, BFS 등에 사용한다.