728x90
리스트란?
- 리스트는 배열 기반 자료구조로, JavaScript에서 Array 객체를 통해 사용된다.
🔹 리스트 주요 연산
const list = [10, 20, 30, 40, 50];
// 조회 (O(1))
console.log(list[2]); // 30
// 삽입 (끝: O(1), 앞/중간: O(n))
list.push(60); // [10, 20, 30, 40, 50, 60]
list.unshift(0); // [0, 10, 20, 30, 40, 50, 60]
// 삭제 (끝: O(1), 앞/중간: O(n))
list.pop(); // [0, 10, 20, 30, 40, 50]
list.shift(); // [10, 20, 30, 40, 50]
// 탐색 (O(n))
console.log(list.indexOf(30)); // 2
console.log(list.includes(50)); // true
🔹 리스트를 활용한 코딩 테스트 예제
배열을 거꾸로 뒤집기
function reverseArray(arr) {
return arr.reverse();
}
console.log(reverseArray([1, 2, 3, 4, 5])); // [5, 4, 3, 2, 1]
연속된 숫자의 누적 합 구하기 (Prefix Sum)
function prefixSum(arr) {
const result = [arr[0]];
for (let i = 1; i < arr.length; i++) {
result.push(result[i - 1] + arr[i]);
}
return result;
}
console.log(prefixSum([1, 2, 3, 4])); // [1, 3, 6, 10]
슬라이딩 윈도우 (고정된 길이의 최대 합 구하기)
function maxSumSubarray(arr, k) {
let maxSum = 0, windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
for (let i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9
연결 리스트란?
- 연결 리스트는 노드(Node)와 포인터(참조)로 이루어진 자료구조이다.
🔹 단일 연결 리스트(Singly Linked List)
- 각 노드가 값과 다음 노드를 가리키는 포인터를 포함합니다.
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// 리스트 끝에 값 추가 (O(n))
append(value) {
const newNode = new ListNode(value);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// 리스트 출력
print() {
let current = this.head;
const values = [];
while (current) {
values.push(current.value);
current = current.next;
}
console.log(values.join(" -> "));
}
}
// 연결 리스트 사용 예제
const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.print(); // 10 -> 20 -> 30
🔹 연결 리스트를 활용한 코딩 테스트 예제
연결 리스트 뒤집기
function reverseLinkedList(head) {
let prev = null;
let current = head;
while (current) {
let next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// 연결 리스트 생성
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
// 리스트 출력 함수
function printList(head) {
let current = head;
const values = [];
while (current) {
values.push(current.value);
current = current.next;
}
console.log(values.join(" -> "));
}
// 예제 실행
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
console.log("원래 리스트:");
printList(head); // 1 -> 2 -> 3 -> 4
const reversedHead = reverseLinkedList(head);
console.log("뒤집힌 리스트:");
printList(reversedHead); // 4 -> 3 -> 2 -> 1
두 개의 정렬된 연결 리스트 합치기
function mergeTwoLists(l1, l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1.value < l2.value) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
// 예제 실행
const l1 = new ListNode(1);
l1.next = new ListNode(3);
l1.next.next = new ListNode(5);
const l2 = new ListNode(2);
l2.next = new ListNode(4);
l2.next.next = new ListNode(6);
console.log("리스트 1:");
printList(l1); // 1 -> 3 -> 5
console.log("리스트 2:");
printList(l2); // 2 -> 4 -> 6
const mergedList = mergeTwoLists(l1, l2);
console.log("합쳐진 리스트:");
printList(mergedList); // 1 -> 2 -> 3 -> 4 -> 5 -> 6
연결 리스트에서 중간 노드 찾기 (투 포인터 활용)
function findMiddleNode(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 예제 실행
const list = new ListNode(10);
list.next = new ListNode(20);
list.next.next = new ListNode(30);
list.next.next.next = new ListNode(40);
list.next.next.next.next = new ListNode(50);
console.log("주어진 리스트:");
printList(list); // 10 -> 20 -> 30 -> 40 -> 50
const middleNode = findMiddleNode(list);
console.log("중간 노드 값:", middleNode.value); // 30
리스트(List) vs 연결 리스트(Linked List)
| 비교 | 리스트 (배열 기반) | 연결 리스트 |
| 메모리 구조 | 연속된 메모리 공간 | 노드들이 포인터로 연결됨 |
| 접근 속도 | O(1) (인덱스로 접근 가능) | O(n) (순차 탐색 필요) |
| 삽입/삭제 속도 | O(n) (중간 삽입/삭제 시 요소 이동 필요) | O(1) (포인터 변경으로 해결 가능) |
| 메모리 사용량 | 데이터만 저장 | 추가로 포인터 저장 공간 필요 |
| 정렬 | 기본 제공 (sort()) | 직접 구현 필요 |
리스트와 연결 리스트의 활용 패턴 정리
| 문제 유형 | 배열 활용 | 연결 리스트 활용 |
| 인덱스로 접근 | O(1) | O(n) |
| 삽입/삭제 | O(n) (중간 요소 이동 필요) | O(1) (포인터 변경) |
| 정렬이 필요한 문제 | sort() 사용 가능 | 직접 구현 필요 |
| 연속적인 데이터 활용 | 슬라이딩 윈도우, 누적 합 | 느린 접근 속도로 부적합 |
| 데이터 삽입/삭제 빈번한 문제 | splice() 사용 가능하지만 성능 저하 | 효율적인 삽입/삭제 가능 |
| 노드 기반 문제 (ex: LRU 캐시, 그래프 연결) | 부적합 | 최적 |
결론
- 배열은 고정된 크기의 데이터를 다룰 때 유리하며, 빠른 접근이 필요한 문제에 적합합니다.
- 연결 리스트는 삽입/삭제가 빈번한 문제에서 성능이 뛰어나며, 노드 기반 문제(LRU, 그래프 탐색)에서 활용됩니다.
728x90