[자료구조] 선형(Linear) 자료구조의 종류와 특징

자료 구조는 알고리즘의 효율성을 결정하는 중요한 요소 중 하나다.
자료 구조는 크게 선형(Linear) 구조와 비선형(NonLinear) 구조로 나뉜다.

 

선형(Linear) 자료 구조

선형구조란 메모리상에 데이터 즉, 요소들이 연속으로 나열된 형태의 자료 구조다. 각 요소는 앞과 뒤의 요소와 1대1 관계를 가진다.

 

각 요소에 접근할 때는 직접 접근으로 빅오 표기법 O(1)의 시간 복잡도를 가지나 요소의 삽입 및 삭제 시에는 데이터 이동으로 인한 시간 복잡도가 증가하므로 O(n)의 시간 복잡도를 가진다.

 

2024.08.23 - [CS] - [자료구조] 시간 복잡도, 공간 복잡도, 빅오(Big-O) 표기법

[자료구조] 시간 복잡도, 공간 복잡도, 빅오(Big-O) 표기법

 

리스트(List)

크게 선형 리스트와 연결 리스트로 나뉘며 선형 리스트는 연속적인 기억장소에 저장되는 리스트 형태의 자료 구조다.

 

선형 리스트 예시는 아래와 같다.

 

반면, 연결 리스트는 각 데이터를 임의의 공간에 저장시키고 각 노드의 포인터 부분을 이용해서 서로 연결한 형태의 자료 구조다.

 

연결 리스트는 크게 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트로 나뉜다. 연결 리스트의 예시는 아래와 같다.

연결 리스트 종류	연결 형태
단순 연결 리스트	한 방향으로 앞에서 뒤로만 연결되어 있는 형태
원형 연결 리스트	단순 연결 리스트와 형태는 비슷하나 제일 끝 노드가 제일 앞 노드가 가리킴
이중 연결 리스트	각 노드의 앞과 뒤를 연결하는 형태 첫 노드와 마지막 노드는 NULL을 가리킴

 

한 번 선언하면 배열의 크기를 변경할 수 없는 선형 리스트에 비해 연결 리스트는 공간적 효율성이 더 뛰어나다.

 

선형 리스트 특징

• <인덱스, 값>의 쌍으로 표현
• 가장 간단한 자료구조
• 접근 속도가 빠름

 

연결 리스트 특징

• 각 노드와 포인터가 연결되어 있음
• 삽입, 삭제가 용이
• 접근 속도가 느림

선형 리스트의 함수는 아래와 같다.

create(n)	n개의 요소를 가진 배열 생성
retrieve(arr, i)	배열 arr의 i번째 요소 반환
store(arr, i, item)	배열 arr의 i번째 위치에 item 저장

 

스택(Stack)

스택은 먼저 들어간 자료가 나중에 나오는 LIFO(Last In First Out) 즉, 후입선출 형태의 자료 구조다.

웹 브라우저 방문기록, 괄호 검사, 깊이 우선 탐색 등에 활용된다.

 

스택의 함수는 아래와 같다.

create()	스택 생성
is_empty(s)	스택이 비어있는지 검사
is_full(s)	스택이 가득 찼는지 검사
push(s, e)	스택 맨 위에 요소 e를 추가
pop(s)	스택 맨 위의 요소 삭제
peek(s)	스택 맨 위의 요소 반환

 

큐(Queue)

큐는 한 쪽 끝은 삽입이 반대쪽 끝은 삭제가 이루어지는 자료 구조로 FIFO(First In First Out) 즉, 선입선출 형태의 자료 구조다.

프로세스 관리, 대기 목록, 너비 우선 탐색 등에 활용된다.

 

 

큐의 함수는 아래와 같다.

create()	큐 생성
init(q)	큐 초기화
is_empty(q)	큐가 비어있는지 검사
is_full(q)	큐가 가득 찼는지 검사
enqueue(q, e)	큐의 뒤에 요소 추가
dequeue(q)	큐의 앞에 있는 요소 반환 후 삭제
peek(q)	큐 앞에 있는 요소 반환

 

덱(Deque)

스택과 큐의 장점만 취합한 자료 구조로 입력 및 삭제가 양 끝단에서 발생할 수 있는 자료 구조다.

 

 

덱의 함수는 아래와 같다.

create()	덱 생성
init(dq)	덱 초기화
is_empty(dq)	덱이 비어었는지 검사
is_full(dq)	덱이 가득 차있는지 검사
add_front(dq, e)	덱 앞에 요소 추가
add_rear(dq, e)	덱 뒤에 요소 추가
delete_front(dq)	덱 앞에 있는 요소 반환 후 삭제
delete_rear(dq)	덱 뒤에 있는 요소 반환 후 삭제
get_front(q)	덱 앞에 있는 요소 반환
get_rear(q)	덱 뒤에 있는 요소 반환