이 글에서는 선형 자료구조의 일반적인 특징과 각각의 선형 자료구조의 특징 그리고 어떤 연산을 지원하는지에 대해 알아보겠습니다.
선형 자료구조의 특징
-
순차적 구조
저장되어 있는 데이터가 순서대로 정렬되어 있습니다. -
순서가 정해짐
데이터가 삽입되거나 삭제되는 순서가 정해져 있습니다. -
고정되거나 동적인 크기
고정되거나 가변적인 크기를 가질 수 있습니다. -
효율적인 접근
데이터에 대한 접근이 효율적 입니다.
배열(Array)
배열은 같은 타입의 데이터들이 순서대로 메모리에 위치하는 자료구조입니다.
배열의 특징
- 동일한 타입의 데이터들의 집합이다.
- 메모리 공간상 연속적인 위치에 데이터들이 저장된다.
- 인덱스의 시작 위치가 0이다.
- 인덱스르 통한 임의적인 접근이 가능하다.
배열의 종류들
-
1차원 배열
가장 간단한 형태의 배열입니다. 하나의 열로 구성됩니다. 하나의 인덱스만 사용합니다. -
2차원 배열
열과 행으로 이루어진 배열입니다. 두 개의 인덱스를 사용하여 데이터에 접근 가능합니다. -
다차원 배열
2차원 이상의 차원으로 구성된 배열입니다.
배열이 지원하는 연산
- 읽기
- 삽입
- 삭제
- 검색
링크드 리스트(Linked List)
링크드 리스트는 노드가 포인터로 연결되어 있는 선형 자료구조입니다.
노드는 데이터를 연결하고 있으며 포인터는 다음 노드를 가리킵니다.
배열과는 달리 물리적 공간속에서 연속적으로 저장되어 있지 않습니다.
특징
-
노드
노드에 값과 다음 노드를 가리키는 포인터가 존재합니다.
1.1 데이터
노드가 가지는 값입니다.
1.2 포인터
다음 노드를 가리키는 포인터입니다. -
헤드
링크드 리스트에서 가장 앞에 있는 노드를 말합니다. 시작 지점입니다. -
꼬리
링크드 리스트에서 가장 뒤에 있는 노드를 말합니다. 끝입니다.
링크드리스트의 종류들
-
단일 링크드 리스트
모든 노드가 다음 노드의 주소를 가지고 있고 마지막 노드는 NULL을 가리킵니다.
-
이중 링크드 리스트
모든 노드가 두개의 포인터를 가집니다. 하나의 포인터는 앞의 노드를 다른 하나는 뒤의 노드를 가리킵니다. 맨 앞에서 맨 뒤로 또는 맨 뒤에서 맨 앞으로 순차적으로 접근할 수 있습니다.
-
원형 링크드 리스트
맨 마지막 노드와 맨 앞의 노드가 서로 연결되어 원형을 형성하는 링크드 리스트입니다.
링크드 리스트가 지원하는 연산
1.읽기
2.검색
3.삽입
4.삭제
스택(Stack)
후입선출 구조를 가지는 선형자료구조입니다.
스택의 종류들
-
고정 크기 스택
고정된 크기의 스택을 가집니다. 만약 스택이 찼는데 무엇인가를 넣으려고 시도한다면 오버플로우가 일어납니다.
스택에 아무것도 없는 상태에서 삭제가 일어나면 언더플로우가 일어납니다. -
가변 크기 스택
동적인 크기의 스택을 가집니다. 스택이 꽉 찬다면 크기를 늘립니다. 반대로 삭제가 일어날때 크기를 줄입니다.
링크드 리스트를 통해서도 구현 가능합니다.
스택이 지원하는 연산
- push()
- pop()
- top()
- size()
- isEmpty()
큐(Queue)
선입선출 구조를 가지는 선형 자료구조입니다.
큐의 종류들
-
삽입 제한 큐
삽입은 한 쪽에서만 일어날 수 있고 삭제는 양쪽에서 일어납니다. -
출력 제한 큐
삽인은 양 쪽에서 일어나지만 삭제는 한 쪽에서만 일어납니다. -
순환 큐
큐의 맨 마지막이 맨 처음과 연결되어 있습니다. -
Double-Ended Queue (Dequeue, 데크)
양쪽 끝에서 삽입과 삭제가 일어날 수 있습니다. -
우선순위 큐
우선순위에 따라 접근이 가능한 특별한 형태의 큐입니다.
큐가 지원하는 연산들
- Enquee
- Dequeue
- Peek() or front
- rear()
- isFull()
- isEmpty()
선형 자료구조의 장단점
장점
- 효율적인 데이터 접근
- 가변적인 크기
- 쉬운 구현
- 다재다능
- 간단한 알고리즘
단점
- 제한된 데이터 접근
- 메모리 오버헤드
- 일부 복잡한 알고리즘
- 메모리의 비효율적인 사용
- 특정 연산에 대한 부적합
