선형 자료구조는
데이터가 일렬로 나열된 형태로, 각 데이터 요소가 선형적으로 연결되어 있습니다.
자료구조를 이렇게 나눈 이유는 얼만큼 빠르게 요소에 접근하냐와
1. 배열 (Array)
정의: 고정된 크기의 동일한 데이터 타입의 요소 모음으로, 메모리에 연속적으로 저장됩니다.
특징:
- 인덱스를 통해 빠른 접근이 가능 (O(1)).
- 크기가 고정되어 있어 동적 크기가 필요할 경우 재할당이 필요합니다.
차이점: 메모리 공간이 연속적이며, 크기가 고정되어 있어 유연성이 떨어집니다.
2. 연결 리스트 (Linked List)
정의: 노드들이 포인터로 연결된 동적 자료구조로, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다.
종류:
- 단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드에 대한 포인터만 가짐.
- 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전 노드와 다음 노드에 대한 포인터를 모두 가짐.
- 원형 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리켜, 순환 구조를 형성.
특징:
- 크기가 동적으로 변할 수 있어 유연함.
- 노드 삽입 및 삭제가 간편 (O(1), 노드의 위치를 알고 있을 때).
차이점: 메모리 공간이 비연속적이며, 포인터를 사용하여 연결되기 때문에 배열보다 더 유연하나, 접근 속도가 느림 (O(n)).
3. 스택 (Stack)
정의: 후입선출(LIFO) 방식으로 데이터를 저장하는 구조입니다. 즉, 마지막에 추가된 데이터가 가장 먼저 제거됩니다.
특징:
인덱스로 꺼내는 것이 아닌 마지막에 추가된 데이터순으로 꺼낼 수 있습니다.
차이점: 배열이나 연결 리스트와 달리, 데이터 접근이 제약되어 있으며, 특정 원소에 직접 접근할 수 없습니다.
4. 큐 (Queue)
정의: 선입선출(FIFO) 방식으로 데이터를 저장하는 구조입니다. 즉, 가장 먼저 추가된 데이터가 가장 먼저 제거됩니다.
종류:
- 기본 큐 (Basic Queue): 일반적인 FIFO 큐.
- 우선순위 큐 (Priority Queue): 각 요소에 우선순위가 부여되어, 우선순위가 높은 데이터가 먼저 제거됨.
- 원형 큐 (Circular Queue): 배열을 이용하여 큐의 공간을 효율적으로 사용하기 위한 구조로, 큐의 끝과 시작이 연결됩니다.
특징:
스택과 유사하게 인덱스로 꺼내는 것은 아니지만 데이터를 넣은 순서대로 꺼낼 수 있습니다.
차이점: 스택과 마찬가지로, 배열이나 연결 리스트와 달리 데이터 접근이 제약되어 있습니다.
연속적 메모리란
데이터가 메모리의 연속된 공간에 저장되는 방식입니다.
장점은 빠른 접근 속도로 인덱스를 사용하여 직접적으로 메모리주소를 계산하므로 요소에 즉시 접근이 가능합니다.
단점은 크기가 고정되어 있어 크기 변경이 필요할 경우 재할당이 필요합니다. 메모리의 낭비가 발생할 수 있습니다.
비연속적 메모리란
데이터가 메모리의 비연속적인 공간에 저장되는 방식입니다.
장점은 크기를 추가와 삭제를 통해 조절이 가능해서 메모리를 효율적으로 사용할 수 있습니다.
단점은 접근 속도가 느립니다. 특정 요소에 접근 하기 위해서는 포인터를 따라가야 하므로 시간이 더 걸릴 수 있습니다.
유연성이란
자료구조가 동적으로 크기를 조정하거나 데이터를 추가/삭제하는 데 얼마나 용이한지를 나타냅니다.
요약
배열 : 고정된크기 , 연속적 메모리, 빠른 접근
크기가 정해져 있으며 빠른 접근이 필요할때
연결 리스트 : 동적인 크기 , 비연속적인 메모리 , 유연하지만 느린접근
크기가 정해져 있지 않고 추가와 삭제가 필요할 때
스택 : 마지막의 데이터를 꺼내는 과정
뒤로 가기등에 사용 될 것 같습니다.
큐 : 순서대로 실행 시켜야 할 때 좋을 것 같습니다.