선형 데이터 구조란 무엇입니까?
요소가 일렬로 배열된 데이터 구조입니다.
1. 연결 리스트
연결 리스트는 데이터 주변의 노드를 포인터로 연결해 공간 효율성을 극대화한 데이터 구조다.
삽입 및 삭제 비용은 O(1), 검색 비용은 O(n)입니다.
- 단일 연결 리스트: 다음 포인터 하나만
- 이중 연결 리스트: next 포인터와 prev 포인터가 있습니다.
- 원형 이중 연결 리스트: 이중 연결 리스트와 동일하지만 마지막 노드의 Next 포인터가 헤드 노드를 가리킨다는 점이 다릅니다.
2. 어레이
배열은 일정한 크기를 가진 동일한 유형의 변수 그룹이며 연속 메모리 위치에 있는 데이터 모음입니다.
또한 반복을 허용하고 순서가 있습니다.
배열은 인덱스에 해당하는 요소에 빠르게 액세스해야 하거나 단순히 데이터를 쌓을 때 사용됩니다.
배열과 연결 목록 비교
배열은 상자를 순서대로 나열하는 데이터 구조입니다.
상자의 수를 알면 해당 상자의 요소를 검색할 수 있습니다.
Linked List는 상자들이 선으로 연결된 형태의 데이터 구조인데, 차이점은 상자 안의 요소를 알기 위해서는 상자 안을 하나씩 들여다봐야 한다는 것입니다.
배열을 사용하면 검색이 더 빠르지만 연결 목록을 사용하면 데이터 추가 및 제거가 더 빠릅니다.
3. 캐리어
벡터는 요소를 동적으로 할당할 수 있는 동적 배열입니다.
컴파일 타임에 카운트를 모른다면 벡터를 사용해야 합니다.
반복적이고 순서가 지정된 무작위 액세스를 허용합니다.
4. 스택
스택은 후입선출(last-in-first-out) 속성이 있는 데이터 구조입니다.
재귀 함수, 알고리즘, 웹 브라우저 방문 기록 등에 사용됩니다.
삽입 및 삭제 비용은 O(1), 조회 비용은 O(n)입니다.
5. 팁
큐는 먼저 삽입된 데이터가 먼저 나오는(First In, First Out) 특성을 가진 데이터 구조로, 스택과 달리 나중에 삽입된 데이터가 먼저 나온다.
삽입 및 삭제 비용은 O(1), 조회 비용은 O(n)입니다.
CPU 작업을 기다리는 프로세스, 스레드 매트릭스 또는 네트워크 연결 대기 매트릭스, 너비 우선 검색, 캐시 등