자료구조 - 선형 자료구조

자료구조(Data Structure)란 자료에 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법이다.

자료구조는 저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분되며, 선형 자료구조는 데이터가 일렬로 나열되어 있고 비선형 자료구조는 데이터가 특정한 형태를 띄고 있다. 선형 자료구조의 종류에는 array, linked list, stack, queue 등이 있으며 비선형 자료구조로는 tree, graph 등이 있다.

이번 포스팅에서는 선형구조를 가지고 있는 자료구조를 개념 위주로 살펴보고, 비슷한 것들끼리 묶어 비교해보려고 한다.  

 

---

배열

• 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
• 미리 크기를 정해놓고 생성하며, 해당 크기만큼의 연속된 메모리 공간을 할당받는다
• 연속된 주소를 할당받았기 때문에 index를 통해 원소에 접근이 가능하다.
• 탐색의 시간 복잡도는 O(1) / 삽입, 삭제의 경우 배열의 끝에서 삽입/삭제가 이루어지는 경우에는 O(1), 처음 또는 중간에 삽입하는 경우 이후의 데이터를 옮겨야 하므로 O(N)의 시간복잡도를 가진다. 

Linked List

• 연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 메모리를 연속적으로 사용하지 않는다.
• 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
• 탐색의 시간 복잡도는 O(N) / 삽입, 삭제의 경우 기본적으로 O(1)이나, 원하는 위치에 삽입을 원해 탐색시간이 소요되는 경우 O(N)이 될 수 있다.

배열 vs Linked List

• 데이터 접근 속도
  • Array는 인덱스를 통한 Random Access를 지원하므로 시간 복잡도 O(1)로 빠르게 찾을 수 있다.
  • LinkedList는 순차 접근 방식을 사용하므로 시간 복잡도 O(N)이 걸린다.
• 데이터의 삽입/삭제 속도
  • Array는 데이터를 중간이나 맨 앞에 삽입/삭제하는 경우 shift가 필요하므로 데이터가 많을수록 비효율적이다.
  • LinkedList는 중간 삽입/삭제는 똑같이 O(N)의 시간 복잡도를 갖지만, 맨 앞 또는 뒤에 삽입할 경우 O(1)의 시간복잡도를 갖는다.
  • 다만 LinkedList는 데이터 삽입/삭제마다 메모리 할당/해제가 일어나므로 시간복잡도는 빠를지라도 시스템 콜(System Call)에 있어서 Array보다 더 시간이 걸린다.
• 메모리 할당
  • Array는 정적 메모리 할당이 이루어진다. (Compile time)
  • LinkedList는 동적 메모리 할당이 이루어진다. (Runtime)
  • Array의 경우 데이터 삽입 시 모든 공간이 다 차버렸다면 새로운 메모리 공간이 필요하지만 LinkedList는 동적으로 할당받을 수 있다.

데이터 삽입/삭제가 빈번하다면 LinkedList를 사용하는 것이 좋고, 데이터 접근 속도가 중요하다면 Array를 사용하는 것이 좋다.

	배열	연결 리스트
장점	인덱스를 통한 빠른 접근 가능	삽입, 삭제 용이
단점	삽입, 삭제 오래 걸림	임의 접근이 불가능하여, 처음부터 탐색 진행해서 탐색해야 함
용도	빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때	데이터에 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때

---

Stack

스택은 값을 저장하려고 하면 가장 최근에 저장된 값 다음에 저장되며, 가장 최근에 삽입된 값이 먼저 삭제되는 LIFO(Last In First Out) 형식을 따르는 자료구조다. 삽입, 삭제 연산이 한 방향에서 이루어진다는 특징을 가지고 있다.

시간 복잡도의 경우 데이터의 삽입, 삭제, top 데이터 조회의 경우 O(1)의 시간 복잡도를 가지지만, 특정 데이터를 조회하려면 O(N)의 시간 복잡도를 갖는다.

 

스택이 활용되는 곳은 다음과 같이 다양하다.

