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

💡 본 글은 면접을 위한 CS 전공지식 노트 도서를 참고하여 정리하였습니다.

5.1 선형 자료구조

5.2.1 연결 리스트

intro

• 선형 = linear = 전후 1:1 연결 형태
• 비선형 = nonlinear = 전후 多:多 연결 형태

📌 선형 자료구조란 요소가 일렬로 나열되어 있는 자료구조이다.
하나의 자료 뒤에 하나의 자료가 존재한다. (비선형은 하나의 자료 뒤에 여러개의 자료가 존재할 수 있음)

선형 구조의 리스트는 선형 리스트(linear list)와 연결 리스트(linked list)로 나뉜다.

연결 리스트 - Linked List

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

즉, 각각의 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 한 줄로 연결되어 있는 방식이다.

이때, 다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있다.

prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결한다.

• 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
• 메모리를 연속적으로 사용하지 않는다.
• 순차적으로 접근해야 하기 때문에 탐색에는 불리하나, 삽입 · 삭제에는 용이하다.
• Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성이 드러난다.

 

종류

1) 싱글 연결 리스트 - Singly Linked List (=단순 연결 리스트)

• 다음 노드에 대한 포인터(next 포인터)만 가지고 있다.

2) 이중 연결 리스트 - Doubly Linked List

• 다음 노드(next 포인터), 이전 노드(prev 포인터)에 대한 포인터를 가지고 있다.
• 전 · 후로 탐색이 가능하다.
• 단순 연결 리스트에서는 최악의 경우 n번의 탐색을 해야한다. 반면 이중 연결 리스트에서는 얻고자 하는 데이터의 위치가 tail에 가까우면 tail에서부터 역방향으로 탐색이 가능하다. 따라서 탐색 시간 절약이 가능하다.

3) 원형 연결 리스트 - Circular Linked List

• 싱글 연결 리스트와 같지만, 마지막 노드의 next 포인터가 null이 아닌 head 노드를 가리킨다.
  

4) 원형 이중 연결 리스트 - Doubly Circular Linked List

• 이중 연결 리스트와 같지만, 마지막 노드의 next 포인터가 null이 아닌 head 노드를 가리킨다.

 

시간 복잡도

• 삽입 · 삭제 : O(1)
  • 처음에 삽입 · 삭제 : O(1)
  • 중간에 삽입 · 삭제 : O(n)
  • 끝에 삽입 · 삭제
    • 끝을 가리키는 별도의 포인터를 갖는 경우 : O(1)
    • 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n) ← 탐색 시간이 소요되기 때문
• 탐색 : O(n)

삽입, 삭제는 용이하지만 접근 속도가 느리다.

 

5.2.2 배열

배열

✏️ 동적배열도 있지만 정적배열을 기반으로 설명한다.

• 같은 타입의 데이터를 여러개 나열한 선형 자료구조
• 연속적인 메모리 공간에 순차적으로 데이터를 모아놓음
• 크기가 정해져 있음 (선언할 때 크기를 정하면, 그 크기로 고정된다.)
• 중복 허용, 순서가 있다.

 

랜덤 접근과 순차적 접근

순차 접근 - Sequential Access

특정 데이터에서 원하는 데이터로 접근하기 위해서는 그 사이의 모든 데이터를 거쳐서 순차적으로 접근해야 한다.

랜덤 접근 - Random Access (=비순차 접근)

인덱스를 통해 원하는 데이터에 바로 접근할 수 있다.

 

배열 vs. 연결 리스트

배열	연결 리스트
크기 고정 → 지정된 크기 이상의 데이터 저장 불가능	크기의 제한이 없음 → 삽입·삭제 자유로움
연속된 메모리 주소를 할당 받음	연속되지 않은 메모리 주소 할당 받음
random access 가능	random access 불가능
탐색 빠름 O(1)	탐색 느림 O(n)
삽입 · 삭제 느림	삽입 · 삭제 빠름
index 존재	node 존재

 

활용 사례

• 배열
  • 정보를 저장할 때 많이 사용 (바구니 역할)
  • 불규칙적인 정보를 저장하거나, 이후에 다시 사용할 정보를 저장하거나 할 때 활용
• 연결리스트
  • 음악 스트리밍 어플에서 이전곡-다음곡을 연결할 때 많이 활용
  • 포토샵의 history 기능
    • history 내역이 쌓여서 특정 작업 시점으로 돌아가거나 다시 최근으로 돌아올 수 있다.

 

5.2.3 벡터

동적으로 요소를 할당할 수 있는 동적 배열이다. 컴파일 시점에 개수를 모른다면 벡터를 써야 한다.

• 중복 허용
• 순서가 있음
• 랜덤 접근 가능
• 탐색 or 맨 뒤의 요소를 삭제·삽입 : O(1)
• 맨 뒤나 맨 앞이 아닌 요소를 삭제·삽입 : O(n)

 

5.2.4 스택

스택

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다.

가장 마지막으로 들어간 데이터가 가장 먼저 나오는 선입후출 구조이다. (LIFO, Last In First Out)

• push : 스택에 데이터를 추가
• pop : 스택에서 데이터를 삭제

활용 분야

• 재귀적인 함수나 알고리즘에 사용됨
• 웹 브라우저 방문 기록

시간 복잡도

• 삽입 · 삭제 : O(1)
• 탐색 : O(n)

 

5.2.5 큐

큐

 

큐는 가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출 구조이다. (FIFO, First In First Out)

• enqueue : 큐에 데이터를 넣음
• dequeue : 큐에서 데이터를 꺼냄
• front : 데이터를 꺼내는 쪽
• rear : 데이터를 넣는 쪽

활용 분야

• CPU 작업을 기다리는 프로세스
• 스레드 행렬 or 네트워크 접속을 기다리는 행렬
• 너비 우선 탐색(BFS)
• 캐시시간 복잡도
• 삽입 · 삭제 : O(1)
• 탐색 : O(n)