지혜의 개발공부로그
자료구조, 선형(정적, 동적 자료구조) & 비선형 자료구조
14 Jul 2025 | Data Structure개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
자료구조란
자료구조는 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말한다. 각각의 자료구조에는 장단점이 있기에 어떤 자료구조가 최선일지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있다. 따라서 다양한 자료구조의 장단점을 살펴보며 어플리케이션의 특징에 따라 어떤 자료구조를 사용하는 것이 최선일지 판단하는 것이 중요하다.
자료구조는 선형과 비선형 등의 여러 속성을 기반으로 분류 가능하다.
- 선형 자료구조(Linear Data Structure) > 데이터 요소를 순서대로 정렬
- 정적 자료구조(Static Data Structure): 크기가 고정되어 있는 자료구조
- 동적 자료구조(Dynamic Data Structure): 크기가 바뀔 수 있는 자료구조
- 비선형 자료구조(Nonlinear Data Structure) > 데이터를 비연속적으로 연결
자료구조를 순회한다는 말은 자료구조의 첫번쨰 요소에서 마지막 요소로 이동한다는 것을 의미한다. 선형 자료구조에서는 첫번쨰 요소에서 마지막 요소까지 백트래킹(BackTracking)없이 쉽게 순회가 가능하지만, 비선형 자료구조에서는 종종 되돌아가야 한다.
비선형 자료구조에서는 원하는 요소에 접근하기 위해 백트래킹이나 재귀가 필요한 경우가 많기 때문에 개별요소에 접근하는 작업에는 선형자료구조가 더 효율적이다. 또한 선형 자료구조는 데이터를 쉽게 순회할 수 있어 비선형 자료구조에 비해 요소 전체를 변경하는 작업이 쉽고, 백트래킹 없이 모든 요소에 접근할 수 있어 자료구조를 설계하고 사용하는 것도 더 쉽다. 그치만 비선형 자료구조는 소셜네트워크 연결과 같은 데이터를 저장하기에 선형 자료구조보다 더 효율적이기 때문에 각각의 특징에 따라 알맞은 자료구조를 선택하는 것이 중요하다.
선형 자료구조
데이터의 요소가 순차적 혹은 선형으로 배열되고 일대일 관계에 있으며 각 요소가 이전 및 다음 인접 요소에 연결되는 자료구조
이러한 선형 자료구조에는 정적/동적 자료구조로 구분되어진다.
- 정적 자료구조: 크기가 고정되어있는 자료구조. 대표적인 예로
배열이 있다. 선언과 동시에 배열의 크기가 정해지고 이후에는 그 크기가 변경 불가능하다. 미리 할당된 메모리 공간에 데이터를 저장하기 때문에 데이터의 추가, 삭제, 크기 변경등이 제한적인 것이 특징이다. - 동적 자료구조: 크기가 동적으로 저정될 수 있는 자료구조. 대표적인 예로
ArrayList, Linked List, Queue, Stack이 있다. 필요에 따라 메모리에서 유연하게 공간을 할당하고 해제해 데이터를 저장할 수 있어 데이터의 추가, 삭제, 크기 변경등이 가능하다.
배열(Array)
인덱스를 사용해 배열의 각 요소를 쉽게 식별할 수 있는 인덱스 기반 데이터 구조를 사용
동일한 데이터 유형의 여러값을 저장하려는 경우 효율적으로 활용이 가능하다. 각 요소의 인덱스 접근이 용이!
연결 리스트(Linked List)
각 요소가 인접한 메모리 위치에 저장되지 않는 선형 자료구조로 포인터로 연결되는 것이 특징.
자료가 추가될 때마다 메모리를 할당받고, 자료는 링크로 연결된다. 자료의 물리적 위치와 논리적 위치가 다를 수 있다. 첫번쨰 노드는 Head, 마지막 노드의 다음 포인터는 항상 null이다.
스택(Stack)
작업이 수행되는 특정 순서를 따르는 선형자료구조 > LIFO(Last In First Out)으로 마지막에 쌓인 데이터가 먼저 나오는 후입선출 방식이다. 데이터 입력 및 검색은 한쪽 끝에서만 가능하고 데이터 입력은 push(), 삭제는 pop()으로 이루어진다.
큐(Queue)
스택과 마찬가지로 작업이 수행되는 특정 순서를 따르는 선형자료구조 > FIFO(First In First Out)으로 처음 들어온 데이터가 먼저 나오는 선입선출 방식이다. 큐의 마지막 요소를 제거하기 위해서는 큐 안의 모든 요소를 제거해야만 가능하다.
덱, 데크(Deque)
양쪽 끝에서 삽입, 삭제가 모두 가능한 자료구조. Stack + Queue!