[CS] 11. 선형 자료 구조

자료 구조란 컴퓨터 과학에서 효율적인 접근과 수정을 하도록 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확하게, 자료 구조는 데이터 값의 모임, 데이터 간 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다. 보통 추상 자료형의 선택으로 시작하는 자료구조는 잘 선택하면 효율적인 알고리즘이 가능하다. 효과적으로 설계된 자료구조는 실행 시간, 메모리 용량과 같은 자원을 최소로 사용하며 연산을 수행한다.

자료의 특성, 크기, 사용법, 연산의 종류와 기억 공간의 크기에 따라 자료구조를 선택할 수 있으며, 자료구조의 종류는 자료형에 따라 분류하는 단순 구조, 자료 구조와 자료 간 관계가 1:1인 선형 구조, 1:N 또는 N:N 구조인 비선형 구조, 파일 구조로 나뉜다.

 

배열

• 가장 일반적인 구조
• 메모리 상 같은 타입의 자료가 연속적으로 저장된다.
• 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위

인덱스를 사용하여 데이터를 검색하고 변경할 수 있으며, 데이터를 정렬하거나 탐색할 때는 유용하나 삽입과 삭제 작업이 비효율적이다. 배열은 크게 정적 배열과 동적 배열로 나뉜다.

1. 정적 배열

프로그램 실행 중에 크기가 고정되어 있는 배열로, 배열의 크기는 선언 시에 지정되며, 이후 크기를 변경할 수 없다. 정적 배열은 컴파일러가 할당한 메모리 공간을 사용하므로, 메모리를 효율적으로 사용할 수 있다. 하지만 배열의 크기가 고정되어 있기 때문에, 배열의 크기를 변경할 수 없는 한계점이 존재.

2. 동적 배열

프로그램 실행 중에 크기를 동적으로 할당할 수 있는 배열로, 필요한 만큼 메모리를 동적으로 할당하여 사용합니다. 그러나 메모리를 할당하고 해제하는 과정에서 오버헤드가 발생할 수 있으며, 메모리를 낭비하는 경우가 존재 가능.

 

튜플

둘 이상의 자료형을 묶음으로 다루는 구조

연결 리스트

데이터를 연속된 메모리 공간에 저장하지 않고, 각각의 데이터를 포인터(pointer)로 연결하여 구성하는 자료 구조이다. 삽입과 삭제가 용이하며, 메모리 공간을 유연하게 사용 가능하다. 하지만 인덱스를 이용한 빠른 접근은 불가능. 노드를 단위로 하고, 노드가 다음 노드를 가리키는 참조값으로 구성. 노드가 다른 노드를 가리키지 않으면 리스트의 끝임을 의미한다.

(파이썬의 경우 리스트 자료형이 연결 리스트의 기능을 포함하고 있다.)연결 리스트는 데이터의 삽입과 삭제가 용이하며, 메모리 공간을 유연하게 사용 가능하다. 하지만 인덱스를 이용한 빠른 접근은 불가능하기 때문에 연결 리스트는 데이터의 순차적인 접근이 필요한 경우에 적합하다.

 

1. 단일 연결 리스트

각 노드가 다음 노드를 가리키는 포인터만을 가지고 있는 형태의 연결 리스트로 노드의 삽입과 삭제가 용이하며, 메모리를 효율적으로 사용 가능하다. 하지만 단일 연결 리스트는 특정 노드에 바로 접근할 수 없기 때문에, 인덱스를 이용한 빠른 접근은 불가능

2. 이중 연결 리스트

각 노드가 다음 노드와 이전 노드를 가리키는 포인터를 모두 가지고 있는 형태의 연결 리스트로 단일 연결 리스트와 달리 양방향으로 탐색이 가능하기 때문에, 양방향으로 노드를 탐색하는 알고리즘에 적합

원형 연결 리스트

각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트로, 데이터의 순환(Circular)을 나타내는 경우나, 무한 루프(Infinite Loop)를 생성해야 하는 경우, 또는 우선순위 큐(Priority Queue)나 라운드 로빈 스케줄링(Round Robin Scheduling) 등의 알고리즘을 구현하는 경우에 원형 연결 리스트가 활용된다.

