선형 자료 구조

본 게시글은 면접을 위한 cs 전공지식 노트를 토대로 작성되었습니다.

 

선형 자료 구조 : 자료를 구성하는 데이터를 순차적으로 나열시킨 형태

 

선형 자료 구조의 종류

선형 자료 구조의 종류로는 배열, 연결 리스트, 스택, 큐 등이 존재합니다.

 

 

 

1. 연결 리스트

각 데이터 요소들에 이전 데이터나 다음 데이터를 가리키는 참조를 부여하여 자료들을 연결하는 자료 구조를 말합니다. 이를 통해 공간적인 효율성을 극대화시킬 수 있습니다. 

삽입과 삭제는 O(1)이 걸리며, 탐색에는 O(N)이 걸립니다.(참조를 따라가며 데이터를 전부 탐색해봐야 하므로 O(N)이 걸림)

 

 

2. 배열

같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. 

이때, 삽입과 삭제에는 O(N)이 걸려서 데이터의 삭제와 추가를 많이 필요로 하는 경우에는 연결리스트를 사용하는 것이 좋습니다. 

 

 

3. 랜덤 접근과 순차 접근

랜덤 접근 : 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능입니다. 예시로서 배열이 있습니다.

순차 접근 : 데이터를 저장된 순서대로 검색해야 합니다. 예시로서 연결리스트가 있습니다.

 

배열은 랜덤 접근이 가능하며, 몇 번째 인덱스인지만 알면 해당 인덱스의 값을 얻어올 수 있습니다.

연결 리스트는 인덱스가 없는 리스트의 특징으로 인하여 특정 요소에 접근하기 위해서는 순차 탐색을 필요로 하므로 일반적으로 탐색 속도가 떨어집니다.

 

 

4. 벡터

동적으로 요소를 할당할 수 있는 동적 배열입니다. 컴파일 시점에서 개수를 모를 때 사용합니다.(벡터 내부에 값이 추가되면 자동으로 크기가 조절됨)

또한, 중복을 허용하고 순서가 있으며 랜덤 접근이 가능합니다.

 

 

5. 스택과 큐

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 가진 자료 구조입니다.(= LIFO)

큐는 먼저 넣은 데이터가 먼저 나오는 성질을 지닌 자료 구조입니다.(FIFO)

스택과 큐의 삽입과 삭제는 O(1)이 걸리며, 탐색은 O(N)이 걸립니다.(모든 데이터를 빼내서 확인해봐야 하므로)

 

 

 

 

 

 

---

참고 자료

면접을 위한 cs 전공지식 노트(주홍철)

https://g.co/kgs/Wy4DWg