단일연결리스트로 구현한 Stack, Queue

단일연결리스트로 구현한 Stack, Queue

Stack

first in first out

// 단일연결리스트로 구현한 stack
class Node{
    constructor(value, next){
        this.value = value;
        this.next = next;
    }
}

class Stack{
    _size = 0; 
    constructor(){
        this.head = null; // 가장 위에 있는(가장 나중에 있는) 노드
        this._size = 0;
    }
    get size(){
        return this._size;
    }
    push(value){
        const new_node = new Node(value, this.head); 
        this.head = new_node;       
        this._size++;
    }
    pop(){
        if(this.head == null){ // ===null ||  ===undefined
            console.log('stack is empty');
            return;
        }
        const target_node = this.head;
        this.head = target_node.next;
        this._size--;
        return target_node;
    }
}
const s = new Stack();
s.push('a');
s.push('b');
console.log(s);

Queue

fist in last out

// 단일연결리스트로 구현한 Queue
class Node{
    constructor(value, next){
        this.value = value;
        this.next = next;
    }
}

class Queue{
    _size = 0; 
    constructor(){
        this.first = null; // 맨 처음 노드
        this.last = null; // 맨 마지막 노드
        this._size = 0;
    }
    get size(){
        return this._size;
    }
    enqueue(value){
        const new_node = new Node(value); 
        if(!this.first){
            this.first = new_node;
            this.last = new_node;
        }else{
            this.last.next = new_node; 
            this.last = new_node;
        }
             
        this._size++;
    }
    dequeue(){
        if(this.first == null){ 
            console.log('queue is empty');
            return;
        }
        const target_node = this.first;
        if(this.first === this.last){
            this.last = null;
        }
        this.first = this.first.next;
        this._size--;
        return target_node;
    }
}
const q = new Queue();
q.enqueue('a');
q.enqueue('b');
console.log(q);

단일연결리스트 linked list

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

추가, 삭제 기능

class Node{
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class LinkedList{
    constructor(){
        this.head = null;
    }
    size(){
        let count = 0;
        let node = this.head;
        while(node){
            count++;
            node = node.next;
        }
        return count;
    }
    clear(){
        this.head = null;
    }
    getFirst(){
        return this.head;
    }
    getLast(){
        let node = this.head;
        while(node.next){
            node = node.next;
        }
        return node;
    }
    append(new_value){
        let new_node = new Node(new_value, null);
        if(this.head == null){
            this.head = new_node;
            return;
        }
        let last_node = this.getLast();
        last_node.next = new_node;
    }
    insertNodeAt(new_value,position_value){ 
        if(position_value == null){
            this.append(new_value);
            return;
        }
        let new_node = new Node(new_value);
        let position_node = this.findNode(position_value);
        new_node.next = position_node.next;
        position_node.next = new_node; 
    }
    findNode(value){
        let node = this.head;
        if(value == null){
            return null;
        }
        while(node.value !== value){
            node = node.next;
        }
        return node;
    }
    findPreviousNode(value){
        let node = this.head;        
        while(node.next && node.next.value !== value){            
            node = node.next;
        }
        return node;
    }
    remove(value){
        if(value == null){
            return;
        }
        let target_node = this.findNode(value);
        if(target_node === this.head){ // head 에 있는 노드를 삭제할 경우
            this.head = target_node.next;
            return;
        }
        let target_pre_node;
        target_pre_node = this.findPreviousNode(value);  
        target_pre_node.next = target_pre_node.next.next;
    }
    printValue(){
        let node = this.head;
        let arr = [];
        while(node){
            arr.push(node.value);            
            node = node.next;
        }   
        return arr.join(', ');     
    }
}
const ll = new LinkedList();
ll.append('a');
ll.append('b');
ll.insertNodeAt('aa','a');
console.log(ll.printValue());
ll.remove('aa');
console.log(ll.printValue());