이중 연결 리스트

이중 연결 리스트는 단일 연결 리스트와 비슷한 특징을 갖지만, 단일 연결 리스트와 달리 노드를 삭제할 때 삭제할 노드의 이전 노드와 다음 노드의 포인터를 변경해줘야 하므로 구현이 복잡하다. 하지만 양방향 탐색이 가능하다는 점과, 단일 연결 리스트와 달리 뒤에서부터 탐색하는 것도 가능하다는 장점이 존재한다.

 

➕양방향 탐색이 필요한 경우

• 역순으로 탐색해야 하는 경우
• 노드를 중간에 삽입하거나 삭제해야 하는 경우
• 스크롤, 브라우저 히스토리 등의 이전/다음 버튼 기능을 구현해야 하는 경우 등

환형 연결 리스트

환형 이중 연결 리스트는 데이터의 순환을 나타내는 경우나, 무한 루프(Infinite Loop)를 생성해야 하는 경우, 또는 우선순위 큐(Priority Queue)나 라운드 로빈 스케줄링(Round Robin Scheduling) 등의 알고리즘을 구현하는 경우에 활용.

이중 연결 리스트와 비슷하다. 차이점은 환형 연결 리스트의 경우 마지막 노드가 처음 노드를 가리키는 형태라는 것(리스트의 끝에 도달하면 처음 노드로 빠르게 이동이 가능해 리스트의 처음과 끝을 일반적인 이중 연결 리스트보다 더 빠르게 처리가 가능)

해시 테이블

해시 테이블은 K-V 값을 갖는 데이터를 저장하는 자료구조로, 각 Key에 대해 해시 함수를 사용해 값을 Value로 변환하고, 해시 값에 해당하는 인덱스에 데이터를 저장. 해시 함수는 각 키(Key)를 유일한 해시 값(Hash Value)으로 매핑하도록 구현. 데이터의 삽입, 삭제, 검색이 모두 O(1)의 상수 시간복잡도로 이루어진다. (해시 테이블의 크기와 충돌 정도에 따라 달라질 수 있다.)

스택

FILO 구조로, 먼저 저장된 것이 마지막에 나오는 자료구조로, 삽입과 삭제가 스택의 가장 위(가장 뒤)에서 일어난다. 스택은 컴퓨터의 함수 호출(Call)과 반환(Return) 등의 작업에서 많이 사용된다. 함수가 호출될 때, 호출된 함수의 정보(매개변수, 로컬 변수, 반환 주소 등)는 스택에 저장되며, 함수가 반환될 때에는 스택의 맨 위에 있는 자료가 삭제된다. 이를 통해, 함수 호출의 순서와 반환의 순서가 일치하는 것을 보장할 수 있습니다.

스택은 또한 중위 표기법으로 작성된 수식을 후위 표기법이나 전위 표기법으로 변환하거나, 괄호의 짝이 맞는지 확인하는 등의 작업과 DFS에도 사용된다.

큐

스택과 반대로, FIFO 구조이다. 먼저 저장된 것이 먼저 나오는 자료구조로, 삽입은 큐의 뒤에서, 삭제는 큐의 앞에서 일어난다. 큐는 대기열을 구현하는 데 많이 사용된다. (프린터 출력 대기열, 메시지 전송 대기열, 작업 스케줄링 대기열 등에서 큐 자료구조가 사용) 또한, BFS 등의 그래프 탐색 알고리즘에서도 사용된다.

 

덱

양쪽에서 자료를 빼고 넣을 수 있는 자료구조로, 덱은 큐와 스택의 장점을 모두 가지고 있어서, 큐나 스택만으로 구현하기 어려운 문제를 해결할 때 사용한다.

---

Reference

https://codingpractices.tistory.com/entry/CS-Data-Structure-자료-구조란-무엇일까

 

[CS] Data Structure, 자료 구조란 무엇일까?