반응형
1. 문제
- 단일 연결 리스트 혹은 이중 연결 리스트를 만들어라. 조건은 다음과 같다.
- 생성자로 객체를 생성하며, 매개변수는 받지 않는다.
- get 함수는 index를 매개변수로 받고 해당 인덱스의 value롤 반환하고, 없으면 -1을 반환하라.
- addAtHead 함수는 새로운 노드를 연결 리스트의 맨 처음에 추가하라.
- addAtTail 함수는 새로운 노드를 연결 리스트의 맨 마지막에 추가하라.
- addAtIndex 함수는 주어진 인덱스에 새로운 노드를 추가하되, 만약 인덱스가 전체 길이와 같을 때도 추가하고 전체 길이보다 큰 경우는 무시한다.
- deleteAtIndex 함수는 해당 index의 노드를 제거하라.
2. 해결
class Node { // 노드 클래스
value: number;
next: Node | null;
constructor(value: number) {
this.value = value;
this.next = null;
}
}
class MyLinkedList { // 단일 연결 리스트.
head: Node | null;
size: number;
constructor() { // 생성자.
this.head = null;
this.size = 0;
}
get(index: number): number { // get 함수.
let pointer = this.head;
let idx = 0;
while (pointer) { // pointer가 null이 아닐 때 까지 반복.
if (idx === index) return pointer.value; // index가 일치하는 Node의 value 반환.
pointer = pointer.next; // 다음 노드로 갱신.
idx++; // 현재 인덱스 갱신.
}
return -1; // 없으면 -1 반환.
}
addAtHead(val: number): void { // addAtHead 함수.
const newNode = new Node(val); // 새로운 노드.
newNode.next = this.head; // 현재 head를 새로운 노드의 next로 지정.
this.head = newNode; // 새로운 노드를 head로 지정.
this.size++; // size 증가.
}
addAtTail(val: number): void { // addAtTail 함수.
const newNode = new Node(val); // 새로운 노드.
if (!this.head) { // 비어 있으면, head로 지정.
this.head = newNode;
} else { // 비어 있지 않으면,
let pointer = this.head;
while (pointer.next) { // node를 탐색해서 next가 null인 노드를 찾고.
pointer = pointer.next;
}
pointer.next = newNode; // 해당 노드의 next에 새로운 노드를 지정.
}
this.size++; // size 증가.
}
addAtIndex(index: number, val: number): void { // addAtIndex 함수.
if (index > this.size) return; // index가 size보다 크면 무시.
if (index === 0) { // index가 0이면 addAtHead 함수 호출.
this.addAtHead(val);
return;
}
const newNode = new Node(val); // 새로운 노드 생성.
let pointer = this.head;
let idx = 0;
while (pointer && idx < index - 1) { // 변경 위치 노드 탐색.
pointer = pointer.next;
idx++;
}
if (pointer) { // 만약 변경 위치에 노드가 존재하면,
newNode.next = pointer.next; // 해당 노드의 next를 새로운 노드의 next로 지정.
pointer.next = newNode; // 해당 노드의 next를 새로운 노드로 지정.
this.size++; // size 증가.
}
}
deleteAtIndex(index: number): void { // deleteAtIndex 함수.
if (index < 0 || index >= this.size) return; // 범위를 벗어나는 index는 무시.
if (index === 0) { // 0번 인덱스를 지우는 경우,
this.head = this.head!.next; // 현재 head의 next를 head로 지정.
} else { // 그 외.
let pointer = this.head;
let idx = 0;
while (pointer && idx < index - 1) { // 삭제 위치 노드 탐색.
pointer = pointer.next;
idx++;
}
if (pointer && pointer.next) { // 삭제 위치 노드의 next 갱신.
pointer.next = pointer.next.next;
}
}
this.size--; // size 감소.
}
}
- 일반적인 연결 리스트 구현이 아니라 몇몇 조건들이 있어서 애좀 먹었다. 침착하게 풀면 괜찮을 거 같다.