이미지 로딩 중...
AI Generated
2025. 11. 6. · 5 Views
단일 연결 리스트 완벽 가이드
단일 연결 리스트의 기본 개념부터 실무 활용까지 다룹니다. 노드 구조, 삽입/삭제 연산, 순회 방법 등을 실제 코드와 함께 배우고, 메모리 효율적인 데이터 구조 설계를 익힐 수 있습니다.
목차
- 단일 연결 리스트란 무엇인가 - 기본 개념과 구조 이해하기
- 리스트 끝에 노드 추가하기 - append 메서드 구현
- 리스트 앞에 노드 추가하기 - prepend 메서드 구현
- 특정 위치에 노드 삽입하기 - insertAt 메서드 구현
- 특정 값을 가진 노드 삭제하기 - remove 메서드 구현
- 리스트 순회와 출력하기 - print와 toArray 메서드 구현
- 특정 값 검색하기 - find와 indexOf 메서드 구현
- 리스트 역순 정렬하기 - reverse 메서드 구현
- 리스트 크기와 빈 상태 확인하기 - getSize와 isEmpty 메서드
- 리스트 초기화하기 - clear 메서드 구현
- 두 리스트 합치기 - concat 메서드 구현
- 중간 노드 찾기 - findMiddle 메서드 구현 (토끼와 거북이 알고리즘)
1. 단일 연결 리스트란 무엇인가 - 기본 개념과 구조 이해하기
시작하며
여러분이 음악 재생 목록을 만들 때, 각 곡이 다음 곡을 가리키는 형태로 연결되어 있다고 상상해보세요. 사용자가 "다음 곡" 버튼을 누르면 현재 곡에서 다음 곡으로 자연스럽게 이동하죠.
이것이 바로 단일 연결 리스트의 실제 활용 예시입니다. 배열을 사용하면 중간에 항목을 추가하거나 삭제할 때 모든 요소를 이동시켜야 하는 번거로움이 있습니다.
큰 데이터를 다룰 때는 이 작업이 상당한 성능 저하를 일으킵니다. 또한 배열은 크기가 고정되어 있어서 동적으로 크기를 조정하기 어렵습니다.
바로 이럴 때 필요한 것이 단일 연결 리스트입니다. 각 요소가 다음 요소의 위치만 기억하고 있어서, 중간에 삽입하거나 삭제할 때 주변 요소들만 조정하면 됩니다.
마치 기차 칸을 연결하듯이 유연하게 데이터를 관리할 수 있죠.
개요
간단히 말해서, 단일 연결 리스트는 각 노드가 데이터와 다음 노드의 주소를 가지고 있는 선형 자료구조입니다. 실무에서 이 자료구조가 필요한 이유는 명확합니다.
데이터의 크기를 미리 알 수 없거나, 중간에 빈번한 삽입과 삭제가 발생하는 경우에 배열보다 훨씬 효율적입니다. 예를 들어, 웹 브라우저의 방문 기록, 텍스트 에디터의 실행 취소 기능, 운영체제의 프로세스 스케줄링 같은 경우에 매우 유용합니다.
배열에서는 중간에 요소를 삽입하려면 O(n) 시간이 걸리지만, 연결 리스트에서는 참조만 바꾸면 되므로 O(1) 시간에 처리할 수 있습니다. 기존에는 고정된 크기의 메모리를 할당했다면, 이제는 필요한 만큼만 동적으로 메모리를 사용할 수 있습니다.
이 자료구조의 핵심 특징은 첫째, 각 노드가 독립적으로 메모리에 할당된다는 점입니다. 둘째, 한 방향으로만 순회가 가능합니다.
셋째, 헤드(head) 포인터만 있으면 전체 리스트에 접근할 수 있습니다. 이러한 특징들이 메모리를 효율적으로 사용하면서도 유연한 데이터 관리를 가능하게 합니다.
코드 예제
// Node 클래스: 데이터와 다음 노드를 가리키는 포인터를 저장
class Node {
constructor(data) {
this.data = data; // 노드가 저장하는 실제 데이터
this.next = null; // 다음 노드를 가리키는 포인터
}
}
// LinkedList 클래스: 전체 리스트를 관리
class LinkedList {
constructor() {
this.head = null; // 리스트의 첫 번째 노드
this.size = 0; // 리스트의 크기 추적
}
}
설명
이것이 하는 일: 단일 연결 리스트는 데이터를 노드라는 단위로 저장하고, 각 노드가 다음 노드의 위치를 기억하여 순차적으로 연결된 구조를 만듭니다. 첫 번째로, Node 클래스는 리스트의 기본 단위입니다.
각 노드는 두 가지 중요한 정보를 담고 있습니다. data 속성은 우리가 실제로 저장하고 싶은 값이고, next 속성은 다음 노드가 메모리 어디에 있는지를 가리킵니다.
처음 노드를 만들 때는 next가 null인데, 이는 "아직 다음 노드가 없다"는 의미입니다. 그 다음으로, LinkedList 클래스가 전체 리스트를 관리합니다.
head는 리스트의 시작점을 가리키는 매우 중요한 포인터입니다. 이 head만 알고 있으면, head.next, head.next.next 이런 식으로 계속 따라가면서 모든 노드에 접근할 수 있습니다.
size는 현재 리스트에 몇 개의 노드가 있는지 추적하여, 나중에 리스트의 크기를 빠르게 확인할 수 있게 합니다. 마지막으로, 이 구조가 실제로 메모리에서 어떻게 작동하는지 생각해보세요.
배열은 연속된 메모리 공간에 데이터를 저장하지만, 연결 리스트는 각 노드가 메모리의 서로 다른 위치에 흩어져 있을 수 있습니다. 노드들은 next 포인터로 연결되어 있기 때문에, 물리적으로 떨어져 있어도 논리적으로는 하나의 리스트를 구성합니다.
여러분이 이 코드를 사용하면 크기 제한 없이 데이터를 추가할 수 있고, 중간에 데이터를 삽입하거나 삭제할 때도 효율적으로 처리할 수 있습니다. 특히 데이터의 크기를 예측할 수 없는 실시간 시스템이나, 빈번한 삽입/삭제가 발생하는 애플리케이션에서 큰 이점을 제공합니다.
실전 팁
💡 head를 잃어버리면 전체 리스트에 접근할 수 없으므로, head를 항상 안전하게 보관하세요. 연산 중에 임시 변수를 사용해서 head를 보존하는 것이 좋습니다.
💡 노드를 삭제할 때는 자바스크립트의 가비지 컬렉션이 처리하지만, 명시적으로 next = null로 설정하면 메모리 누수를 방지할 수 있습니다.
💡 size 속성을 유지하면 리스트의 길이를 O(1) 시간에 알 수 있습니다. 순회하면서 세는 것보다 훨씬 효율적입니다.
💡 디버깅할 때는 각 노드의 data와 next를 출력하는 헬퍼 함수를 만들어두면 리스트의 상태를 쉽게 확인할 수 있습니다.
💡 실무에서는 타입스크립트를 사용하여 제네릭으로 구현하면 다양한 데이터 타입을 안전하게 다룰 수 있습니다.
2. 리스트 끝에 노드 추가하기 - append 메서드 구현
시작하며
여러분이 할일 목록 앱을 만들고 있다고 가정해보세요. 사용자가 새로운 할일을 추가할 때마다 리스트의 끝에 항목이 추가되어야 합니다.
가장 최근에 추가된 항목이 리스트의 마지막에 위치하는 것이 자연스럽죠. 단일 연결 리스트에서 끝에 노드를 추가하는 것은 생각보다 신경 써야 할 부분이 많습니다.
리스트가 비어있는 경우와 이미 노드가 있는 경우를 다르게 처리해야 하고, 마지막 노드를 찾기 위해 전체 리스트를 순회해야 할 수도 있습니다. 바로 이럴 때 필요한 것이 잘 설계된 append 메서드입니다.
모든 엣지 케이스를 고려하여 안전하게 노드를 추가하고, 리스트의 무결성을 유지할 수 있습니다.
개요
간단히 말해서, append 메서드는 새로운 노드를 생성하여 리스트의 맨 끝에 추가하는 기능입니다. 이 메서드가 실무에서 중요한 이유는, 데이터를 순차적으로 쌓아가는 작업이 매우 흔하기 때문입니다.
로그 시스템에서 새로운 로그를 기록하거나, 채팅 애플리케이션에서 새 메시지를 추가하거나, 작업 큐에서 새 작업을 등록하는 경우에 모두 append 연산을 사용합니다. 예를 들어, 실시간 주식 거래 시스템에서 새로운 거래 내역을 계속 추가하는 경우에 매우 유용합니다.
배열의 push 메서드처럼 단순해 보이지만, 연결 리스트에서는 마지막 노드를 찾아서 그 노드의 next를 새 노드로 연결해야 합니다. 기존에는 배열 인덱스로 바로 접근했다면, 이제는 head부터 시작해서 next를 따라가며 마지막 노드를 찾아야 합니다.
이 메서드의 핵심 특징은 첫째, 리스트가 비어있을 때는 head를 새 노드로 설정합니다. 둘째, 노드가 있을 때는 마지막 노드를 찾아서 연결합니다.
셋째, 항상 size를 증가시켜 리스트의 크기를 정확하게 유지합니다. 이러한 처리가 데이터 일관성을 보장합니다.
코드 예제
// 리스트 끝에 새로운 노드를 추가하는 메서드
append(data) {
const newNode = new Node(data); // 새 노드 생성
// 케이스 1: 리스트가 비어있는 경우
if (this.head === null) {
this.head = newNode; // head를 새 노드로 설정
} else {
// 케이스 2: 노드가 있는 경우 - 마지막 노드 찾기
let current = this.head;
while (current.next !== null) {
current = current.next; // 다음 노드로 이동
}
current.next = newNode; // 마지막 노드와 연결
}
this.size++; // 리스트 크기 증가
return this; // 메서드 체이닝을 위해 this 반환
}
설명
이것이 하는 일: append 메서드는 전달받은 데이터로 새 노드를 만들고, 리스트가 비어있는지 확인한 후, 적절한 위치에 노드를 추가하여 리스트를 확장합니다. 첫 번째로, 새로운 Node 객체를 생성합니다.
이 노드는 사용자가 전달한 data를 저장하고, next는 null로 초기화됩니다. 왜냐하면 이 노드는 리스트의 끝에 추가될 것이므로, 다음 노드가 없기 때문입니다.
그 다음으로, 리스트가 비어있는지 확인하는 중요한 분기점이 있습니다. this.head === null이면 리스트에 아무 노드도 없다는 뜻입니다.
이 경우 새 노드가 리스트의 첫 번째이자 마지막 노드가 되므로, head를 새 노드로 직접 설정합니다. 이것이 가장 간단한 케이스입니다.
리스트에 이미 노드가 있다면, 마지막 노드를 찾아야 합니다. current 변수를 head부터 시작해서, while 루프로 next가 null인 노드를 찾을 때까지 계속 이동합니다.
current.next가 null이라는 것은 current가 현재 마지막 노드라는 의미입니다. 그 노드의 next를 새 노드로 설정하면 연결이 완성됩니다.
마지막으로, this.size++로 리스트의 크기를 1 증가시킵니다. 이렇게 하면 나중에 getSize() 같은 메서드를 호출할 때 O(1) 시간에 크기를 반환할 수 있습니다.
return this를 사용하면 list.append(1).append(2).append(3) 같은 메서드 체이닝이 가능해져서 코드가 더 간결해집니다. 여러분이 이 메서드를 사용하면 데이터를 순차적으로 쌓아가는 작업을 안전하게 처리할 수 있습니다.
빈 리스트든 큰 리스트든 일관되게 작동하며, 리스트의 무결성이 항상 유지됩니다. 다만 시간 복잡도가 O(n)이라는 점을 알아두세요.
마지막 노드를 찾기 위해 전체 리스트를 순회해야 하기 때문입니다.
실전 팁
💡 tail 포인터를 추가로 유지하면 append 연산을 O(1) 시간에 처리할 수 있습니다. tail은 항상 마지막 노드를 가리키므로 순회가 불필요합니다.
💡 메서드 체이닝을 지원하려면 항상 this를 반환하세요. 이렇게 하면 여러 연산을 한 줄로 연결할 수 있어 코드가 깔끔해집니다.
💡 null 체크를 빠뜨리면 런타임 에러가 발생할 수 있습니다. 특히 빈 리스트 케이스를 항상 먼저 처리하는 습관을 들이세요.
💡 대량의 데이터를 추가할 때는 append보다 배열로 모아서 한 번에 처리하는 것이 더 효율적일 수 있습니다. 반복적인 순회를 줄일 수 있기 때문입니다.
💡 테스트 시에는 빈 리스트, 노드 1개, 노드 여러 개인 경우를 모두 확인하세요. 엣지 케이스를 놓치기 쉬운 메서드입니다.
3. 리스트 앞에 노드 추가하기 - prepend 메서드 구현
시작하며
여러분이 뉴스 피드 애플리케이션을 개발하고 있다고 생각해보세요. 가장 최신 뉴스가 항상 맨 위에 표시되어야 합니다.
새 기사가 들어올 때마다 리스트의 맨 앞에 추가해야 하는 것이죠. 이런 요구사항은 실무에서 매우 흔합니다.
스택(Stack) 자료구조를 구현하거나, 실행 취소 기능을 만들거나, 최근 검색 기록을 관리할 때 모두 앞에 데이터를 추가하는 연산이 필요합니다. 배열에서는 unshift를 사용하지만, 이 연산은 모든 요소를 한 칸씩 뒤로 밀어야 해서 O(n) 시간이 걸립니다.
바로 이럴 때 연결 리스트의 prepend가 진가를 발휘합니다. 단순히 head 포인터만 바꾸면 되므로 O(1) 시간에 처리됩니다.
이것이 연결 리스트가 배열보다 뛰어난 대표적인 상황입니다.
개요
간단히 말해서, prepend 메서드는 새로운 노드를 생성하여 리스트의 맨 앞에 추가하는 기능입니다. 이 메서드가 중요한 이유는 상수 시간에 삽입이 가능하다는 점입니다.
리스트의 크기와 상관없이 항상 같은 시간이 걸립니다. 실무에서는 최근 활동 로그, 브라우저의 뒤로 가기 스택, 게임의 상태 저장 등에서 자주 사용됩니다.
예를 들어, 텍스트 에디터에서 사용자의 모든 입력 행동을 앞에서부터 쌓아가면, 최근 행동부터 차례로 실행 취소할 수 있습니다. 배열의 unshift는 내부적으로 모든 요소를 이동시켜야 하지만, 연결 리스트의 prepend는 그럴 필요가 없습니다.
기존에는 데이터 이동으로 인한 성능 저하가 있었다면, 이제는 단순히 포인터 두 개만 조정하면 됩니다. 이 메서드의 핵심 특징은 첫째, 항상 O(1) 시간 복잡도를 보장한다는 점입니다.
둘째, 기존 head를 새 노드의 next로 연결합니다. 셋째, 새 노드를 새로운 head로 만듭니다.
이 세 단계만 거치면 삽입이 완료되므로 매우 효율적입니다.
코드 예제
// 리스트 앞에 새로운 노드를 추가하는 메서드
prepend(data) {
const newNode = new Node(data); // 새 노드 생성
// 핵심: 새 노드의 next를 현재 head로 설정
newNode.next = this.head; // 기존 리스트를 새 노드 뒤에 연결
// head를 새 노드로 업데이트
this.head = newNode; // 새 노드가 리스트의 새로운 시작점
this.size++; // 리스트 크기 증가
return this; // 메서드 체이닝 지원
}
설명
이것이 하는 일: prepend 메서드는 새 노드를 만들고, 그 노드를 현재 리스트의 맨 앞에 배치하여 새로운 head로 만듭니다. 기존 리스트는 새 노드의 뒤에 그대로 연결됩니다.
첫 번째로, 새로운 Node 객체를 생성합니다. 이 시점에서 newNode.next는 null입니다.
하지만 우리는 이 노드를 리스트의 앞에 추가할 것이므로, 이 노드의 next가 현재 리스트의 첫 번째 노드를 가리켜야 합니다. 그 다음으로, newNode.next = this.head라는 핵심 코드가 실행됩니다.
현재 head가 null이면(빈 리스트) newNode.next도 null이 되고, head가 어떤 노드를 가리키고 있다면 newNode.next가 그 노드를 가리키게 됩니다. 이렇게 하면 새 노드 뒤에 기존 리스트가 연결되는 구조가 만들어집니다.
마지막으로, this.head = newNode로 head를 업데이트합니다. 이제 head가 새 노드를 가리키므로, 리스트를 순회할 때 이 새 노드부터 시작하게 됩니다.
이 두 줄의 코드만으로 삽입이 완료되며, 리스트의 크기와 무관하게 항상 일정한 시간이 걸립니다. 여러분이 이 메서드를 사용하면 리스트의 크기가 아무리 커도 앞에 데이터를 추가하는 작업이 즉시 완료됩니다.
append가 O(n) 시간이 걸리는 것과 대조적으로, prepend는 O(1) 시간에 처리되므로 성능이 중요한 상황에서 매우 유용합니다. 특히 스택이나 큐를 구현할 때, 또는 최근 데이터부터 처리해야 하는 시스템에서 큰 이점을 제공합니다.
실전 팁
💡 prepend는 append보다 훨씬 빠르므로, 순서가 중요하지 않다면 prepend를 사용하는 것이 좋습니다. 나중에 reverse 메서드로 순서를 바꿀 수도 있습니다.
💡 스택(Stack)을 구현할 때는 prepend를 push로, 첫 번째 노드 삭제를 pop으로 사용하면 모든 연산이 O(1)입니다.
💡 빈 리스트에 prepend하는 경우를 별도로 처리할 필요가 없습니다. newNode.next = this.head가 자동으로 null을 설정하기 때문입니다.
💡 head 포인터를 잃어버리지 않도록 주의하세요. this.head = newNode보다 먼저 newNode.next = this.head를 실행해야 합니다. 순서가 바뀌면 기존 리스트를 잃어버립니다.
💡 실무에서는 prepend와 removeFirst를 조합하여 LRU(Least Recently Used) 캐시의 기본 동작을 구현할 수 있습니다.
4. 특정 위치에 노드 삽입하기 - insertAt 메서드 구현
시작하며
여러분이 플레이리스트 편집 기능을 만들고 있다고 상상해보세요. 사용자가 "3번째 곡과 4번째 곡 사이에 이 곡을 넣고 싶어요"라고 요청합니다.
단순히 앞이나 뒤에 추가하는 것이 아니라, 정확히 원하는 위치에 삽입해야 하는 상황입니다. 이런 요구사항은 실제 애플리케이션에서 자주 발생합니다.
정렬된 리스트를 유지하면서 새 데이터를 적절한 위치에 넣거나, 사용자가 직접 지정한 위치에 항목을 삽입하는 기능이 필요합니다. 배열에서는 splice를 사용하지만, 이는 삽입 위치 이후의 모든 요소를 이동시켜야 합니다.
바로 이럴 때 연결 리스트의 insertAt이 효율적입니다. 삽입 위치까지만 이동해서 포인터 몇 개만 조정하면 되므로, 대량의 데이터 이동 없이 삽입을 완료할 수 있습니다.
개요
간단히 말해서, insertAt 메서드는 지정된 인덱스 위치에 새로운 노드를 삽입하는 기능입니다. 이 메서드가 실무에서 중요한 이유는 유연한 데이터 삽입이 가능하기 때문입니다.
정렬 순서를 유지하면서 데이터를 추가하거나, 우선순위 큐에서 특정 우선순위 위치에 작업을 넣거나, 게임에서 캐릭터를 특정 순위에 배치하는 등의 작업에 사용됩니다. 예를 들어, 이메일 클라이언트에서 중요한 메일을 특정 위치에 고정하는 기능을 구현할 때 매우 유용합니다.
배열의 splice는 삽입 위치부터 끝까지 모든 요소의 인덱스를 변경해야 하지만, 연결 리스트는 그럴 필요가 없습니다. 기존에는 최악의 경우 O(n) 시간의 데이터 이동이 필요했다면, 이제는 삽입 위치를 찾는 O(n) 시간만 필요하고 실제 삽입은 O(1)입니다.
이 메서드의 핵심 특징은 첫째, 인덱스 유효성을 검증해야 한다는 점입니다. 둘째, 이전 노드를 찾아서 그 노드와 다음 노드 사이에 새 노드를 끼워 넣습니다.
셋째, 인덱스 0이면 prepend와 동일하게 처리합니다. 이러한 세심한 처리가 리스트의 무결성을 보장합니다.
코드 예제
// 특정 인덱스에 노드를 삽입하는 메서드
insertAt(index, data) {
// 인덱스 유효성 검사
if (index < 0 || index > this.size) {
throw new Error('Index out of bounds');
}
// 맨 앞에 삽입하는 경우 prepend 사용
if (index === 0) {
return this.prepend(data);
}
const newNode = new Node(data);
let current = this.head;
let previous = null;
let count = 0;
// 삽입 위치의 이전 노드 찾기
while (count < index) {
previous = current;
current = current.next;
count++;
}
// 새 노드를 이전 노드와 현재 노드 사이에 삽입
newNode.next = current; // 새 노드가 현재 노드를 가리킴
previous.next = newNode; // 이전 노드가 새 노드를 가리킨
this.size++;
return this;
}
설명
이것이 하는 일: insertAt 메서드는 사용자가 지정한 인덱스까지 리스트를 순회하여, 그 위치에 새 노드를 기존 노드들 사이에 삽입합니다. 첫 번째로, 인덱스 유효성을 검사합니다.
index가 0보다 작거나 현재 리스트 크기보다 크면 에러를 발생시킵니다. 이 검증이 중요한 이유는, 잘못된 인덱스로 삽입을 시도하면 리스트가 손상되거나 무한 루프에 빠질 수 있기 때문입니다.
index === this.size인 경우는 허용되는데, 이는 리스트 끝에 추가하는 것과 같기 때문입니다. 그 다음으로, 특별한 경우를 처리합니다.
index가 0이면 리스트의 맨 앞에 삽입하는 것이므로, 이미 구현한 prepend 메서드를 재사용합니다. 이렇게 하면 코드 중복을 피하고 일관성을 유지할 수 있습니다.
일반적인 경우에는 삽입 위치를 찾아야 합니다. current를 head부터 시작해서, while 루프로 index 위치까지 이동합니다.
중요한 점은 previous 변수로 이전 노드를 계속 추적한다는 것입니다. 왜냐하면 우리는 previous와 current 사이에 새 노드를 삽입해야 하기 때문입니다.
마지막으로, 실제 삽입이 일어납니다. newNode.next = current로 새 노드가 현재 위치의 노드를 가리키게 하고, previous.next = newNode로 이전 노드가 새 노드를 가리키게 합니다.
이 두 줄의 순서가 중요합니다. 순서를 바꾸면 current 노드에 대한 참조를 잃어버릴 수 있습니다.
여러분이 이 메서드를 사용하면 리스트의 어느 위치에든 데이터를 안전하게 삽입할 수 있습니다. 배열처럼 대량의 데이터를 이동시킬 필요가 없어서, 큰 리스트에서도 효율적으로 작동합니다.
다만 삽입 위치를 찾기 위해 순회가 필요하므로, 인덱스가 클수록 시간이 더 걸린다는 점을 기억하세요.
실전 팁
💡 인덱스 유효성 검사를 빼먹으면 안 됩니다. 잘못된 인덱스는 리스트를 손상시킬 수 있으므로, 항상 검증 로직을 먼저 실행하세요.
💡 이전 노드를 추적하는 것이 핵심입니다. previous 없이는 삽입 위치 앞의 노드를 조작할 수 없습니다.
💡 포인터 업데이트 순서가 매우 중요합니다. newNode.next를 먼저 설정하고, 그 다음에 previous.next를 설정해야 노드를 잃어버리지 않습니다.
💡 정렬된 리스트에 삽입할 때는 insertAt 대신 삽입 위치를 찾는 전용 메서드를 만드는 것이 더 효율적입니다. 값을 비교하면서 동시에 삽입 위치를 찾을 수 있기 때문입니다.
💡 테스트 시에는 인덱스 0, 중간, 끝, 범위 밖 등 다양한 케이스를 확인하세요. 특히 빈 리스트와 노드 1개인 리스트는 엣지 케이스입니다.
5. 특정 값을 가진 노드 삭제하기 - remove 메서드 구현
시작하며
여러분이 장바구니 기능을 구현하고 있다고 생각해보세요. 사용자가 "이 상품을 장바구니에서 빼주세요"라고 요청합니다.
상품의 위치가 아니라 상품 자체를 지정하는 것이죠. 리스트에서 특정 값을 찾아 삭제해야 하는 상황입니다.
이런 삭제 연산은 데이터를 관리하는 모든 시스템에서 필수적입니다. 사용자 목록에서 탈퇴한 사용자를 제거하거나, 작업 큐에서 취소된 작업을 삭제하거나, 캐시에서 만료된 항목을 제거하는 등 다양한 상황에서 사용됩니다.
배열에서는 filter나 splice를 사용하지만, 이는 삭제 후 빈 공간을 채우기 위해 요소들을 이동시켜야 합니다. 바로 이럴 때 연결 리스트의 remove가 효율적입니다.
삭제할 노드를 찾으면, 그 노드를 건너뛰도록 포인터만 조정하면 됩니다. 메모리 이동 없이 논리적으로만 제거하는 것이죠.
개요
간단히 말해서, remove 메서드는 지정된 값을 가진 첫 번째 노드를 리스트에서 제거하는 기능입니다. 이 메서드가 실무에서 중요한 이유는 값 기반 삭제가 매우 자연스러운 작업이기 때문입니다.
사용자는 보통 "3번째 항목을 삭제해줘"가 아니라 "이 항목을 삭제해줘"라고 말합니다. 소셜 미디어에서 특정 게시물을 삭제하거나, 음악 플레이어에서 특정 곡을 제거하거나, 연락처에서 특정 사람을 삭제하는 경우에 모두 값 기반 삭제를 사용합니다.
예를 들어, 채팅 앱에서 특정 메시지를 삭제할 때 메시지 ID로 찾아서 제거하는 것이 일반적입니다. 배열에서 값을 찾아 삭제하려면 indexOf로 위치를 찾고 splice로 삭제해야 하는데, 이는 두 번의 순회가 필요합니다.
기존에는 찾기와 삭제를 분리해서 처리했다면, 연결 리스트에서는 한 번의 순회로 찾으면서 동시에 삭제할 수 있습니다. 이 메서드의 핵심 특징은 첫째, 값을 비교하면서 순회한다는 점입니다.
둘째, 이전 노드의 next를 삭제할 노드의 next로 연결하여 노드를 건너뜁니다. 셋째, head를 삭제하는 경우를 별도로 처리합니다.
이러한 세심한 처리가 리스트의 연결 상태를 안전하게 유지합니다.
코드 예제
// 특정 값을 가진 첫 번째 노드를 삭제하는 메서드
remove(data) {
if (this.head === null) {
return null; // 빈 리스트면 삭제할 것이 없음
}
// 케이스 1: head가 삭제 대상인 경우
if (this.head.data === data) {
this.head = this.head.next; // head를 다음 노드로 이동
this.size--;
return data;
}
// 케이스 2: 일반 노드를 삭제하는 경우
let current = this.head;
let previous = null;
while (current !== null) {
if (current.data === data) {
// 삭제 대상을 찾음 - 이전 노드와 다음 노드를 직접 연결
previous.next = current.next;
this.size--;
return data;
}
previous = current;
current = current.next;
}
return null; // 값을 찾지 못한 경우
}
설명
이것이 하는 일: remove 메서드는 리스트를 순회하면서 지정된 값과 일치하는 노드를 찾고, 그 노드를 리스트의 연결에서 제거합니다. 첫 번째로, 빈 리스트인지 확인합니다.
this.head === null이면 삭제할 노드가 없으므로 null을 반환합니다. 이 검증이 없으면 뒤의 코드에서 null.data를 참조하려다 에러가 발생할 수 있습니다.
그 다음으로, 특별한 경우를 처리합니다. head 노드가 삭제 대상이라면, 단순히 head를 head.next로 변경하면 됩니다.
이렇게 하면 기존 head는 리스트에서 분리되고, 두 번째 노드가 새로운 head가 됩니다. 만약 리스트에 노드가 하나뿐이었다면, head.next는 null이므로 head도 null이 되어 빈 리스트가 됩니다.
일반적인 경우에는 리스트를 순회하면서 값을 찾습니다. current를 head부터 시작해서, while 루프로 각 노드의 data를 비교합니다.
중요한 점은 previous로 이전 노드를 추적한다는 것입니다. 삭제 대상을 찾으면, previous.next = current.next로 이전 노드가 삭제 대상의 다음 노드를 직접 가리키게 합니다.
이렇게 하면 current 노드가 리스트의 연결에서 제외됩니다. 마지막으로, 자바스크립트의 가비지 컬렉터가 자동으로 제외된 노드의 메모리를 회수합니다.
우리는 명시적으로 메모리를 해제할 필요가 없습니다. 리스트에서 참조가 끊어진 노드는 자동으로 정리되므로 메모리 누수 걱정이 없습니다.
여러분이 이 메서드를 사용하면 값을 기준으로 데이터를 안전하게 삭제할 수 있습니다. 배열처럼 인덱스를 먼저 찾을 필요가 없어서 코드가 더 직관적입니다.
다만 이 메서드는 일치하는 첫 번째 노드만 삭제한다는 점을 기억하세요. 모든 일치하는 노드를 삭제하려면 별도의 메서드가 필요합니다.
실전 팁
💡 head 삭제 케이스를 먼저 처리하지 않으면, previous가 null인 상태에서 previous.next를 참조하려다 에러가 발생합니다.
💡 값을 찾지 못한 경우를 명확히 처리하세요. null을 반환하거나 false를 반환하여 호출자가 결과를 확인할 수 있게 합니다.
💡 삭제된 노드의 next를 명시적으로 null로 설정하면 디버깅 시 도움이 됩니다. current.next = null처럼 정리하는 것이 좋은 습관입니다.
💡 모든 일치 항목을 삭제하려면 루프를 계속 진행하도록 수정하세요. return 대신 continue를 사용하면 됩니다.
💡 삭제 전에 리스트 크기를 확인하여, 삭제 후 빈 리스트가 되는지 미리 알 수 있습니다. 이는 tail 포인터를 관리할 때 특히 중요합니다.
6. 리스트 순회와 출력하기 - print와 toArray 메서드 구현
시작하며
여러분이 리스트 구현을 마치고 나서 "이게 제대로 작동하나?"를 확인하고 싶을 때가 있습니다. 콘솔에 리스트의 내용을 출력하거나, 다른 함수에 배열 형태로 전달해야 하는 상황이죠.
디버깅할 때나 테스트할 때 리스트의 현재 상태를 쉽게 확인하는 것이 얼마나 중요한지 아실 겁니다. 연결 리스트는 배열처럼 console.log로 간단히 출력되지 않습니다.
노드들이 next 포인터로 연결되어 있기 때문에, 그냥 출력하면 복잡한 객체 구조만 보입니다. 또한 많은 라이브러리나 함수들이 배열을 입력으로 기대하므로, 연결 리스트를 배열로 변환할 필요가 있습니다.
바로 이럴 때 순회 메서드들이 필요합니다. 리스트의 모든 노드를 방문하면서 데이터를 수집하거나 출력하는 기능을 제공합니다.
개요
간단히 말해서, print 메서드는 리스트의 모든 값을 읽기 쉬운 형태로 출력하고, toArray 메서드는 리스트를 배열로 변환하는 기능입니다. 이 메서드들이 실무에서 중요한 이유는 디버깅과 상호 운용성 때문입니다.
개발 중에 리스트의 상태를 빠르게 확인하거나, 리스트 데이터를 다른 함수나 API에 전달해야 하는 경우가 많습니다. 로그 시스템에서 현재 저장된 로그들을 확인하거나, 테스트에서 리스트의 내용을 검증하거나, 프론트엔드에서 리스트 데이터를 화면에 표시하는 경우에 모두 유용합니다.
예를 들어, React에서 연결 리스트의 데이터를 map으로 렌더링하려면 먼저 배열로 변환해야 합니다. 직접 노드를 순회하는 것보다 전용 메서드를 사용하면 코드가 훨씬 깔끔해집니다.
기존에는 매번 while 루프를 작성해서 순회했다면, 이제는 toArray()를 한 번 호출하면 모든 데이터를 배열로 얻을 수 있습니다. 이 메서드들의 핵심 특징은 첫째, 리스트를 변경하지 않는다는 점입니다(읽기 전용).
둘째, head부터 시작해서 next를 따라가며 모든 노드를 방문합니다. 셋째, 순회 패턴을 재사용 가능한 형태로 캡슐화합니다.
이러한 특징이 안전하고 편리한 데이터 접근을 가능하게 합니다.
코드 예제
// 리스트의 모든 값을 문자열로 출력하는 메서드
print() {
if (this.head === null) {
console.log('List is empty');
return;
}
let current = this.head;
let output = '';
while (current !== null) {
output += current.data;
if (current.next !== null) {
output += ' -> '; // 노드 사이를 화살표로 연결
}
current = current.next;
}
console.log(output);
}
// 리스트를 배열로 변환하는 메서드
toArray() {
const result = [];
let current = this.head;
while (current !== null) {
result.push(current.data); // 각 노드의 데이터를 배열에 추가
current = current.next;
}
return result;
}
설명
이것이 하는 일: print와 toArray 메서드는 리스트의 모든 노드를 순차적으로 방문하면서, 각 노드의 데이터를 수집하거나 출력합니다. 첫 번째로, print 메서드는 빈 리스트를 확인합니다.
head가 null이면 "List is empty"를 출력하고 종료합니다. 이렇게 하면 빈 리스트를 시각적으로 명확하게 표현할 수 있습니다.
그 다음으로, current를 head로 초기화하고 while 루프를 시작합니다. 각 반복에서 current.data를 output 문자열에 추가합니다.
중요한 부분은 current.next가 null이 아닐 때만 " -> "를 추가한다는 것입니다. 이렇게 하면 마지막 노드 뒤에 불필요한 화살표가 붙지 않습니다.
예를 들어 "1 -> 2 -> 3"처럼 깔끔하게 출력됩니다. toArray 메서드는 비슷한 패턴을 사용하지만, 문자열 대신 배열에 데이터를 수집합니다.
result 배열을 만들고, 순회하면서 각 노드의 data를 push합니다. current = current.next로 다음 노드로 이동하며, current가 null이 되면(리스트의 끝) 루프가 종료됩니다.
마지막으로, toArray는 수집한 배열을 반환합니다. 이 배열은 리스트와 완전히 독립적이므로, 배열을 수정해도 원본 리스트에는 영향을 주지 않습니다.
이것이 중요한 이유는, 호출자가 안전하게 배열을 조작할 수 있기 때문입니다. 여러분이 이 메서드들을 사용하면 리스트의 내용을 쉽게 확인하고, 다른 코드와 통합할 수 있습니다.
print는 개발 중 빠른 디버깅에 유용하고, toArray는 리스트 데이터를 배열 기반 API나 함수에 전달할 때 필수적입니다. 순회 패턴이 메서드로 캡슐화되어 있어서, 매번 while 루프를 작성할 필요가 없습니다.
실전 팁
💡 print 메서드에 구분자를 매개변수로 받도록 개선하면 더 유연합니다. print(', ')처럼 호출하면 쉼표로 구분된 출력을 얻을 수 있습니다.
💡 toArray는 순회 로직을 재사용하는 좋은 예입니다. 다른 메서드들도 toArray()를 호출해서 배열 메서드를 활용할 수 있습니다.
💡 큰 리스트를 출력할 때는 최대 노드 수를 제한하는 것이 좋습니다. 예를 들어 처음 10개만 출력하고 "... and 50 more"처럼 표시하세요.
💡 forEach 메서드를 추가로 구현하면 사용자가 각 노드에 대해 커스텀 로직을 실행할 수 있습니다. list.forEach(data => console.log(data)) 같은 형태로 사용 가능합니다.
💡 개발 환경에서만 print를 사용하고, 프로덕션 코드에서는 제거하거나 로깅 레벨을 조정하세요. 불필요한 출력이 성능에 영향을 줄 수 있습니다.
7. 특정 값 검색하기 - find와 indexOf 메서드 구현
시작하며
여러분이 친구 목록에서 특정 친구를 찾거나, 작업 큐에서 특정 작업의 위치를 확인하고 싶을 때가 있습니다. "이 데이터가 리스트에 있나요?" 또는 "몇 번째 위치에 있나요?"라는 질문에 답해야 하는 상황이죠.
검색은 거의 모든 데이터 구조에서 가장 기본적이면서도 중요한 연산입니다. 사용자 인증 시스템에서 특정 사용자를 찾거나, 전자상거래에서 특정 상품이 장바구니에 있는지 확인하거나, 게임에서 특정 아이템을 소유하고 있는지 검증하는 경우에 모두 검색 연산이 필요합니다.
바로 이럴 때 find와 indexOf 메서드가 필요합니다. 하나는 값의 존재 여부를 확인하고, 다른 하나는 값의 위치를 찾습니다.
이 두 메서드로 리스트의 데이터를 효율적으로 탐색할 수 있습니다.
개요
간단히 말해서, find 메서드는 지정된 값을 가진 노드를 찾아 반환하고, indexOf 메서드는 그 값의 인덱스 위치를 반환하는 기능입니다. 이 메서드들이 실무에서 중요한 이유는 데이터 접근과 검증이 매우 빈번하기 때문입니다.
권한 시스템에서 사용자가 특정 권한을 가지고 있는지 확인하거나, 캐시에서 특정 키의 데이터를 찾거나, 중복 체크를 위해 값이 이미 존재하는지 검사하는 경우에 사용됩니다. 예를 들어, 소셜 미디어에서 이미 팔로우한 사용자인지 확인할 때, 팔로우 목록에서 해당 사용자를 검색하는 것이 일반적입니다.
배열의 includes나 indexOf는 내부적으로 순차 검색을 하므로, 연결 리스트와 시간 복잡도가 동일합니다. 기존에는 배열 메서드에 의존했다면, 이제는 연결 리스트에서도 동일한 검색 기능을 직접 구현하여 사용할 수 있습니다.
이 메서드들의 핵심 특징은 첫째, 순차 검색을 수행하므로 O(n) 시간이 걸린다는 점입니다. 둘째, 일치하는 첫 번째 값만 찾습니다.
셋째, 값을 찾지 못하면 명확한 신호(null 또는 -1)를 반환합니다. 이러한 특징이 검색 결과를 명확하게 처리할 수 있게 합니다.
코드 예제
// 특정 값을 가진 노드를 찾는 메서드
find(data) {
let current = this.head;
while (current !== null) {
if (current.data === data) {
return current; // 찾은 노드 반환
}
current = current.next;
}
return null; // 값을 찾지 못한 경우
}
// 특정 값의 인덱스를 찾는 메서드
indexOf(data) {
let current = this.head;
let index = 0;
while (current !== null) {
if (current.data === data) {
return index; // 찾은 위치의 인덱스 반환
}
current = current.next;
index++;
}
return -1; // 값을 찾지 못한 경우 -1 반환 (배열 컨벤션)
}
설명
이것이 하는 일: find와 indexOf 메서드는 리스트를 처음부터 끝까지 순회하면서, 각 노드의 데이터를 찾고자 하는 값과 비교하여 일치하는 것을 찾습니다. 첫 번째로, find 메서드는 current를 head로 초기화하고 순회를 시작합니다.
while 루프의 각 반복에서 current.data를 찾고자 하는 값과 비교합니다. 이 비교는 === 연산자를 사용하므로, 값과 타입이 모두 일치해야 합니다.
예를 들어 숫자 5와 문자열 "5"는 다른 값으로 취급됩니다. 일치하는 노드를 찾으면 즉시 그 노드를 반환하고 메서드를 종료합니다.
이것이 중요한 이유는, 리스트에 같은 값이 여러 개 있어도 첫 번째만 반환한다는 의미이기 때문입니다. 만약 리스트를 끝까지 순회했는데도 값을 찾지 못하면, current가 null이 되어 루프가 종료되고 null을 반환합니다.
그 다음으로, indexOf 메서드는 비슷한 패턴을 사용하지만 추가로 index 변수를 추적합니다. 각 노드를 확인할 때마다 index를 1씩 증가시킵니다.
값을 찾으면 현재 index를 반환하고, 찾지 못하면 -1을 반환합니다. -1을 사용하는 이유는 자바스크립트 배열의 indexOf와 동일한 컨벤션을 따르기 위해서입니다.
마지막으로, 호출자는 반환값을 검사하여 검색 성공 여부를 판단할 수 있습니다. find의 경우 if (node !== null)로, indexOf의 경우 if (index !== -1)로 체크하면 됩니다.
이러한 명확한 반환값이 에러 처리를 쉽게 만듭니다. 여러분이 이 메서드들을 사용하면 리스트에서 데이터를 안전하게 검색하고, 그 결과를 명확하게 처리할 수 있습니다.
두 메서드 모두 O(n) 시간이 걸리지만, 평균적으로는 리스트의 절반만 검색하면 됩니다. 검색 성능이 중요하다면, 정렬된 리스트나 해시 테이블 같은 다른 자료구조를 고려해보세요.
실전 팁
💡 객체를 비교할 때는 참조 비교가 되므로, 깊은 비교가 필요하면 커스텀 비교 함수를 매개변수로 받도록 개선하세요.
💡 findAll 메서드를 추가하면 모든 일치하는 노드를 배열로 반환할 수 있습니다. 중복 값을 모두 찾아야 할 때 유용합니다.
💡 lastIndexOf를 구현하려면 리스트를 끝까지 순회하면서 마지막으로 일치한 인덱스를 기억하면 됩니다.
💡 대소문자 구분 없이 문자열을 검색하려면, 비교 전에 toLowerCase()를 적용하세요. data.toLowerCase() === searchValue.toLowerCase() 형태로 사용합니다.
💡 성능이 중요한 경우, 자주 검색하는 값들을 Map이나 Set에 캐싱하여 O(1) 검색을 구현할 수 있습니다.
8. 리스트 역순 정렬하기 - reverse 메서드 구현
시작하며
여러분이 채팅 앱에서 메시지 순서를 바꾸고 싶다고 생각해보세요. 처음에는 오래된 메시지부터 표시했는데, 사용자가 "최신 메시지를 먼저 보여주세요"라고 요청합니다.
전체 데이터의 순서를 뒤집어야 하는 상황이죠. 리스트를 역순으로 만드는 것은 많은 알고리즘과 애플리케이션에서 필요합니다.
스택을 큐로 변환하거나, 경로를 역추적하거나, 애니메이션을 거꾸로 재생하는 경우에 사용됩니다. 배열에서는 reverse() 메서드가 있지만, 이는 내부적으로 많은 요소 교환이 발생합니다.
바로 이럴 때 연결 리스트의 reverse가 효율적입니다. 실제 데이터를 이동시키지 않고, 단순히 next 포인터의 방향만 바꾸면 됩니다.
메모리 복사 없이 논리적 순서만 변경하는 것이죠.
개요
간단히 말해서, reverse 메서드는 리스트의 노드 순서를 역순으로 바꾸는 기능입니다. 이 메서드가 실무에서 중요한 이유는 데이터의 표현 순서를 바꾸는 작업이 자주 발생하기 때문입니다.
게시판에서 정렬 순서를 바꾸거나, 이력서에서 경력을 최신순으로 정렬하거나, 음악 플레이리스트를 거꾸로 재생하는 경우에 사용됩니다. 예를 들어, Git 커밋 히스토리를 최신 커밋부터 표시하거나, 파일 시스템에서 경로를 역순으로 순회하는 경우에 매우 유용합니다.
배열의 reverse는 요소를 직접 교환하므로 추가 공간이 필요하지 않지만, 교환 연산이 많이 발생합니다. 연결 리스트에서는 요소를 이동시키지 않고 포인터만 조정합니다.
기존에는 데이터를 복사해서 역순으로 삽입했다면, 이제는 제자리에서(in-place) 포인터만 바꾸면 됩니다. 이 메서드의 핵심 특징은 첫째, 제자리 역순 정렬로 추가 메모리를 거의 사용하지 않는다는 점입니다.
둘째, 각 노드의 next를 이전 노드로 바꿉니다. 셋째, 기존 head가 tail이 되고, 기존 tail이 head가 됩니다.
이러한 포인터 조작이 효율적인 역순 정렬을 가능하게 합니다.
코드 예제
// 리스트의 순서를 역순으로 바꾸는 메서드
reverse() {
if (this.head === null || this.head.next === null) {
return this; // 빈 리스트나 노드 1개면 변경 불필요
}
let previous = null; // 이전 노드 (처음에는 null)
let current = this.head; // 현재 노드
let next = null; // 다음 노드를 임시 저장
while (current !== null) {
// 1. 다음 노드를 임시 저장 (연결을 잃어버리지 않기 위해)
next = current.next;
// 2. 현재 노드의 next를 이전 노드로 변경 (방향 반전)
current.next = previous;
// 3. 포인터들을 한 칸씩 앞으로 이동
previous = current;
current = next;
}
// 4. previous가 새로운 head (마지막 노드였던 것)
this.head = previous;
return this;
}
설명
이것이 하는 일: reverse 메서드는 리스트를 순회하면서 각 노드의 next 포인터가 다음 노드 대신 이전 노드를 가리키도록 변경하여, 전체 연결 방향을 반대로 만듭니다. 첫 번째로, 엣지 케이스를 처리합니다.
리스트가 비어있거나 노드가 하나만 있으면, 역순으로 만들어도 결과가 같으므로 그냥 반환합니다. 이 체크가 없어도 알고리즘은 작동하지만, 불필요한 연산을 피할 수 있습니다.
그 다음으로, 세 개의 포인터를 초기화합니다. previous는 null로 시작하는데, 이는 역순 후 기존 head의 next가 null이 되어야 하기 때문입니다.
current는 head부터 시작하여 각 노드를 순회합니다. next는 임시 저장 공간으로, current.next를 바꾸기 전에 다음 노드의 위치를 기억하는 역할을 합니다.
while 루프의 각 반복은 세 단계로 이루어집니다. 첫째, next = current.next로 다음 노드를 저장합니다.
이것이 매우 중요한 이유는, 다음 줄에서 current.next를 변경하면 원래 다음 노드로 가는 연결이 끊어지기 때문입니다. 둘째, current.next = previous로 포인터 방향을 반전시킵니다.
이제 current 노드가 다음이 아닌 이전을 가리킵니다. 셋째, previous와 current를 한 칸씩 앞으로 이동시킵니다.
마지막으로, 루프가 끝나면 current는 null이고, previous는 원래 리스트의 마지막 노드를 가리킵니다. 이 노드가 역순 리스트의 새로운 head가 되므로, this.head = previous로 업데이트합니다.
이제 리스트는 완전히 역순이 되었습니다. 여러분이 이 메서드를 사용하면 대용량 리스트도 효율적으로 역순 정렬할 수 있습니다.
추가 메모리를 거의 사용하지 않으며(O(1) 공간), 각 노드를 정확히 한 번씩만 방문하므로 O(n) 시간에 완료됩니다. 이 알고리즘은 포인터 조작의 교과서적인 예시로, 연결 리스트 면접 문제에서도 자주 출제됩니다.
실전 팁
💡 포인터 세 개(previous, current, next)를 동시에 추적하는 것이 핵심입니다. 종이에 그림을 그려가며 각 단계를 시각화하면 이해가 쉽습니다.
💡 next를 저장하지 않고 current.next를 바로 바꾸면 나머지 리스트로 가는 연결을 잃어버립니다. 순서가 매우 중요합니다.
💡 재귀로도 구현할 수 있지만, 큰 리스트에서는 스택 오버플로우 위험이 있으므로 반복문이 더 안전합니다.
💡 tail 포인터를 유지하는 경우, reverse 후에 기존 head를 tail로, 기존 tail을 head로 교환해야 합니다.
💡 디버깅 시 각 반복 후 print를 호출하여 포인터 변경을 확인하면 도움이 됩니다. 하지만 프로덕션 코드에서는 제거하세요.
9. 리스트 크기와 빈 상태 확인하기 - getSize와 isEmpty 메서드
시작하며
여러분이 작업 큐 시스템을 만들고 있다고 생각해보세요. "처리할 작업이 남아있나요?" 또는 "현재 몇 개의 작업이 대기 중인가요?"라는 질문에 빠르게 답해야 합니다.
이런 정보는 시스템 모니터링, 조건 분기, 사용자 인터페이스 업데이트 등에서 필수적입니다. 리스트의 상태를 확인하는 것은 거의 모든 작업의 전제 조건입니다.
빈 리스트에서 삭제를 시도하면 에러가 발생하고, 크기를 알아야 페이지네이션을 구현할 수 있습니다. 배열에서는 length 프로퍼티로 즉시 알 수 있지만, 연결 리스트에서는 명시적으로 추적하지 않으면 매번 순회해야 합니다.
바로 이럴 때 getSize와 isEmpty 메서드가 필요합니다. 크기를 멤버 변수로 관리하면 O(1) 시간에 상태를 확인할 수 있습니다.
개요
간단히 말해서, getSize 메서드는 리스트에 있는 노드의 개수를 반환하고, isEmpty 메서드는 리스트가 비어있는지 확인하는 기능입니다. 이 메서드들이 실무에서 중요한 이유는 효율적인 상태 확인이 성능에 직접적인 영향을 미치기 때문입니다.
반복문의 조건, 에러 검증, UI 업데이트 등에서 자주 호출되므로 빠른 응답이 필요합니다. 웹 애플리케이션에서 장바구니의 상품 개수를 표시하거나, 게임에서 인벤토리 용량을 체크하거나, 메시지 큐에서 처리해야 할 메시지 수를 확인하는 경우에 사용됩니다.
예를 들어, 대시보드에서 실시간으로 대기 중인 작업 수를 표시할 때, getSize()를 매번 호출하므로 O(1) 성능이 필수입니다. 크기를 매번 순회하여 세는 것은 O(n) 시간이 걸려서 비효율적입니다.
size 변수를 유지하면 상수 시간에 크기를 알 수 있습니다. 기존에는 필요할 때마다 계산했다면, 이제는 삽입/삭제 시 size를 업데이트하여 항상 정확한 값을 가지고 있습니다.
이 메서드들의 핵심 특징은 첫째, O(1) 시간 복잡도를 보장한다는 점입니다. 둘째, 추가 순회 없이 즉시 결과를 반환합니다.
셋째, isEmpty는 head 체크 또는 size 체크로 구현할 수 있습니다. 이러한 효율성이 전체 시스템의 성능을 향상시킵니다.
코드 예제
// 리스트의 크기를 반환하는 메서드
getSize() {
return this.size; // O(1) 시간에 크기 반환
}
// 리스트가 비어있는지 확인하는 메서드
isEmpty() {
return this.head === null; // head가 null이면 빈 리스트
// 또는: return this.size === 0; 도 가능
}
// 리스트의 첫 번째 값을 반환하는 메서드 (보너스)
getFirst() {
if (this.isEmpty()) {
return null;
}
return this.head.data;
}
// 리스트의 마지막 값을 반환하는 메서드 (보너스)
getLast() {
if (this.isEmpty()) {
return null;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
return current.data;
}
설명
이것이 하는 일: getSize와 isEmpty 메서드는 리스트의 현재 상태를 나타내는 정보를 빠르게 반환합니다. 순회 없이 멤버 변수만 확인하므로 매우 효율적입니다.
첫 번째로, getSize 메서드는 단순히 this.size를 반환합니다. 우리는 노드를 추가하거나 삭제할 때마다 size를 업데이트했으므로, 이 값은 항상 정확합니다.
만약 size를 유지하지 않았다면, 리스트를 순회하면서 노드를 세어야 하므로 O(n) 시간이 걸립니다. size를 유지하는 대신 약간의 메모리(정수 하나)와 업데이트 로직이 필요하지만, 조회 성능이 크게 향상됩니다.
그 다음으로, isEmpty 메서드는 두 가지 방법으로 구현할 수 있습니다. this.head === null을 체크하는 방법은 head 포인터만 확인하므로 가장 직접적입니다.
this.size === 0을 체크하는 방법도 가능하며, 둘 다 O(1) 시간입니다. 일반적으로 head 체크가 더 명확하므로 선호됩니다.
추가로 구현한 getFirst 메서드는 빈 리스트 체크 후 head.data를 반환합니다. 이것도 O(1) 시간에 처리됩니다.
반면 getLast 메서드는 마지막 노드를 찾기 위해 전체 리스트를 순회해야 하므로 O(n) 시간이 걸립니다. 만약 tail 포인터를 유지한다면, getLast도 O(1) 시간에 처리할 수 있습니다.
마지막으로, 이 유틸리티 메서드들은 다른 메서드에서도 자주 사용됩니다. 예를 들어 remove 메서드 시작 부분에서 if (this.isEmpty()) return null처럼 사용하면 코드가 더 읽기 쉽고 안전해집니다.
또한 사용자 코드에서도 조건 분기나 유효성 검사에 활용할 수 있습니다. 여러분이 이 메서드들을 사용하면 리스트의 상태를 효율적으로 확인하고, 그에 따라 적절한 처리를 할 수 있습니다.
특히 isEmpty는 많은 연산의 전제 조건으로 사용되므로, 항상 먼저 체크하는 습관을 들이세요. 빈 리스트에서 잘못된 연산을 시도하면 런타임 에러가 발생할 수 있습니다.
실전 팁
💡 size를 유지하려면 모든 삽입/삭제 메서드에서 일관되게 업데이트해야 합니다. 하나라도 빼먹으면 size가 부정확해집니다.
💡 tail 포인터를 추가하면 append와 getLast도 O(1) 시간이 됩니다. 약간의 추가 메모리로 큰 성능 향상을 얻을 수 있습니다.
💡 isEmpty를 사용하면 코드 가독성이 높아집니다. if (list.head === null)보다 if (list.isEmpty())가 의도를 더 명확하게 표현합니다.
💡 getFirst와 getLast는 peek 연산으로도 불립니다. 스택이나 큐를 구현할 때 유용합니다.
💡 프로덕션 코드에서는 size와 실제 노드 개수가 일치하는지 검증하는 테스트를 추가하세요. 버그로 인한 불일치를 빠르게 발견할 수 있습니다.
10. 리스트 초기화하기 - clear 메서드 구현
시작하며
여러분이 게임의 스코어보드를 관리하고 있다고 생각해보세요. 새 게임이 시작되면 "모든 기록을 지우고 처음부터 다시 시작"해야 합니다.
또는 장바구니를 비우거나, 검색 히스토리를 초기화하거나, 임시 데이터를 정리해야 하는 상황이죠. 리스트의 모든 데이터를 삭제하는 것은 매우 흔한 작업입니다.
하나씩 노드를 삭제할 수도 있지만, 그것은 비효율적입니다. 세션이 종료될 때 사용자 데이터를 정리하거나, 캐시를 비우거나, 테스트 간에 상태를 리셋하는 경우에 전체 초기화가 필요합니다.
바로 이럴 때 clear 메서드가 필요합니다. 단순히 head를 null로 만들고 size를 0으로 리셋하면, 모든 노드가 한 번에 정리됩니다.
개요
간단히 말해서, clear 메서드는 리스트의 모든 노드를 제거하고 빈 상태로 초기화하는 기능입니다. 이 메서드가 실무에서 중요한 이유는 리소스 정리와 상태 관리 때문입니다.
메모리 누수를 방지하고, 테스트를 독립적으로 실행하고, 사용자 세션을 깔끔하게 종료하는 데 필요합니다. 웹 애플리케이션에서 로그아웃 시 사용자 데이터를 정리하거나, 게임에서 라운드가 끝날 때 임시 상태를 리셋하거나, 데이터베이스 트랜잭션을 롤백할 때 사용됩니다.
예를 들어, 채팅 앱에서 대화방을 나갈 때 로컬에 캐시된 메시지 리스트를 정리하는 경우에 매우 유용합니다. 하나씩 노드를 삭제하면 O(n) 시간이 걸리고 반복적인 연산이 필요합니다.
clear를 사용하면 O(1) 시간에 전체를 정리할 수 있습니다. 기존에는 while 루프로 removeFirst를 반복 호출했다면, 이제는 단순히 포인터 몇 개만 리셋하면 됩니다.
이 메서드의 핵심 특징은 첫째, O(1) 시간에 모든 노드를 제거한다는 점입니다. 둘째, 가비지 컬렉션이 자동으로 메모리를 회수합니다.
셋째, 리스트를 생성자 직후 상태로 되돌립니다. 이러한 간단함이 안전하고 효율적인 초기화를 제공합니다.
코드 예제
// 리스트의 모든 노드를 제거하는 메서드
clear() {
this.head = null; // head를 null로 설정
this.size = 0; // size를 0으로 리셋
// 자바스크립트의 가비지 컬렉터가 자동으로
// 참조가 끊어진 모든 노드의 메모리를 회수함
return this; // 메서드 체이닝 지원
}
// 전체 리스트를 배열로 생성하는 정적 메서드 (보너스)
static fromArray(arr) {
const list = new LinkedList();
for (const item of arr) {
list.append(item);
}
return list;
}
// 사용 예시
const list = LinkedList.fromArray([1, 2, 3, 4, 5]);
list.print(); // 1 -> 2 -> 3 -> 4 -> 5
list.clear(); // 리스트 초기화
console.log(list.isEmpty()); // true
console.log(list.getSize()); // 0
설명
이것이 하는 일: clear 메서드는 리스트의 시작점을 나타내는 head를 null로 만들고, 크기를 0으로 리셋하여 모든 노드와의 연결을 끊습니다. 첫 번째로, this.head = null을 실행합니다.
이것만으로도 리스트의 모든 노드가 "도달 불가능(unreachable)" 상태가 됩니다. head를 통해서만 리스트에 접근할 수 있는데, head가 null이 되면 어떤 노드도 접근할 수 없습니다.
자바스크립트의 가비지 컬렉터는 도달 불가능한 객체를 자동으로 감지하여 메모리를 회수합니다. 그 다음으로, this.size = 0으로 크기를 리셋합니다.
이렇게 하면 getSize()가 정확히 0을 반환하고, isEmpty()가 true를 반환합니다. 만약 size를 업데이트하지 않으면, 리스트는 비어있는데 size가 여전히 이전 값을 가지고 있어서 불일치가 발생합니다.
추가로 구현한 fromArray 정적 메서드는 배열을 받아서 연결 리스트를 생성합니다. 이는 테스트나 초기화 시 매우 유용합니다.
예를 들어 const list = LinkedList.fromArray([1,2,3])처럼 간단하게 리스트를 만들 수 있습니다. 정적 메서드이므로 인스턴스 없이 LinkedList.fromArray()로 호출합니다.
마지막으로, return this를 사용하여 메서드 체이닝을 지원합니다. list.append(1).append(2).clear().append(3) 같은 형태로 여러 연산을 연결할 수 있습니다.
이것은 선택사항이지만, 플루언트 인터페이스 패턴을 따르면 코드가 더 표현력 있게 됩니다. 여러분이 이 메서드를 사용하면 리스트를 빠르고 안전하게 초기화할 수 있습니다.
각 노드를 개별적으로 삭제할 필요 없이, 단 두 줄의 코드로 전체를 정리합니다. 메모리 관리는 자바스크립트 엔진이 알아서 처리하므로, 메모리 누수 걱정도 없습니다.
테스트 코드에서 특히 유용하며, beforeEach나 afterEach 훅에서 리스트를 초기화하는 데 사용할 수 있습니다.
실전 팁
💡 tail 포인터를 유지하는 경우, clear에서 tail도 null로 설정해야 합니다. 그렇지 않으면 tail이 삭제된 노드를 가리킬 수 있습니다.
💡 명시적으로 노드의 next를 null로 설정할 필요는 없습니다. 가비지 컬렉터가 자동으로 처리하므로, head만 끊으면 충분합니다.
💡 clear 후에 리스트를 재사용할 수 있습니다. 새로 생성하는 것과 동일한 상태가 되므로, 다시 노드를 추가할 수 있습니다.
💡 대용량 리스트를 정리할 때도 clear는 O(1)입니다. 노드가 100만 개여도 순회하지 않고 포인터만 바꾸므로 즉시 완료됩니다.
💡 프로덕션 환경에서 민감한 데이터를 다루는 경우, clear 전에 각 노드의 데이터를 명시적으로 null로 설정하여 보안을 강화할 수 있습니다.
11. 두 리스트 합치기 - concat 메서드 구현
시작하며
여러분이 두 개의 재생 목록을 하나로 합치고 싶다고 생각해보세요. "클래식 음악 리스트"와 "재즈 음악 리스트"를 연결해서 "통합 재생 목록"을 만드는 상황입니다.
배열에서는 concat이 새 배열을 만들지만, 연결 리스트에서는 포인터만 연결하면 됩니다. 두 리스트를 병합하는 것은 데이터 처리에서 자주 발생합니다.
여러 소스에서 온 데이터를 통합하거나, 분할 정복 알고리즘에서 결과를 합치거나, 병렬 처리된 데이터를 하나로 모으는 경우에 사용됩니다. 배열의 concat은 모든 요소를 복사해야 하므로 O(n + m) 시간과 공간이 필요합니다.
바로 이럴 때 연결 리스트의 concat이 효율적입니다. 첫 번째 리스트의 마지막 노드를 두 번째 리스트의 첫 노드에 연결하기만 하면 됩니다.
개요
간단히 말해서, concat 메서드는 현재 리스트의 끝에 다른 리스트를 연결하여 하나의 리스트로 만드는 기능입니다. 이 메서드가 실무에서 중요한 이유는 데이터 통합이 매우 흔한 작업이기 때문입니다.
여러 API 응답을 합치거나, 페이지네이션된 데이터를 연결하거나, 머지 소트 같은 알고리즘을 구현할 때 사용됩니다. 예를 들어, 소셜 미디어에서 "팔로우" 피드와 "추천" 피드를 합쳐서 하나의 통합 피드를 만들 때 매우 유용합니다.
배열의 concat은 새 배열을 생성하고 모든 요소를 복사하지만, 연결 리스트에서는 마지막 노드의 next만 변경하면 됩니다. 기존에는 데이터 복사로 인한 메모리와 시간 오버헤드가 있었다면, 이제는 포인터 하나만 조정하면 됩니다.
이 메서드의 핵심 특징은 첫째, 원본 리스트들을 수정할 수도 있고 새 리스트를 만들 수도 있다는 점입니다. 둘째, 첫 번째 리스트의 끝을 찾아야 합니다.
셋째, 두 리스트의 크기를 합산합니다. 이러한 처리가 안전한 병합을 보장합니다.
코드 예제
// 다른 리스트를 현재 리스트 끝에 연결하는 메서드
concat(otherList) {
// 현재 리스트가 비어있으면 다른 리스트를 그대로 사용
if (this.isEmpty()) {
this.head = otherList.head;
this.size = otherList.size;
return this;
}
// 다른 리스트가 비어있으면 변경 없음
if (otherList.isEmpty()) {
return this;
}
// 현재 리스트의 마지막 노드 찾기
let current = this.head;
while (current.next !== null) {
current = current.next;
}
// 마지막 노드의 next를 다른 리스트의 head에 연결
current.next = otherList.head;
// 크기 업데이트
this.size += otherList.size;
return this;
}
// 새로운 리스트를 생성하여 반환하는 버전 (불변)
concatNew(otherList) {
const newList = new LinkedList();
// 현재 리스트의 모든 노드를 복사
let current = this.head;
while (current !== null) {
newList.append(current.data);
current = current.next;
}
// 다른 리스트의 모든 노드를 복사
current = otherList.head;
while (current !== null) {
newList.append(current.data);
current = current.next;
}
return newList;
}
설명
이것이 하는 일: concat 메서드는 두 리스트를 하나로 연결하여, 첫 번째 리스트 뒤에 두 번째 리스트가 이어지는 구조를 만듭니다. 첫 번째로, 특별한 경우들을 처리합니다.
현재 리스트가 비어있으면, 다른 리스트를 그대로 사용합니다. this.head와 this.size를 otherList의 값으로 설정하면 됩니다.
반대로 다른 리스트가 비어있으면, 현재 리스트를 그대로 반환합니다. 이 엣지 케이스 처리가 없으면 뒤의 코드에서 null 참조 에러가 발생할 수 있습니다.
그 다음으로, 현재 리스트의 마지막 노드를 찾아야 합니다. current를 head부터 시작해서, while 루프로 current.next가 null인 노드를 찾을 때까지 이동합니다.
이 순회가 필요한 이유는, 단일 연결 리스트에서는 마지막 노드에 직접 접근할 방법이 없기 때문입니다. 만약 tail 포인터를 유지한다면 이 순회를 생략하고 O(1) 시간에 concat할 수 있습니다.
마지막 노드를 찾으면, current.next = otherList.head로 연결합니다. 이 한 줄로 두 리스트가 하나로 합쳐집니다.
그리고 this.size += otherList.size로 크기를 업데이트합니다. 이제 첫 번째 리스트가 두 리스트의 모든 노드를 포함하게 되었습니다.
마지막으로, concatNew 메서드는 원본을 수정하지 않고 새 리스트를 만듭니다. 두 리스트를 모두 순회하면서 데이터를 복사하여 새 리스트에 추가합니다.
이것은 불변성(immutability)을 유지하고 싶을 때 유용합니다. 원본 리스트를 보존해야 하는 경우에 이 버전을 사용하세요.
여러분이 concat을 사용하면 여러 데이터 소스를 효율적으로 통합할 수 있습니다. tail 포인터 없이는 O(n) 시간이 걸리지만, tail을 유지하면 O(1)로 개선됩니다.
concatNew는 O(n + m)이지만 원본 안전성을 제공합니다. 상황에 맞게 선택하세요.
실전 팁
💡 tail 포인터를 유지하면 concat을 O(1) 시간에 처리할 수 있습니다. 마지막 노드를 찾는 순회가 불필요해지기 때문입니다.
💡 원본 리스트를 수정하지 않으려면 concatNew를 사용하세요. 함수형 프로그래밍에서는 불변성이 중요합니다.
💡 concat 후 otherList는 여전히 원래 노드들을 가리킵니다. 두 리스트가 같은 노드를 공유하므로, 한쪽을 수정하면 다른쪽에도 영향을 줍니다.
💡 여러 리스트를 합칠 때는 reduce를 사용하세요. lists.reduce((acc, list) => acc.concat(list), new LinkedList())처럼 작성할 수 있습니다.
💡 대용량 리스트를 자주 합치는 경우, 더블 엔드 큐(Deque)나 tail 포인터를 고려하세요. 성능이 크게 향상됩니다.
12. 중간 노드 찾기 - findMiddle 메서드 구현 (토끼와 거북이 알고리즘)
시작하며
여러분이 긴 리스트의 정확히 중간 지점을 찾아야 하는 상황을 생각해보세요. 리스트를 두 부분으로 나누거나, 중간값을 찾거나, 머지 소트를 구현할 때 필요합니다.
배열이라면 length / 2로 간단하지만, 연결 리스트에서는 인덱스 접근이 안 됩니다. 중간 노드를 찾는 가장 직관적인 방법은 먼저 전체 길이를 세고, 다시 중간까지 순회하는 것입니다.
하지만 이는 두 번의 순회가 필요합니다. 면접이나 실무에서는 더 효율적인 방법이 선호됩니다.
바로 이럴 때 토끼와 거북이 알고리즘(Floyd's Cycle Detection)을 응용합니다. 한 포인터는 한 칸씩, 다른 포인터는 두 칸씩 이동하면, 빠른 포인터가 끝에 도달할 때 느린 포인터가 정확히 중간에 있습니다.
개요
간단히 말해서, findMiddle 메서드는 두 개의 포인터를 사용하여 단 한 번의 순회로 리스트의 중간 노드를 찾는 기능입니다. 이 알고리즘이 실무에서 중요한 이유는 효율성과 우아함 때문입니다.
머지 소트에서 리스트를 분할하거나, 팰린드롬 검사를 위해 중간을 찾거나, 순환 감지에도 사용됩니다. 예를 들어, 음악 재생 목록에서 중간 지점부터 재생하거나, 데이터 파티셔닝에서 균등 분할 지점을 찾을 때 매우 유용합니다.
두 번 순회하는 방법은 O(n + n/2) = O(1.5n)이지만, 토끼와 거북이는 O(n)으로 약간 더 효율적입니다. 기존에는 길이를 먼저 계산해야 했다면, 이제는 동시에 찾으면서 한 번에 처리할 수 있습니다.
이 알고리즘의 핵심 특징은 첫째, 단일 순회로 중간을 찾는다는 점입니다. 둘째, 추가 메모리를 거의 사용하지 않습니다(포인터 두 개).
셋째, 홀수/짝수 길이 모두 정확하게 처리합니다. 이러한 특징이 이 알고리즘을 면접 문제에서 자주 출제되게 만듭니다.
코드 예제
// 리스트의 중간 노드를 찾는 메서드 (토끼와 거북이)
findMiddle() {
if (this.isEmpty()) {
return null;
}
// 단일 노드면 그 노드가 중간
if (this.head.next === null) {
return this.head;
}
// 느린 포인터(거북이): 한 칸씩 이동
let slow = this.head;
// 빠른 포인터(토끼): 두 칸씩 이동
let fast = this.head;
// fast가 끝에 도달하면 slow는 중간에 위치
while (fast !== null && fast.next !== null) {
slow = slow.next; // 한 칸 이동
fast = fast.next.next; // 두 칸 이동
}
// slow가 가리키는 노드가 중간 노드
return slow;
}
// 실제 사용 예시
const list = LinkedList.fromArray([1, 2, 3, 4, 5]);
const middle = list.findMiddle();
console.log(middle.data); // 3 (홀수 개일 때 정확한 중간)
const list2 = LinkedList.fromArray([1, 2, 3, 4, 5, 6]);
const middle2 = list2.findMiddle();
console.log(middle2.data); // 4 (짝수 개일 때 뒤쪽 중간)
설명
이것이 하는 일: findMiddle 메서드는 두 개의 포인터를 서로 다른 속도로 이동시켜, 한 번의 순회만으로 리스트의 중간 노드를 정확하게 찾아냅니다. 첫 번째로, 엣지 케이스를 처리합니다.
빈 리스트면 null을 반환하고, 노드가 하나뿐이면 그 노드를 반환합니다. 이 체크가 없으면 뒤의 코드에서 null.next를 참조하려다 에러가 발생할 수 있습니다.
그 다음으로, 두 포인터를 초기화합니다. slow와 fast 모두 head부터 시작합니다.
while 루프의 조건이 매우 중요합니다. fast !== null && fast.next !== null을 체크하는 이유는, fast가 두 칸씩 이동하므로 fast.next.next를 참조하기 전에 fast.next가 존재하는지 확인해야 하기 때문입니다.
루프의 각 반복에서 slow는 한 칸 이동하고, fast는 두 칸 이동합니다. 이것이 핵심 아이디어입니다.
fast가 slow보다 두 배 빠르게 이동하므로, fast가 끝에 도달할 때 slow는 정확히 절반 지점에 있게 됩니다. 예를 들어 노드가 5개라면, fast가 5번째 노드에 도달할 때 slow는 3번째 노드에 있습니다.
마지막으로, 리스트 길이가 홀수일 때와 짝수일 때의 동작을 이해해야 합니다. 홀수(예: 5개)일 때는 slow가 정확히 중간(3번째)에 위치합니다.
짝수(예: 6개)일 때는 slow가 뒤쪽 중간(4번째)에 위치합니다. 만약 앞쪽 중간을 원한다면, 루프 조건을 조정하거나 previous 포인터를 추가로 유지하면 됩니다.
여러분이 이 알고리즘을 사용하면 연결 리스트를 효율적으로 분할하거나, 중간값을 빠르게 찾을 수 있습니다. 이 기법은 순환 감지, 팰린드롬 검사, 머지 소트 등 다양한 알고리즘의 기초가 됩니다.
특히 면접에서 자주 출제되므로, 이 패턴을 확실히 익혀두세요.
실전 팁
💡 이 알고리즘은 Floyd의 순환 감지 알고리즘의 변형입니다. 순환이 있는지 확인하는 데도 같은 원리를 사용합니다.
💡 앞쪽 중간을 원하면 slow의 이전 노드를 추적하면 됩니다. previous 포인터를 추가로 유지하세요.
💡 이 기법은 공간 복잡도가 O(1)이므로 메모리 제약이 있는 환경에서 매우 유용합니다.
💡 머지 소트를 구현할 때 이 메서드로 리스트를 두 부분으로 나눌 수 있습니다. 중간 노드를 찾고 그 앞에서 리스트를 분리하면 됩니다.
💡 디버깅 시 각 반복마다 slow와 fast의 위치를 출력하면 알고리즘의 동작을 시각화할 수 있습니다.