• 시스템 스택(System Stack) / 실행시간 스택(Runtime stack) : 프로그램의 함수 호출과 복귀에 따른 실행 순서 관리
• 인터럽트 루틴 처리
• 웹 브라우저 방문 기록 관리 (뒤로 가기 버튼을 클릭 시에, 가장 나중에 열린 페이지부터 나오기 때문에 = 실행 취소(undo)와 같은 원리)
• 실행 취소 (undo)
• 수식의 후위 표기법(Postfix Notation)
• 수식의 괄호식 검사
• 계산기 검사
• 깊이 우선 탐색(DFS, Depth-First Search)

Queue

큐는 한 방향에서는 삽입 연산이, 반대 방향에서는 삭제 연산이 이루어지는 FIFO(First In First Out) 형식을 따르는 자료구조다. 시간 복잡도의 경우 데이터의 삽입, 삭제, front 데이터 조회의 경우 O(1)의 시간 복잡도를 가지지만, 특정 데이터를 조회하려면 O(N)의 시간 복잡도를 갖는다.

 

큐가 활용되는 곳은 다음과 같이 다양하다.

• 순차적으로 처리해야 하는 일 ( = 우선순위가 동일한 일)
• 프로세스 레디 큐
• 스케쥴링
• 캐시(Cache) 구현
• 네트워크 패킷 전송시 필요한 버퍼 대기 큐
• javascript의 Event Loop 관리 (비동기 처리)
• 키보드 버퍼
• 프린터의 출력 처리
• 너비 우선 탐색(BFS, Breadth-First Search)

 

스택으로 큐를 구현할 수 있는가?

큐는 선입선출의 구조로 데이터가 들어온 순서대로 나가게된다. 이는 스택 2개를 활용하여 구현 수 있다. 

스택 A와 B가 존재한다. 만약 큐에 PUSH하는 과정이 일어나면 스택 A에 PUSH를 한다. 이후 큐에 POP연산을 하게되면 스택 A의 모든 데이터를 스택 B로 옮긴다. 그렇게되면 스택 A의 역순으로 데이터가 저장될 것이고 스택 B를 POP하면 큐에 저장된 데이터 순서대로 출력된다.

 

큐로 스택을 구현할 수 있는가?

스택은 가장 마지막에 들어온 데이터가 가장 먼저 나온다. 이를 큐의 특징을 활용하여 구현해보자.

push 연산은 첫번째 큐에 원소를 추가하기 전에 첫번째 큐가 빌때까지 두번째 큐로 값을 옮겨준다. 그 후 첫번째 큐에 원소를 추가하고 두번째 큐에서 다시 첫번째 큐로 빌때까지 원소들을 전부 다시 옮겨준다. 쉽게 말하자면 원소를 추가할 때마다 원소들의 위치를 스택에 맞게 변경시키는 것이다. 이후 pop 연산은 첫번째 큐에서 dequeue만 하면 된다.

 

Deque

양방향에서 삽입, 삭제 연산이 모두 이루어지는 큐를 말한다. front에서만 output이 발생하고 rear에서만 input이 발생하는 입출력의 방향이 제한되어 있는 큐나 스택과 달리 덱은 양방향에서 입출력이 가능하다.

 

이러한 특성 때문에 스케줄링 알고리즘을 수행할 때 스케줄링이 복잡해질수록 덱이 더 효율적으로 동작한다. 즉, 우선순위를 관리하는 데 있어 스택과 큐에 비해 이점을 갖는다.
예를 들어 오래된 프로세스에 우선순위를 주고 싶다면 앞에 있는 프로세스를 빼내야하는데 이는 스택에서 불가능하고 최근에 들어온 프로세스에 우선순위를 두고 싶다면 큐에서 불가능하다. 반면 덱은 두 경우 모두에서 사용 가능하다.

 

 

 

출처

https://velog.io/@xxhaileypark/%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-Array-LinkedList

[자료 구조] 배열 & 연결 리스트 (Array & LinkedList)

https://github.com/Seogeurim/CS-study/tree/main/contents/data-structure

GitHub - Seogeurim/CS-study: 🌎 진정한 컴퓨터공학도가 되기 위한 우리들의 지식 정리 공간 💥

https://velog.io/@oeueoo/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Stack-Queue

[자료구조] Stack, Queue