1. 연결 리스트 소개
1-1. head, tail, length 프로퍼티를 담고 있는 자료 구조
- head = 연결 리스트의 시작 노드
- tail = 연결 리스트의 마지막 노드
- 중간 노드들은?
- head 노드로 부터 다음 노드, 그 다음 노드, ...를 알아내는 방식으로 접근한다.
- length = 작업을 용이하게 하기 위해 길이를 유지한다.
- 필요한 작업을 수행하기 위해 연결 리스트에 몇 개의 요소가 있는지 알아야 한다.
1-2. 연결 리스트는 노드로 구성되어 있고, 각 노드는 value와 포인터를 갖는다.
- 포인터는 다른 노드나 null을 가리킨다.
- 포인터가 null을 가리킨다 ? = 더이상 다음 노드가 없다.
1-3. 단일 연결리스트란?
- 각 노드가 다음 노드로 오직 단일 방향으로만 연결되어 있는 연결 리스트
2. 배열과 연결 리스트의 차이점
2-1. 연결리스트는 엘리베이터가 없는 건물이고 배열은 엘리베이터가 있는 건물
2-2. 표 정리
| 리스트 | 배열 |
|---|---|
| 인덱스가 없다 | 순서대로 인덱스가 있다 |
| next 포인터를 가진 노드를 통해 연결된다 | 삽입과 삭제에 비용이 많이 들 수 있다(expensive) |
| 랜덤 액세스가 허용되지 않는다 | 특정 인덱스로 빠르게 접근할 수 있다 |
3. 단일 연결리스트 구현
// val = 값
// next = 포인터
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
const first = new Node('Hi');
first.next = new Node('there');
first.next.next = new Node('how');
first.next.next.next = new Node('are');
first.next.next.next.next = new Node('you');이 상태에서 first는 이렇게 생겼다. 두번째 사진은 next를 끝까지 펼친 모습이다.
3-1. next.next.next...는 너무 번거롭다. push 메서드 만들기
push 메서드 역할 = 새로운 Node를 연결 리스트의 끝에 추가
// 의사코드
// 1. push 메서드는 한 value을 받아야 한다.
// 2. 메서드에 전달되는 value를 사용해서 새로운 Node를 생성해라.
// 3. 리스트에 head가 없다면, head와 tail은 새로 생성한 Node가 되도록 설정해라.
// 3-1. 그게 아니면, tail의 다음 프로퍼티로 새로운 Node를 설정하고 tail 프로퍼티는 새롭게 생성된 Node가 되도록 해라.
// 4. 길이를 1 추가해라.
// 5. 연결 리스트를 반환해라.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val) {
const newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
}
const list = new SinglyLinkedList();
list.push('단일');
list.push('연결');
list.push('리스트');결과화면
- '연결'은 head의 next에 담겨있다.
3-2. pop 메서드 추가
// 의사코드
// 1. 리스트에 아무 노드도 없는 경우, undefined를 반환한다.
// 2. tail에 도달할 때까지 리스트를 순회한다.
// 3. 마지막에서 2번째 노드의 `next`를 `null`로 설정한다.
// 4. 마지막에서 2번째 노드를 tail로 설정한다.
// 5. 길이를 1 감소시킨다.
// 6. 제거된 노드의 값을 반환한다.
class SinglyLinkedList{
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
...
pop() {
if (!this.head) return undefined;
let current = this.head;
let newTail = current;
while (current.next) {
newTail = current;
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
// length가 1일때 pop()을 실행할 경우 head와 tail이 같은 노드를 가리키기 때문에 초기화
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
}
const list = new SinglyLinkedList();
list.push('단일');
list.push('연결');
list.push('리스트');
결과화면
- pop 메서드를 실행하면 '리스트' 노드를 반환한다.
- list 변수에는 '리스트' 노드가 사라져 있고 새로운 tail로 '연결'이 설정되었다.
3-3. shift 메서드 추가
// 의사코드
// 1. 노드가 없을 경우, undefined를 반환한다.
// 1-1. 노드가 있을 경우, 현재의 head를 변수에 저장하고
// 2. 현재 head의 next 노드를 가리키도록 헤드 속성을 업데이트한다.
// 3. 리스트의 길이를 1 감소시킨다.
// 4. 제거된 이전 head의 값을 반환한다.
...
shift() {
if (!this.head) return undefined;
let oldHead = this.head;
this.head = oldHead.next;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return oldHead;
}결과화면
3-4. unshift 메서드 추가
// 의사코드
// 1. 메서드로 전달된 값을 사용해서 새로운 노드를 생성한다.
// 2. list에 head가 없으면 head와 tail은 새롭게 생성된 노드가 되도록 한다.
// 2-1. 노드가 이미 있는 경우, 새롭게 생성된 노드의 next를 현재의 head 값으로 설정한다.
// 3. list의 길이를 1 증가시킨다.
// 4. liked list를 반환한다.
unshift(val) {
const newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}결과화면
3-5. get 메서드 추가
- 연결리스트 내에서 위치로(by it's position) 노드를 검색(retrieve)하는 메서드
// 의사코드
// 1. index를 받는다.
// 1-1. index가 음수이거나 리스트의 길이와 같거나 길이보다 클 경우 not working (return null)
// 2. 루프를 통해 인덱스가 지정하는 위치에 이를 때까지 반복해서 이동해서 해당 index 위치에 있는 노드를 반환한다.
get(index) {
if (index < 0 || index >= this.length) return null;
let count = 0;
let current = this.head;
while (count < index) {
current = current.next;
count++;
}
return current;
}결과
3-6. set 메서드 추가
- 연결리스트 내에서 그 위치에 따라 노드의 값을 바꾸는 메서드
// 1. index와 value 받기
// 2. get 메서드를 사용해서 노드 찾기
// 3. 노드가 없을 경우 return false
// 4. 노드가 있을 경우 그 노드의 값이 value가 되도록하고 return true
set(index, val) {
const foundNode = this.get(index);
if (foundNode) {
foundNode.val = val;
return true;
} else return false;
}결과
(추가) Class의 Static(정적) 메서드 관련
강의에서 정적 메서드 내용이 지나갔는데 딥다이브에서 읽은 기억이 나서 찾아본 내용
MDN에서 정적 메서드는 애플리케이션 유틸리티 함수를 만드는데 사용된다고 한다.
class Student {
constructor(firstName, lastName) {
this.firstName = firstName;
this.lastName = lastName;
}
// 클래스 몸체에서 정의한 메서드는 기본적으로 프로토타입 메서드가 된다
fullName() {
return `Your full name is ${this.firstName} ${this.lastName}`;
}
// 정적 메서드
static enrollStudents(...students) {
return 'ENROLLING STUDENTS!';
}
}
let firstStudent = new Student('Colt', 'Steele');
let secondStudent = new Student('Blue', 'Steele');
// 정적 메서드를 사용하면 클래스의 인스턴스화 없이 호출될 수 있다.
Student.enrollStudents([firstStudent, secondStudent]);정적 메서드와 프로토타입 메서드의 차이점
- 정적 메서드와 프로토타입 메서드는 자신이 속해 있는 프로토타입 체인(?????)이 다르다
- 정적 메서드는 클래스로 호출하고, 프로토타입 메서드는 인스턴스로 호출한다.
- 정적 메서드는 인스턴스 프로퍼티를 참조할 수 없지만 프로토타입 메서드는 참조할 수 있다.
this에서의 차이점
- 클래스 메서드 내부의 this는 메서드를 소유한 객체가 아니라 메서드를 호출한 객체에 바인딩된다.
- 프로토타입 메서드는 인스턴스로 호출해야 하므로 프로토타입 메서드 내부의 this는 프로토타입 메서드를 호출한 인스턴스(firstStudent, secondStudent)를 가리킨다.
- 정적 메서드는 클래스로 호출해야 하므로 정적 메서드 내부의 this는 인스턴스가 아닌 클래스를 의미한다.
📌 메서드 내부에서 인스턴스 프로퍼티를 참조할 필요가 있다면 this를 써야 하기 때문에 프로토타입 메서드로 정의해야 하고, 반대 경우라면 정적 메서드로 정의하는 것이 좋다(메서드 내부에 this가 없어도 프로토타입 메서드로 정의할 수 있지만 인스턴스를 생성한 다음 호출해야 하므로 불편하다).
class StaticMethodCall {
static staticMethod() {
return '정적 메서드 실행';
}
static anotherStaticMethod() {
// 동일 클래스 내 다른 정적 메서드 내에서 정적 메서드를 호출하는 경우
// 키워드 this를 사용할 수 있다
return this.staticMethod() + '(다른 정적 메서드에서)';
}
}
StaticMethodCall.staticMethod(); // '정적 메서드 실행'
StaticMethodCall.anotherStaticMethod(); // '정적 메서드 실행(다른 정적 메서드에서)'class Triple {
static triple(n) {
n = n || 1;
return n * 3;
}
}
class BiggerTriple extends Triple {
static triple(n) {
return super.triple(n) * super.triple(n);
}
}
console.log(Triple.triple()); // 3
console.log(Triple.triple(6)); // 18
BiggerTriple.triple(3); // 81
const tp = new Triple();
console.log(BiggerTriple.triple(3)); // 81
console.log(tp.triple()); // TypeError: tp.triple is not a function
console.log(tp.constructor.triple(4)); // 12
Frontend Engineer