[자료구조] 5.2. 선형 자료 구조

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다.

---

 

5.2. 선형 자료 구조

선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다.

 

 

1) 연결 리스트

연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조이다.

삽입과 삭제에 O(1), 탐색에 O(n)이 걸린다.

 

위와 같이 prev 포인터와 next 포인터로 앞과 뒤를 연결한 것이 연결 리스트이다.

연결 리스트는 다음과 같이 3가지 연결 리스트가 존재한다.

• 싱글 연결 리스트: next 포인터만 가진다.
• 이중 연결 리스트: next 포인터와 prev 포인터를 가진다.
• 원형 이중 연결 리스트: 마지막 노드의 next 포인터가 헤드 노드를 가리키는 이중 연결 리스트.

 

 

 

2) 배열

배열은 같은 타입의 변수, 정해진 크기, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.

또한, 중복을 허용하고 순서가 존재한다.

 

책에서는 정적 배열을 기반으로 설명하고 있다.

삽입과 삭제에 O(n), 탐색에 O(1)이 되어 랜덤 접근이 가능하다.

 

따라서 연결리스트는 삽입와 삭제, 배열은 탐색에 유리한 자료 구조라 할 수 있다.

그래서 배열은 인덱스에 해당하는 원소에 빠르게 접근해야 하거나, 간단하게 데이터를 쌓고 싶을 때 사용한다.

 

 

랜덤 접근과 순차적 접근

직접 접근이라고도 하는 랜덤 접근은 임의의 인덱스에 해당하는 데이터에 접근한다.

이는 데이터를 저장된 순서대로 검색하는 순차적 접근과 반대이다.

(참고로, 연결 리스트에서는 랜덤 접근이 불가능하다.)

 

 

 

 

3) 벡터

벡터는 동적으로 요소를 할당할 수 있는 동적 배열이다.

컴파일 시점에 개수를 모르는 경우에 사용하고, 중복을 허용하며 순서가 있고 랜덤 접근이 가능하다.

맨 뒤를 제외한 요소의 삽입과 삭제에 O(n), 탐색과 맨 뒤 요소의 삽입과 삭제는 O(1)이 걸린다.

 

 

 

 

4) 스택

스택은 가장 마지막에 들어간 데이터가 가장 먼저 나오는 LIFO(Last In First Out) 성질을 가진 자료구조이다.

재귀적인 함수, 알고리즘, 웹 브라우저 방문 기록 등에 쓰인다.

삽입과 삭제에 O(1), 탐색에 O(n)이 걸린다.

 

 

 

 

5) 큐

큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 성질을 가진 자료구조이다.

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용된다.

삽입과 삭제에 O(1), 탐색에 O(n)이 걸린다.