Table Of Content

</aside>

선형 자료 구조

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

연결 리스트

연결 리스트 (Linked List)

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

삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다.

prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결 리스트이다.

연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있다.

맨 앞의 노드를 헤드(head)라고 한다.

싱글 연결 리스트 : next 포인터만 가진다.
이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말한다.

이중 연결 리스트

이중 연결 리스트는 앞에서부터 요소를 넣는 push_front(), 뒤에서부터 요소를 넣는 push_back(), 중간에 요소를 넣는 insert() 등의 함수가 있다.

const a = [];

// push_back (뒤에 추가)
for (let i = 0; i < 10; i++) a.push(i);

// push_front (앞에 추가)
for (let i = 0; i < 10; i++) a.unshift(i);

// begin()++ 위치(index 1)에 1000 삽입
a.splice(1, 0, 1000);

console.log(a.join(" "));
// 9 1000 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9

// pop_front (앞에서 제거)
a.shift();

// pop_back (뒤에서 제거)
a.pop();

console.log(a.join(" "));
// 1000 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8

연결리스트(Linked List)

연결리스트(=링크드리스트)는 컴퓨터 자료를 저장하는 구조 중 하나
데이터를 저장할 수 있는 공간 안에 다음 데이터의 주소를 가지고 있는 구조

배열과 비교

배열은 크기를 한번 정하면 늘리거나 줄일 수 없음
- 리스트 중간에 원소 삽입/삭제 시 다수의 데이터를 옮겨야함
반면, 연결리스트는 다른 데이터의 이동없이 중간에 데이터 삽입/삭제 가능
- 특정 요소를 찾을 때는 전체를 순회하므로 검색 시간이 느림

이중 연결 리스트(Double Linked List)

단방향 연결리스트의 한계
- 어떤 노드의 앞에 새로운 노드를 삽입하기 어려움
- 삭제의 경우 항상 삭제할 노드의 앞 노드가 필요
- 단방향 순회만이 가능
이중 연결 리스트
- 각각의 노드가 다음(next) 노드의 주소를 가지는 연결 리스트
- prev가 있어서 양방향으로 탐색하고 삽입하기 편함

배열

배열(Array)

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

또한, 중복을 허용하고 순서가 있다.

‘정적 배열’을 기반으로 설명

접근(참조)에 O(1)의 시간 복잡도를 가지며 랜덤 접근(random access)이 가능하다.

삽입과 삭제에는 O(n)이 걸린다.

따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 접근(참조)를 많이 하는 것은 배열로 하는 것이 좋다.

랜덤 접근과 순차적 접근

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

배열과 연결 리스트 비교

배열 : 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자이 요소를 끄집어낼 수 있다.
연결 리스트 : 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다.

배열은 n번째 요소의 접근(참고)가 빠르고 연결 리스트는 느리다.

배열의 경우 그저 상자 위에 있는 요소에 접근하면 되기 때문에 O(1)의 시간 복잡도를 가지고, 연결 리스트는 매번 상자를 열어야 하고 주어진 선을 기반으로 순차적으로 열어야 하기 때문에 접근(참조)의 경우 O(n)의 시간 복잡도를 가진다.

즉, 참조가 많이 일어나는 작업의 경우 배열이 빠르고 연결 리스트는 느리다.

하지만 데이터 추가 및 삭제는 연결 리스트가 더 빠르고 배열은 느리다.

배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 되기 때문이다.

const a = new Array(10);
for (let i = 0; i < 10; i++) a[i] = i;
console.log(a); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

벡터

벡터 (Vector)

벡터란?

크기가 자동으로 늘어나는 배열 (동적으로 요소를 할당할 수 있는 동적 배열)

일반 배열 → 크기 고정  (선언할 때 크기 결정)
벡터     → 크기 유동  (요소 추가할 때마다 자동 조절)

언제 사용하나? 컴파일 시점에 개수를 모른다면 벡터 사용

벡터의 특징

중복 허용 : [1, 1, 2, 2] 가능
순서 있음 : 인덱스로 순서 보장
랜덤 접근 : v[3]처럼 바로 접근 가능 O(1)

시간 복잡도

연산	복잡도	이유
탐색/`v[i]`	O(1)	인덱스로 바로 접근
`push_back()` 맨 뒤 삽입	O(1) amortized	아래에서 자세히 설명
중간 삽입/삭제	O(n)	뒤 요소를 전부 밀어야 함

push_back()이 왜 O(1)일까?

push_back()을 할 때의 벡터 크기 증가

push_back(1) → 용량 1  → 꽉 참! → 2배 확장 → 비용: 1+1
push_back(2) → 용량 2  → 꽉 참! → 2배 확장 → 비용: 1+1
push_back(3) → 용량 4  → 여유 ✓          → 비용: 2+1
push_back(4) → 용량 4  → 꽉 참! → 2배 확장 → 비용: 1
push_back(5) → 용량 8  → 여유 ✓          → 비용: 4+1
push_back(6) → 용량 8  → 여유 ✓          → 비용: 1
push_back(7) → 용량 8  → 여유 ✓          → 비용: 1
push_back(8) → 용량 8  → 꽉 참! → 2배 확장 → 비용: 1
push_back(9) → 용량 16 → 여유 ✓          → 비용: 8+1

매번 확장하는 게 아니라, 2의 제곱승 + 1번째(1, 2, 3, 5, 9번째 …)에만 확장

수식으로 보면?

// 수식을 풀어서 설명하면:
비용(cᵢ) = 확장 없으면 1
          확장 있으면 1 + 2ᵏ  (기존 요소 복사 비용)

n번 push_back() 총 비용 T(n):

T(n) = (그냥 삽입 비용 합) + (확장 비용 합)
     = n  +  (1 + 2 + 4 + 8 + ... + 2^logn)
     = n  +  (2n - 1)
     = 3n - 1

이걸 n으로 나누면 평균 비용 = 3 → 상수

amortized O(1)?

비싼 날이 가끔 있지만, 평균 내면 항상 저렴한 것

마치 헬스장 월정액과 같다:

매일 가면 하루 비용 1,000원 (저렴)
어쩌다 한 번 비싼 날이 있어도 월 평균으로 보면 O(1)에 수렴

확장 비용이 가끔 크게 발생해도, 전체 연산 수로 나눈 평균은 상수(3)이기 때문에 push_back()은 O(1) amortized라고 할 수 있다.

const v = [];

// 1~10 push_back 뒤에서 추가
for (let i = 1; i <= 10; i++) v.push(i);
console.log(v.join(" "));
// 1 2 3 4 5 6 7 8 9 10

// pop_back (맨 뒤 제거)
v.pop();
console.log(v.join(" "));
// 1 2 3 4 5 6 7 8 9

// erase(begin, begin+1) → 맨 앞 1개 제거
v.splice(0, 1);
console.log(v.join(" "));
// 2 3 4 5 6 7 8 9

// find(begin, end, 100) → 100 찾기
const a = v.indexOf(100);
if (a === -1) console.log("not found");
// not found

// fill(begin, end, 10) → 전체를 10으로 채우기
v.fill(10);
console.log(v.join(" "));
// 10 10 10 10 10 10 10 10

// clear → 배열 비우기
v.length = 0;
console.log(v.join(" "));
// (빈 줄)

스택

큐