var Trie = function() {
this.root = {};
};
Trie.prototype.insert = function(word) {
let node = this.root;
word.split('').forEach((char)=>{
if (!node[char]) node[char] = {};
node = node[char];
})
node.isEnd = true;
};
Trie.prototype.search = function(word) {
let node = this.searchNode(word);
return node!=null?node.isEnd==true:false;
};
Trie.prototype.startsWith = function(prefix) {
let node = this.searchNode(prefix);
return node != null;
};
Trie.prototype.searchNode = function(word) {
let node = this.root;
for (let char of word.split('')) {
if (node[char]) {
node = node[char]
} else {
return null;
}
}
return node;
}이러한 코드에서
Trie.prototype.insert = function(word) {
let node = this.root;
word.split('').forEach((char)=>{
if (!node[char]) node[char] = {};
node = node[char];
})
node.isEnd = true;
};순간insert부분에서 이해가 잘 되지않았습니다. node를 변경했는데 root는 어째서 변경이 일어나는 것일까요?
이 이유는 바로 객체는 참조형이기 때문입니다.
참조형, 기본형 데이터
Primative type
간단한 설명만 하고 넘어가겠습니다.
Primative type는 기본적인 데이터 형식을 말합니다. 흔히
- number
- string
- boolean
- symbol
- null
- undefined
을 말하며 메모리상에 데이터 자체를 저장하므로 불변적인 특성을 지닙니다.
| 변수명 | num | str | ||
|---|---|---|---|---|
| 주소 | @1 | @2 |
| 주소 | @1 | @2 | ||
|---|---|---|---|---|
| 데이터 | 11223 | "ㅅㅅㄷㄷㄴㄴ" |
변수 안에는 주소가 들어가 있고 그 주소에 맞는 데이터 공간에 원하는 데이터가 존재하는 형식이다. 또한 우리가 아는 것처럼 @1주소 데이터를 아무도 바라보지 않는다면 가비지컬렉션에 의해 삭제된다.
Reference Type
Reference Type은 데이터 주소를 저장하는 가변적이며 참조적인 데이터 형식을 말합니다.
- object
- array
- function
- date
- regexp
- Map, WeakMap, Set, WeakSet
이 이에 속합니다.
왜 참조형인가
왜 참조형인지 그리고 참조형을 어떻게 작동하는 지를 알아야
Trie.prototype.insert = function(word) {
let node = this.root;
word.split('').forEach((char)=>{
if (!node[char]) node[char] = {};
node = node[char];
})
node.isEnd = true;
};코드의 작동을 이해할 수 있습니다.
| 변수명 | num | str | obj | |
|---|---|---|---|---|
| 주소 | @1 | @2 | @3 |
| 주소 | @1 | @2 | @3 | @4 |
|---|---|---|---|---|
| 데이터 | 11223 | "ㅅㅅㄷㄷㄴㄴ" | {a: @4} | "test" |
자 왜 참조형인지 보이시나요 ?
obj의 주소 @3에서는 데이터 자체가 들어있지 않기 때문입니다.
흐름
obj => @3 => {a:@4} => "test"
이렇게 타고 들어가야하기 때문입니다.
그렇다면 obj도 불변성을 지닐까요? 이것 또한 아닙니다.
obj의 a값을 변경한다면
| 변수명 | num | str | obj | |
|---|---|---|---|---|
| 주소 | @1 | @2 | @3 |
| 주소 | @1 | @2 | @3 | @4 | @5 |
|---|---|---|---|---|---|
| 데이터 | 11223 | "ㅅㅅㄷㄷㄴㄴ" | {a: | "test" | "newValue" |
이렇게 바뀌게 되는 것입니다.
즉
- 불변성 : 주소에 있는 기존 데이터를 그냥 두고 새로운 데이터를 만듬
- 가변성 : 주소에 있는 기존 데이터에는 다시 주소가 들어있기에 주소를 바꿈
이런 것입니다.
코드의 작동
let root = {}
let node = root;
"test".split('').forEach((char)=>{
if (!node[char]) node[char] = {};
node = node[char];
})
node.isEnd = true;
};좀 더 편하게 작동 변경했습니다.
이를 표로 표현하면
변수명 root node 주소 @1 @1
주소 @1 데이터 {}
이렇게 메모리에 저장될 것입니다.
그리고 반복문에 의해 텍스트 test 중 t가 실행되면
node.t = {}를 할당할 것입니다. 그러면 메모리는
변수명 root node 주소 @1 @1
주소 @1 @2 데이터 {t : @2} {}
로 바뀔 것입니다.
그리고 node = node[char]이 작동하면
변수명 root node 주소 @1 @2
주소 @1 @2 데이터 {t : @2} {}
여기서 다음 문자열 e가 시작되면
변수명 root node 주소 @1 @2
주소 @1 @2 @3 데이터 {t : @2} {e: @3} {}
으로 변경되는 것입니다. 마지막으로 node = node.e가 되면 node의 주소는 @3으로 변경될 것입니다.
이렇게 접근을 한다면 계속적인 반복을 사용하지 않아도 root의 deeps를 계속해서 증가할 것입니다.
root = {
t : {
e : {}
}
}
끝
사실 JS가 데이터를 어떻게 저장하는 지를 알면 문제를 쉽게 풀 수도, 코드를 쉽게 이해할 수도 있는 간단한 문제였습니다. 알고리즘을 잘 풀고 컴포넌트를 잘 만들고도 라이브러리 공부도 중요하지만 JS에 대한 공부. 즉, 기본기를 탄탄히 하는 것도 중요하다는 것을 배워봅니다.
참조
코어 자바스크립트 - 정재남 지음
