백준 1158번 요세푸스 문제를 푸는데,
linked list를 활용해서 원형을 구현할 수 있을 것 같았다.
어레이와 비교해서, 링크드 리스트는 index로 노드를 찾아내는데에 느리다는 단점을 가지고 있다.
하지만 이 문제에서는 index가 최대 5000밖에 되지 않는다.
그래도 어레이 또한 가장 뒤가 아닌 인덱스에서 값을 빼고 앞으로 땡기는 과정은 최악 O(n)이기 때문에,
공부하는 김에
자바스크립트로 linked list와 Circular Linked List를 구현해보았다!!
Linked List
링크드리스트는 Node객체가 줄줄이 이어진 list이다.
구현코드
class Node{
constructor(data,next=null){
this.data=data;
this.next=next;
}
}
class LinkedList{
constructor(){
this.head=null;
this.size=0;
}
insertFirst(data){
const newNode=new Node(data,this.head);
this.head=newNode;
this.size+=1;
}
insertLast(data){
const newNode=new Node(data);
let lastNode;
if(this.head === null){
this.head=newNode;
}else{
lastNode=this.head;
while(lastNode.next !== null){
lastNode=lastNode.next;
}
lastNode.next=newNode;
}
this.size+1;
}
insertAt(data,index){
const newNode=new Node(data);
let previousNode, nextNode=this.head, count=0;
if(index<0 || index>=this.size) return;
if(index===0) {
insertFirst(data);
return;
}
if(index===this.size){
insertLast(data);
return;
}
while(count<index){
count+=1;
previousNode=nextNode;
nextNode=nextNode.next;
}
previousNode.next=newNode;
newNode.next=nextNode;
this.size+=1;
}
removeAt(index){
if(index<0 || index>=this.size) return;
let previousNode, removedNode=this.head, count=0;
if(index===0){
this.head=removedNode.next;
}else{
while(count<index){
count+=1;
previousNode=removedNode;
removedNode=removedNode.next;
}
previousNode.next=removedNode.next;
}
this.size+=1;
}
}📌 링크드 리스트 단점
어레이와 다르게 메모리상에서 연속되어 위치하지 않는다. 다음으로 이어질 노드의 reference를 저장하여 이 주소값으로 연결되어 이어나간다.
그래서 어레이와 다르게,
각 노드마다 다음 노드를 가리키는 포인터를 따로 저장할 메모리가 추가로 필요하게 된다.
연속된 메모리 주소에 저장되지 않는 특성때문에,
특정 위치에 있는 노드를 얻는데 드는 비용이 커서 속도가 상대적으로 느리다.
배열은 배열의 시작점에서 인덱스를 찾아가면 되기 때문에 매우 빠르다.
반면, 링크드 리스트는 최악의 경우 O(N)의 시간복잡도를 가지게 된다.
위 코드에서 보는 것 처럼 this.size라는 값을 따로 저장하게 된다.
이 사이즈는 리스트가 연결된 노드의 수를 의미하는데,
n번째 노드를 원한다면 size값 이하에서 for문을 직접 돌려서 한노드 한노드 찾아가야..;; 하기 때문에 속도가 느린 것이다.
📌 링크드 리스트 장점
단점에서 썼듯이, 앞에서부터 차례대로 한노드 한노드 찾아가는 것이 매우 느리다.
하지만 이 특징 때문에 새로운 노드의 추가와 노드의 삭제가 쉽고 빠르다.
어떤 노드의 다음노드를 지우고 싶다면,
다음 노드와 연결되어있던 포인터를 다다음노드를 가리키도록 싸악 옮겨 버리면 끝이다.
📌사용처
노드의 유동성이 장점이기 때문에, 데이터의 추가,삭제가 빈번한 상황에서 유리하다. 조회는 시간이 많이 걸리기 때문에 이런 경우는 시간적으로 불리하다.
Circular Linked List로 변형해서 문제풀기!
📌 구현 코드
constructor(){
this.tail=null;
this.size=0;
}위에서 구현한 CircularLinkedList 클래스의 에서
this.head 대신 this.tail로 바꾼다.
원형 링크드 리스트는 head와 tail의 구분의미가 없으므로,
가장 끝을 tail로 지정하고, 이 노드의 next포인터를 가장 앞의 노드를 가리키게 하면 된다.
📌 메소드 2가지
이 문제를 풀기 위해 메소드 두개를 만들었다.
전체 코드는 하단에 있다.
insertTail(data): 끝에 데이터 추가하기.
- 🚫 유의사항
- 마지막 노드를 변수로 만들어서 사용하려고
tailNode=this.tail이런 식으로 썼었는데 디버깅해보니 계속 null이었다. - 당연함.
this.tail의 초기값은 그냥 null이고,,,, 포인터가 아닌데 포인터로 착각해서 여태 null가지고 북치고 장구치고 있었다.
휴.........화가 난다ㅠㅠ
- 마지막 노드를 변수로 만들어서 사용하려고
// Insert new node to tail
insertTail(data){
const newNode=new Node(data);
// 리스트가 비어있을 때, 새 노드가 head이자 tail이다.
if(this.tail === null){ // 노드가 없다면 tail이 가리키는 곳이 null이다.
this.tail=newNode; // tail을 새 노드를 가리키도록 주소를 할당한다.
this.tail.next=newNode; // tail.next(=head)에 새 노드를 할당한다.
}
// 리스트에 노드가 있을 때, 기존 tail자리에 새 노드를 넣는다.
else{
newNode.next=this.tail.next; // 새 노드 다음에 head노드 연결한다.
this.tail.next=newNode; // 새 노드를 현재 tail의 다음으로 연결한다.
this.tail=newNode; // 새 노드를 tail로 지정한다.
}
this.size+=1;
return;
}removeInFrontOfTail(k): tail노드로 부터 k번째 노드를 지우고, 지운 노드에 있던 데이터를 반환.
// Remove kth nodes in front of tail
removeInFrontOfTail(k){
let previousNode,removedNode=this.tail;
let removedData;
// 꼬리노드에서 k번 앞으로 나아간 지워야할노드 removedNode를 구한다.
// 지워야할노드의 이 전 노드 previousNode를 구한다.
for(let i=0;i<k;i++){
previousNode=removedNode;
removedNode=removedNode.next;
}
removedData=removedNode.data;
previousNode.next=removedNode.next;
this.tail=removedNode; // 다음 반복을 위해 지워진 노드를 tail로 지정한다.
this.size-=1;
return removedData;
}
📌 실제 문제풀이
const cLinkedList=new CircularLinkedList();
let answer='';
// 차례대로 tail에 삽입한다.
for(let i=1;i<=n;i++){
cLinkedList.insertTail(i);
}
// 리스트가 모두 비워질 때까지
// 꼬리에서 k번 째 노드를 지운다.
while(cLinkedList.size>0){
answer+=cLinkedList.removeInFrontOfTail(k)+', ';
}
console.log(`<${answer.slice(0,-2)}>`);
링크드리스트는 처음 제대로 공부해보는데 겁나 헷갈렸다 ㅜㅜㅜ으악
