- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)
'자바스크립트로 하는 자료 구조와 알고리즘'은 전통적인(?) prototype을 통해 자료구조를 구현하였고, 'JavaScript Algorithms and Data Structures Masterclass'에서는 ES6의 class를 통해 자료구조를 구현하였다.
개인적으로는 YDKJS에서 소개된 '위임' 디자인 패턴이 매우 인상 깊었기 때문에, 이 시리즈에서 자료구조의 구현은 모두 이 '위임'패턴을 적용해보려고 한다.
각 노드가 다른 노드를 가리키는 자료 구조로 시작 노드는 head, 끝 노드는 tail이라 부른다.
각 노드는 값과 다른 노드(혹은 null)를 가리키는 포인터를 갖는다.
배열은 인덱스가 있지만, 연결 리스트는 인덱스가 없다.
따라서 연결 리스트의 특정 원소에 접근하려면 head(혹은 tail)부터 시작하여 하나 하나 타고 올라가는 수밖에 없다.
그러나 배열에 비해서 삽입과 삭제에 있어서 효율적이다.
배열 같은 경우 이미 인덱스가 정해져있기 때문에 삽입과 삭제로 인덱스의 재정렬이 필요한 경우가 많다.
(사실상 연결 리스트를 쓰는 이유)
const Node = {
init: function (val) {
this.val = val;
this.next = null;
},
};
// Node는 Object.create으로 생성한 위임객체로부터 동작을 위임받을 수임객체
const head = Object.create(Node);
// head는 init의 작동을 Node에 위임한 위임객체
head.init("시작 노드");
클래스형 패턴에서는 new로 생성과 초기화를 한꺼번에 하는 반면, 위임 패턴에서는 이렇듯 생성과 초기화가 분리되어 있다.
관점에 따라 이게 더 귀찮다고 생각할 수도 있겠지만, 생성과 초기화를 다른 시점에 수행해야 할 경우도 있기 때문에 위임 패턴이 더 유연하다고 할 수 있다.
const SinglyLinkedList = {
init: function () {
this.head = null;
this.tail = null;
this.length = 0;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
const SinglyLinkedList = {
// 앞 생략
push: function (val) {
const newNode = Object.create(Node);
newNode.init(val);
if (!this.head) {
// head가 없다는 것은 연결 리스트에 노드가 하나도 없다는 것이므로,
// 새로 생긴 노드는 head이자 tail이 된다.
this.head = newNode;
this.tail = newNode;
} else {
// tail의 next에 새로운 노드를 설정해주고,
// 그 노드를 새로 tail로 설정해준다.
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");
tail을 바로 찾으면 되니 시간 복잡도는 1이다.
Array.prototype.push의 경우 마찬가지로 시간 복잡도는 1이다.
const SinglyLinkedList = {
// 앞 생략
pop: function () {
if (!this.head) {
// head가 없다는 것은 더 이상 pop할 노드가 없다는 것
return;
}
let nodeToBePopped;
if (this.length == 1) {
// 연결 리스트의 길이가 1이라는 것은 head와 tail을 null로 초기화해야 한다는 것
nodeToBePopped = this.head;
this.head = null;
this.tail = null;
} else {
let previousNode = this.head;
let currentNode = previousNode.next;
while (currentNode.next) {
currentNode = currentNode.next;
previousNode = previousNode.next;
}
nodeToBePopped = currentNode;
previousNode.next = null;
this.tail = previousNode;
}
this.length--;
return nodeToBePopped;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");
previousNode를 찾기 위해서라도 순회를 돌아야하므로 시간 복잡도는 n이다.
Array.prototype.pop의 경우 마지막 인덱스에 접근만 하면 되기 때문에 시간 복잡도는 1이다.
const SinglyLinkedList = {
// 앞 생략
shift: function () {
if (!this.head) {
// head가 없다는 것은 더 이상 shift할 노드가 없다는 것
return;
}
const nodeToBeShifted = this.head;
if (this.length == 1) {
// 연결 리스트의 길이가 1이라는 것은 head와 tail을 null로 초기화해야 한다는 것
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
}
this.length--;
nodeToBeShifted.next = null;
return nodeToBeShifted;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");
head를 바로 찾으면 되니 시간 복잡도는 1이다.
Array.prototype.shift의 경우 모든 원소들의 인덱스를 하나씩 앞으로 당겨야 하므로 시간 복잡도가 n이다.
const SinglyLinkedList = {
// 앞 생략
unshift: function (val) {
const newNode = Object.create(Node);
newNode.init(val);
if (!this.head) {
// head가 없다는 것은 unshift한 노드가 head이자 tail이 되어야 한다는 것
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
head를 바로 찾으면 되니 시간 복잡도는 1이다.
Array.prototype.unshift의 경우 모든 원소들의 인덱스를 하나씩 뒤로 밀어내야 하므로 시간 복잡도가 n이다.
const SinglyLinkedList = {
// 앞 생략
get: function (idx) {
if (idx < 0 || idx >= this.length) {
return;
}
let currentNode = this.head;
for (let i = 0; i < idx; i++) {
currentNode = currentNode.next;
}
return currentNode;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");
최선의 경우는 인덱스가 0인 경우로 시간 복잡도가 1이고,
최악의 경우는 인덱스가 (this.length - 1)인 경우로 시간 복잡도가 n까지 올라간다.
일반적으로 시간 복잡도를 n으로 간주한다.
Array의 경우 인덱스로 원소에 접근하는 것은 원소의 위치에 관계없이 시간 복잡도가 1이다.
const SinglyLinkedList = {
// 앞 생략
set: function (idx, val) {
const nodeToChangeValue = this.get(idx);
if (!nodeToChangeValue) {
return;
}
nodeToChangeValue.val = val;
return nodeToChangeValue;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");
const SinglyLinkedList = {
// 앞 생략
insert: function (idx, val) {
if (idx < 0 || idx > this.length) {
return;
}
if (idx == 0) {
return this.unshift(val);
}
if (idx == this.length) {
return this.push(val);
}
const newNode = Object.create(Node);
newNode.init(val);
const previousNode = this.get(idx - 1);
// 앞선 예외처리의 결과로 여기에서 idx - 1의 범위는 다음과 같다.
// 1 <= idx <= this.length - 1
// 0 <= (idx - 1) <= this.length - 2
// 따라서 previousNode는 반드시 존재할 수 밖에 없음.
const oldNode = previousNode.next;
// previousNode의 인덱스 범위에 1을 더한 값을 범위로 가진다.
// 즉, 1 <= indexOfOldNode <= this.length - 1
// 역시, oldNode도 반드시 존재한다.
newNode.next = oldNode;
previousNode.next = newNode;
this.length++;
return this;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");
const SinglyLinkedList = {
// 앞 생략
remove: function (idx) {
if (idx < 0 || idx >= this.length) {
return;
}
if (idx == 0) {
return this.shift();
}
if (idx == this.length - 1) {
return this.pop();
}
const previousNode = this.get(idx - 1);
// 앞선 예외처리의 결과로 인덱스의 범위는 아래와 같다.
// 1 <= idx <= this.length - 2
// 0 <= (idx - 1) <= this.length - 3
// 따라서 newTail은 반드시 존재한다.
const nodeToBeRemoved = previousNode.next;
// 1 <= indexOfNodeToBeRemoved <= this.length - 2
previousNode.next = nodeToBeRemoved.next;
this.length--;
nodeToBeRemoved.next = null;
return nodeToBeRemoved;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("CentOS");
list.push("레드햇");
list.push("닉값하고 싶다");
const SinglyLinkedList = {
// 앞 생략
reverse: function () {
if (!this.head) {
return this;
}
let currentNode = this.head;
while (currentNode.next) {
const nextNode = currentNode.next;
currentNode.next = nextNode.next;
nextNode.next = this.head;
this.head = nextNode;
}
this.tail = currentNode;
return this;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("레드햇");
const SinglyLinkedList = {
// 앞 생략
find: function (val) {
if (!this.head) {
return;
}
let currentNode = this.head;
for (let i = 0; i < this.length; i++) {
if (currentNode.val == val) {
return i.toString();
}
currentNode = currentNode.next;
}
return;
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("레드햇");
최선의 경우는 찾고자 하는 노드가 head에 해당하는 경우로 시간 복잡도가 1이고,
최악의 경우는 찾고자 하는 노드가 tail에 해당하는 경우로 시간 복잡도가 n까지 올라간다.
일반적으로 시간 복잡도를 n으로 간주한다.
Array.prototype.indexOf가 이와 유사하지 않을까 추측한다
(내부 코드를 모르니...)
const SinglyLinkedList = {
// 앞 생략
removeByValue: function (val) {
if (!this.head) {
return;
}
const indexOfTarget = parseInt(this.find(val));
if (isNaN(indexOfTarget)) {
return;
}
return this.remove(indexOfTarget);
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("CentOS");
list.push("레드햇");
list.push("닉값하고 싶다");
const SinglyLinkedList = {
// 앞 생략
removeDuplicate: function () {
if (!this.head) {
return this;
}
const hashTable = {};
let currentNode = this.head;
let count = 0;
while (true) {
let nextNode = currentNode.next;
// 밑에서 remove할 경우 currentNode의 next참조가 사라지기 때문에
// 해당 참조를 보존할 목적
if (!hashTable.hasOwnProperty(currentNode.val)) {
hashTable[currentNode.val] = 1;
} else {
this.remove(count);
count--;
}
if (nextNode) {
currentNode = nextNode;
count++;
} else {
return this;
}
}
},
};
const list = Object.create(SinglyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");
list.push("우분투");
list.push("CentOS");
list.push("리눅스");
list.push("우분투");
const Node = {
init: function (val) {
this.val = val;
this.next = null;
},
};
const SinglyLinkedList = {
init: function () {
this.head = null;
this.tail = null;
this.length = 0;
},
push: function (val) {
const newNode = Object.create(Node);
newNode.init(val);
if (!this.head) {
// head가 없다는 것은 연결 리스트에 노드가 하나도 없다는 것이므로,
// 새로 생긴 노드는 head이자 tail이 된다.
this.head = newNode;
this.tail = newNode;
} else {
// tail의 next에 새로운 노드를 설정해주고,
// 그 노드를 새로 tail로 설정해준다.
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
},
pop: function () {
if (!this.head) {
// head가 없다는 것은 더 이상 pop할 노드가 없다는 것
return;
}
let nodeToBePopped;
if (this.length == 1) {
// 연결 리스트의 길이가 1이라는 것은 head와 tail을 null로 초기화해야 한다는 것
nodeToBePopped = this.head;
this.head = null;
this.tail = null;
} else {
let previousNode = this.head;
let currentNode = previousNode.next;
while (currentNode.next) {
currentNode = currentNode.next;
previousNode = previousNode.next;
}
nodeToBePopped = currentNode;
previousNode.next = null;
this.tail = previousNode;
}
this.length--;
return nodeToBePopped;
},
shift: function () {
if (!this.head) {
// head가 없다는 것은 더 이상 shift할 노드가 없다는 것
return;
}
const nodeToBeShifted = this.head;
if (this.length == 1) {
// 연결 리스트의 길이가 1이라는 것은 head와 tail을 null로 초기화해야 한다는 것
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
}
this.length--;
nodeToBeShifted.next = null;
return nodeToBeShifted;
},
unshift: function (val) {
const newNode = Object.create(Node);
newNode.init(val);
if (!this.head) {
// head가 없다는 것은 unshift한 노드가 head이자 tail이 되어야 한다는 것
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
},
get: function (idx) {
if (idx < 0 || idx >= this.length) {
return;
}
let currentNode = this.head;
for (let i = 0; i < idx; i++) {
currentNode = currentNode.next;
}
return currentNode;
},
set: function (idx, val) {
const nodeToChangeValue = this.get(idx);
if (!nodeToChangeValue) {
return;
}
nodeToChangeValue.val = val;
return nodeToChangeValue;
},
insert: function (idx, val) {
if (idx < 0 || idx > this.length) {
return;
}
if (idx == 0) {
return this.unshift(val);
}
if (idx == this.length) {
return this.push(val);
}
const newNode = Object.create(Node);
newNode.init(val);
const previousNode = this.get(idx - 1);
// 앞선 예외처리의 결과로 여기에서 idx - 1의 범위는 다음과 같다.
// 1 <= idx <= this.length - 1
// 0 <= (idx - 1) <= this.length - 2
// 따라서 previousNode는 반드시 존재할 수 밖에 없음.
const oldNode = previousNode.next;
// previousNode의 인덱스 범위에 1을 더한 값을 범위로 가진다.
// 즉, 1 <= indexOfOldNode <= this.length - 1
// 역시, oldNode도 반드시 존재한다.
newNode.next = oldNode;
previousNode.next = newNode;
this.length++;
return this;
},
remove: function (idx) {
if (idx < 0 || idx >= this.length) {
return;
}
if (idx == 0) {
return this.shift();
}
if (idx == this.length - 1) {
return this.pop();
}
const previousNode = this.get(idx - 1);
// 앞선 예외처리의 결과로 인덱스의 범위는 아래와 같다.
// 1 <= idx <= this.length - 2
// 0 <= (idx - 1) <= this.length - 3
// 따라서 newTail은 반드시 존재한다.
const nodeToBeRemoved = previousNode.next;
// 1 <= indexOfNodeToBeRemoved <= this.length - 2
previousNode.next = nodeToBeRemoved.next;
this.length--;
nodeToBeRemoved.next = null;
return nodeToBeRemoved;
},
reverse: function () {
if (!this.head) {
return this;
}
let currentNode = this.head;
while (currentNode.next) {
const nextNode = currentNode.next;
currentNode.next = nextNode.next;
nextNode.next = this.head;
this.head = nextNode;
}
this.tail = currentNode;
return this;
},
find: function (val) {
if (!this.head) {
return;
}
let currentNode = this.head;
for (let i = 0; i < this.length; i++) {
if (currentNode.val == val) {
return i.toString();
}
currentNode = currentNode.next;
}
return;
},
removeByValue: function (val) {
if (!this.head) {
return;
}
const indexOfTarget = parseInt(this.find(val));
if (isNaN(indexOfTarget)) {
return;
}
return this.remove(indexOfTarget);
},
removeDuplicate: function () {
if (!this.head) {
return this;
}
const hashTable = {};
let currentNode = this.head;
let count = 0;
while (true) {
let nextNode = currentNode.next;
// 밑에서 remove할 경우 currentNode의 next참조가 사라지기 때문에
// 해당 참조를 보존할 목적
if (!hashTable.hasOwnProperty(currentNode.val)) {
hashTable[currentNode.val] = 1;
} else {
this.remove(count);
count--;
}
if (nextNode) {
currentNode = nextNode;
count++;
} else {
return this;
}
}
},
};
const list = Object.create(SinglyLinkedList);
list.init();