[CS] 자료구조(선형 자료 구조)

1. 선형 자료 구조

요소가 일렬로 나열되어 있는 자료 구조

 

 

1-1. 연결 리스트

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조(상자를 순서대로 나열한 데이터 구조, 몇 번째 상자인지만 알면 해당 상자의 요소를 꺼내기 쉬움)

• prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것
• 맨 앞에 있는 노드를 헤드라고 함
• 데이터를 추가와 삭제를 많이 할 때 사용
• 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트 3 종류가 있음

* 용어 설명
- 싱글 연결 리스트 : next 포인터만 가짐
- 이중 연결 리스트 : next 포인터와 prev 포인터를 가짐
- 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만, 마지막 노드의 next 포인터가 헤드 노드를 가리킴

 

 

1-2. 배열

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

(상자를 선으로 연결한 형태의 데이터 구조, 상자 안에 요소를 알려면 하나씩 상자 내부를 확인 해봐야 함)

 

• 중복을 허용하고 순서가 있음
• 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용(탐색을 많이 할 때)
• 직접접근과 순차적 접근이 있음

*용어 설명
- 직접 접근(=랜덤 접근) : 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
- 순차적 접근 : 데이터를 저장된 순서대로 검색해야 하는 기능

 

 

 

1-3. 벡터

동적으로 요소를 할당할 수 있는 동적 배열

• 컴파일 시점에 개수를 모른다면 벡터를 써야함
• 중복을 허용하고 순서가 있고, 랜덤 접근이 가능함

 

 

 

1-4. 스택

가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 가진 자료 구조

(재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰임)

 

 

 

 

1-5. 큐

먼저 집어넣은 데이터가 먼저 나오는 성질을 지닌 자료 구조

(CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용)

 

 

 

 

 

공부기록용으로 남기는 블로그입니다.      

잘못 작성된 사항이 있다면 댓글 남겨주세요^^

 

 

 

출처
- 면접을 위한  CS 전공지식 노트 : 주홍철