선형 데이터 구조
선형 데이터 구조의 개요
-
데이터 구조가 선형이라는 것은 데이터 구조를 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬되어 있음을 뜻한다.
-
이러한 데이터 구조는 이해하기 쉬울 뿐더러 프로그램 개발할 때 사용하기 쉽다.
선형 데이터 구조
-
배열 , 리스트 : 범용적인 데이터 구조. 모든 데이터 구조가 배열이나 리스트에서 파생됐거나 어떤 방식으로든 배열과 리스트를 사용하기 때문이다.
-
배열과 리스트를 이해하면 다른 데이터 구조를 다루기 위한 기반 지식
랜덤 접근과 순차적 접근
직접 접근이라하는 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능.
데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대
배열
✨ 배열은 자료형이 같은 요소들을 저장한다.
- 배열에 저장된 각각의 자료를 요소(element)라고 한다.
- 요소에 매겨진 숫자를 배열의 인덱스.
- 중복을 허용하고, 순서가 있다.
- 인덱스 기반으로 탐색하기에 O(1)의 Random Access가 가능.
- 다차원 배열은 요소가 배열로 이루어진 배열. 2차원배열은 가장 일반적인 다차원 배열, 여기에 데이터를 저장한 것을 행렬 이라 한다.
배열의 문제점
- 요소들의 순차적 구성 때문에 배열에서 데이터를 추가하거나 삭제할 때는 배열 내 다른 데이터의 순서를 다시 매겨야 하므로 처리하는 데 많은 시간이 걸린다.
- O(n) 시간 복잡도를 가진다.
- 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열
리스트
-
배열의 특별한 유형. 리스트의 요소는 흩어진 상태로 메모리에 저장된다.
-
이때문에 연결 리스트(Linked List라고도 한다)는 메모리를 더 효과적으로 사용
-
리스트의 요소는 데이터 요소와 포인터(=참조)의 쌍으로 구성
-
포인터는 리스트 내의 바로 다음 요소가 저장된 메모리 위치를 가리킨다
-
연결 리스트에서 데이터 요소와 다음 요소를 가리키는 포인터의 쌍을 '노드(node)' 라고 한다
-
연결리스트는 해당 리스트에 진입하는 지점이 있도록 구성, 이러한 진입점을 '헤드' 라고 한다.
-
노드 하나가 다른 노드를 가리키는 포인터 하나를 갖는 유형의 연길 리스트를 단방향 연결 리스트라 한다.
-
단방향 연결 리스트에서 마지막 노드는 다른 노드를 가리키지 않으므로 포인터는 널값을 갖는다.
- 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다.
백터
- 동적으로 요소를 할당할 수 있는 동적 배열. 중복을 허용하고, 랜덤 접근이 가능
- Array의 특성을 가진 리스트.
- 자바에서의 Vector는 동기화 처리가 된 ArrayList()를 이야기한다.
- 탐색하는데는 O(1)의 시간복잡도를 갖고, 요소를 삽입하거나, 삭제하는데는 O(n)의 시간이 걸린다. 다만 맨 뒤나 앞의 요소를 삭제하거나 삽입하는데는 O(1)의 시간이 걸린다.
스택
- LIFO (Last In First Out 후입선출) 자료 구조
- 푸시 : 스택에 요소를 추가하는 동작, 팝 : 스택에 요소를 삭제하는 동작
- 개념을 쉽게 시각화 가능(단순함)
- 정석 스택과 동적 스택으로 나눌 수 있다.
- 함수 호출, 스케줄링, 인터럽트 메커니즘 등의 다양한 기본 컴퓨팅 프로세스에 사용
단점
-
최상단에서만 데이터 요소를 삭제 및 추가가능.
-
이는 특정 요소를 검색하는 속도 재한
큐
- 각 요소에 우선순위를 부여하는 데이터 구조
- FIFO (First In First Out, 선입선출) 자료구조
- 인큐 : 큐에 요소를 추가 , 데큐 : 큐에 요소를 삭제
스택과 큐의 구조를 결합하면 매우 좋은 프로그램과 데이터구조를 만들 수 있다. 기본적인 큐는 선형 데이터 구조지만 비선형 데이터 구조의 큐도 있다.
우선순위 큐
- 기본적인 큐를 확장한 것. 키(값을 식별하고 검색하는 데 사용)와 값(실제 사용하는 데이터)의 체계를 사용해 큐의 요소들을 정렬.
- 우선순위 큐 구현에는 연결리스트나 배열과 같은 데이터 구조 사용.
- 모든 요소는 우선순위가 있으며 우선순위가 높은 요소가 먼저 삭제된다.
