선형 자료 구조

선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조이다.

연결 리스트

연결리스트란?

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화
시킨 자료 구조입니다.

• 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다.
• 연결리스트에는 싱글, 이중, 원형 이중 리스트가 있다.
• prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 모양이다.
• 맨 앞에 있는 노드를 head라고 한다.

각 연결 리스트의 정의

• 싱글 연결 리스트: next 포인터만 가지는 구조
• 이중 연결 리스트: next와 prev 포인터 두 가지다 가지는 구조
• 원형 이중 연결 리스트: 이중 연결 리스트와 같지만
  마지막 노드의 next 포인터가 헤드 노드를 가리키는 구조

배열

배열이란?

같은 타입의 변수들로 이루어져 있으며, 크기가 정해져 있다.
중복을 허용하고 순서가 있는게 특징이다.

※ 여기서 말하는 배열은 '정적 배열'을 기반으로 설명하는 것이다.
탐색에 O(1)이 되어 랜덤 접근이 가능하다.
삽입과 삭제에는 O(n)이 걸린다.

배열과 연결 리스트 비교

이를 보고 유추 할 수 있는 것은
데이터의 추가와 삭제를 많이하는 작업은 연결 리스트
탐색을 많이 하는 것은 배열로 하는 것이 좋다.

특히 배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나
간단하게 데이터를 쌓고 싶을 때 사용하게 된다.

이 말은 배열은 순서를 가지고 있기 때문에 인덱스 즉
각각의 정보에 번호가 있고 그 번호를 찾아 데이터를 찾는
방식이기 때문에 탐색은 배열이 좋다.

랜덤 접근과 순차적 접근

직접 접근이라고 하는 랜덤 접근은 동일한 시간에
배열과 같은 순차적인 데이터가 있을 경우 임의의
인덱스 번호를 찾아 그 인덱스의 해당 값에 있는
데이터에 접근할 수 있는 기능이다.
순차적 접근은 말 그대로 순차적으로 접근 하는 것이다.

이를 보면 알 수 있듯이 연결 리스트 경우에는
순차적으로 하나 하나 찾아야 하기 때문에
탐색 속도가 배열에 비해 느린 것을 알 수가 있다.

하지만 추가나 삭제 같은경우는 순서대로 순서가 있는
배열 같은경우 앞의 박스가 비어있다면 채워주고 그 뒤에
추가하는 방식이기 때문에 선만 연결 해주면 되는
연결 리스트보다 느리다.

벡터

벡터는 동적으로 요소를 할당할 수 있는 동적 배열이다.
컴파일 시점에 갯수를 모른다면 벡터를 써야 한다.

특징

• 중복을 허용한다.
• 순서가 있다.
• 랜덤 접근이 가능하다.

스택

스택은 가장 마지막에 들어간 데이터가 먼저 나오는 구조를 가지고 있는 자료구조이다.
보통 재귀함수, 알고리즘등에 사용이 되고, 웹 브라우저 방문 기록등에 사용이 된다.

큐

큐는 먼저 집어 넣어놓은 데이터가 먼저 나오는 성질을 가진 자료구조이다.
스택과는 반대되는 개념을 가지고 있다.
보통 CPU 작업을 기다리는 프로세스, 스레드 행렬, 네트워크 접속을 기다리는 행렬
너비 우선 탐색, 캐시등에 사용이 된다.

마지막으로..

선형 자료 구조 첫 번째로 연결 리스트와 배열을 알아 보았습니다.
각각이 장,단점이 있고 특징들이 명확하게 나뉘는 것을 잘 캐치해서
판단해야 할 것 같습니다.
그리고 나머지의 벡터, 스택, 큐가 있습니다.
위의 그림들은 면접을 위한 cs 전공지식노트 라는 책에서 발췌한 것입니다.
앞으로 공부해야 할 내용들이 많지만 하루하루더 발전하기위해
공부를 열심히 해야 할 것 같습니다.