선형 자료구조
선형 자료구조
- 선형 자료구조란 요소가 일렬로 나열되어있는 자료구조를 뜻한다.
연결리스트
Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장한다. Linked List는 물리적인 메모리상에서는 비연속적으로 저장되지만 Linked List를 구성하는 각각의 Node가 다음 Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조이다. 단, 마지막 Node가 가리키는 address는 null값으로 저장되어있다.
배열
가장 기본적인 자료구조에 속하며, 연속된 메모리 공간에 순차적으로 데이터를 저장하는 선형 자료구조이다. 배열의 가장 큰 특징으로는 `색인(index)`으로 해당 원소(element)를 접근할 수 있다는 점과 논리적 저장 순서와 물리적(메모리) 저장 순서가 일치한다.
접근할 때의 시간 복잡도는 `Big-O(1)`에 해당 하며 즉,비순차접근(Random Access)가 가능하다는 장점이 존재한다.
Random Access vs Sequential Access
순차 접근
- 말 그대로 자료의 요소를 순차적으로 접근하는 것을 얘기한다.
- 시간 복잡도가 높으며 속도측면에서 비효율적인 구조로 꼽힌다.
- 대표적으로 연결리스트가 존재한다.
랜덤 접근 배열은 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있다. 즉, 랜덤 액세스(Random Access)가 가능하다.
✨ Array vs Linked List를 비교해서 설명해주세요
Array는 메모리상에서 연속적으로 데이터를 저장하는 자료구조입니다. Linked List는 메모리 상에서는 연속적이지는 않지만, 각각의 원소가 다음원소의 주소값을 저장해놓기에 논리적으로는 연속성을 보장받는 자료구조입니다.
그래서 각 operation 즉 내부 동작 작업의 시간복잡도가 다릅니다. 데이터조회,접근은 Array의 경우 O(1) Linked List의 경우 O(N)이며 삽입/삭제 또한 Array는 O(N),Linked List는 O(1)의 시간복잡도를 가집니다.
따라서 데이터의 양이 고정적이고, 조회작업이 많다면 Array를, 데이터의 개수가 불확실하고 삽입 또는 삭제 작업이 잦다면 Linked List를 사용하는 것이 좋습니다.
`조회`에서는 Array는 random access라는 특성상 빠르지만, Linked List는 순차접근의 특성상 느리다.
`삽입/삭제`에서는 Array의 시간복잡도는 맨 앞/뒤의 경우 시간복잡도가 O(1)이며, 맨 마지막 원소가 아닌 중간에 있는 원소를 삽입/삭제 할경우 `shift`가 일어나기 때문에 비용이 추가적으로 지불된다.이경우에는 시간복잡도가 O(N)이다.
하지만 Linked List도 삽입후 정렬 단계를 거치기에 표면적으로는 시간복잡도가 O(1)이지만, 실질적으로는 O(N)이다.
벡터
- 동적으로 요소를 할당할 수 있는 동적 배열이다.
- 컴파일 시점에 개수를 모륻다면 벡터를 써야한다.
- 중복이 허용되며 Random Acesss가 가능한 구조이다.
스택
스택은 가장 마지막으로 들어간 데이터가 첫번쨰로 나오는 LIFO 구조의 자료구조이다.
큐
queue는 선입선출 FIFO(First in First Out)의 자료구조입니다. 시간복잡도는 enqueue O(1),dequeue O(1)로, 활용 예시로는 Cache 구현, 프로세스 관리, 너비우선탐색(BFS)등이 존재합니다.
queue에 데이터를 offer하는 것을 `enqueue`라고 하며 반대로 poll하는 것을 `dequeue`라고한다. 또한 FIFO 구조임을 기억하자
