선형 자료 구조

선형 자료 구조

선형 자료 구조는 데이터 요소들이 선형적으로 나열되어 있는 자료 구조로, 각 요소들이 순서에 따라 배치되어 있는 것을 의미한다.

연결 리스트(Linked List)

각 요소가 데이터와 다음 요소를 가르키는 포인터로 이루아진 선형 자료 구조이다.

메모리 상에 불연속적으로 저장되며, 삽입과 삭제가 O(1)으로 빠르지만, 특정 위치 요소에 접근하는데는 순차적으로 탐색해야 하기 때문에 검색 O(n)으로 느리다.

배열(Array)

동일한 데이터 타입의 요소들이 메모리 상에 연속적으로 저장되는 선형 자료 구조이다.

인덱스를 이용하여 특정 위치 접근이 가능하여 빠른 검색이 가능하다.

메모리 할당이 연속적이기 때문에 빠른 데이터 접근이 가능하다.

크기가 고정되어 있기 때문에 크기 변경이 어렵고, 요소를 삽입과 삭제하는 연산이 비효율적일 수 있다.

 

※데이터 삽입, 삭제가 많으면 연결 리스트 사용 / 탐색을 많이 하면 배열을 사용.

 

스택(Stack)

데이터를 후입선출(Last In First Out)의 방식으로 저장하는 선형 자료 구조이다.

데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지며, 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나온다는 특징이 있다.

삽입과 삭제의 시간 복잡도는 O(1), 탐색에 O(n)이 걸린다.

재귀적인 함수, 괄호의 짝을 맞추는 등의 알고리즘에 사용될 수 있다.

큐(Queue)

데이터를 선입선출(Fist In First Out)의 방식으로 저장하는 선형 자료 구조이다.

데이터의 삽입은 큐의 한쪽 끝에서, 삭제는 반대 쪽에서 이루어지며, 가장 먼저 넣은 데이터가 먼저 나온다는 특징이 있다.

삽입과 삭제의 시간 복잡도는 O(1), 탐색에 O(n)이 걸린다.

데이터의 순서를 유지해야 하는 상황에서 사용될 수 있다.