자료구조 with javascript

0. 서론

코딩테스트를 조금씩 준비하려고 한다. 비록 자료구조는 학부생때 C++로 배웠지만 기억이 나지 않고 내 주 언어인 자바스크립트로 자료구조를 다시한번 정리하려고 한다.

대표적인 자료구조

• 스택
• 큐
• 트리
• 리스트
• 맵
• 셋

1. stack

스택은 LIFO (Last in, First Out) 구조를 가지며 선형 자료형이다.
js에서는 배열을 통해 간단히 구현할 수 있으며, 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek등의 작업이 가능하다.

const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);

console.log(`push fin ${stack}`);

stack.pop(); //3
console.log(`pop3 ${stack}`);
stack.pop(); //2
console.log(`pop2 ${stack}`);
stack.pop(); //1
console.log(`pop1 ${stack}`);

2. Queue

큐는 FIFO(First in, First Out) 구조를 가진다.
큐 또한 js에서 array로 구현이 가능하다.
큐의 enqueue는 push로 deque구현한데 dequeue는 shift를 쓴다
큐는 맨 앞의 요소를 방출하기 때문에 shift를 사용한다.

const queue=[];

queue.push(1);//enqueue
queue.push(2);//enqueue
queue.push(3);//enqueue

queue.shift(); //dequeue 1
queue.shift(); //dequeue 2
queue.shift(); //dequeue 3

3. Linked List

연결리스트는 모든 요소가 다음 요소에 연결된 자료구조다.
노드마다 연결되어있고 각 노드에 노드의 현재값과 다음값, 이전값(이중연결리스트)가 있다.
자료가 연결되어 있기때문에 새로운 자료를 앞쪽에 추가/삭제할때 굉장히 유용하며, 이중연결리스트일 경우 이전페이지,다음페이지 처럼 리스트형태로 연결할 때 사용한다.

하지만 특정 자료를 찾기 까다롭다는 단점이 있는데, 3번 데이터를 찾으려면 무조건 1번 2번을 거쳐야 한다는 단점이 있다. 만약, 이 요소가 많을경우 굉장히 비효율적으로 되는데 이럴 경우 array를 이용하는 편이 더 효율적이라고 볼 수 있다.

단일 연결 리스트

자바스크립트는 객체로 연결리스트를 구현할 수 있다.

const n1={
    data:100
}
const n2={
    data:200
}

n1.next=n2;

console.log(n1);
console.log(n2);

class를 이용해 구현할 수 있다.

class Node{
    constructor(data,next=null){
        //data와 next를 넣고 next의 기본값을 null로 지정, linkedlist의 마지막의 next는 null이기 때문
        this.data=data;
        this.next=next;
    }
}

class LinkedList{
    constructor(){
        this.head=null;//처음 데이터가 없다면 head는 null이다.
        this.size=0;
    }

    //맨 앞에 삽입
    insertFirst(data){
        this.head=new Node(data,this.head)
        //헤드에 새로운 노드가 들어가며 next는 기존의 head가 된다.
        this.size++;
    }

    //마지막 삽입
    insertLast(data){
        let node = new Node(data);//마지막 데이터이므로 next의 default값인 null로 된다.

        // 빈 배열일 경우 헤드 생성
        if(!this.head){//head의 값이 없을 경우
            this.head=node;//지금 삽입된 값이 헤드가 됨
        }else{
            current=this.head; //값이 있을 경우 current 변수에 헤드값을 정의해줌

            while(current.next){//current값에 next가 있다면, 즉 next가 null이 아니라면
                current=current.next //current값에 current.next를 넣어준다.
            }// 위 작업을 current.next가 없을 때까지 반복한다, 즉 리스트의 맨 끝까지 반복한다.
            current.next=node; // 결국 마지막노드에 도달했을 때 next를 새로운 노드로 설정해준다.
        }
        this.size++;
    }

    //중간 삽입
    insertAt(data,index){
        if(index<0&&index>this.size){
            return;
        }//인덱스가 노드의 size범위를 넘어서면 아무것도 리턴하지 않음

        //첫번째에 삽입
        if(index===0){
            this.head=new Node(data,this.head)//insertfirst메소드랑 동일
            this.size++;
            return;
        }


        const node=new Node(data);
        let current,previous;

        current=this.head; //current변수에 헤드값 적용(검사값이라 생각하면 됨)
        let count=0;

        while(count<index){
            previous=current;//previous변수에 헤드값이 들어간 current 삽입
            count++;
            current=current.next;//검사값에 다음 검사할 값 넣어줌(next)
        }//위 함수를 입력하려는 인덱스 값 이전까지 해준다.

        node.next=current; //node는 중간에 삽입되므로 다음 검사값을 next에 넣어주고
        previous.next = node;//node의 이전값으로 previous가 설정된다

        this.size++; //리스트가 만들어졌으니 사이즈 증가
    }


    //해당 인덱스의 값을 가져오는 메소드
    getAt(index){
        let currnet = this.head;
        let count=0;

        while(current){ //current.next가 null이 될때까지(끝까지)
            if(count==index){
                console.log(current.data);
            }
            count++;
            current=current.next;
        }
        return null;
    }

    removeAt(index){
        if(index<0&&index>this.size){
            return;
        }

        let current=this.head;
        let previous;
        let count=0;

        //첫 번쨰 인자를 삭제할경우
        if(index===0){
            this.head=current.next;//맨 첫번째 인자를 삭제했으므로 한 칸씩 뒤로 밀림
        }else{
            //첫번째 인자가 아닐경우
            while(count<index){//입력받은 인덱스 번호까지 찾음
                count++;
                previous=current;
                current=current.next;
            }
            previous.next=current.next;//중간값이 삭제 되었으므로 이전값의 다음값은 현재값의 다음값이 된다.
        }
        this.size--;
    }

    
}