자료구조

자료구조

harugi7 1개월 전

*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다.

 

Linked List 구현 (JS)

추상자료형

어떠한 데이터와 그 데이터에 대한 연산을 표기하는 것이야.

 

연결리스트의 추상자료형

  1. 모든 데이터 출력 - printAll()

  2. 모든 데이터 제거 - clear()

  3. 인덱스 삽입 - insertAt(index, data);

     

  4. 마지막 삽입 - insertLast(data);

     

  5. 인덱스 삭제 - deleteAt(index);

  6. 마지막 삭제 - deleteLast();

  7. 인덱스 읽기 - getNodeAt(index);

 구현

이제 위 추상자료형을 바탕으로 구현을 해보자.

연결리스트는 데이터를 담은 노드를 서로 연결하는 구조야. 이를 위해서 가장 먼저 만들어야하는 것은 노드겠지?

  • 노드

     

    class Node{
    // 생성자의 매개변수로 data, next를 만들어준다.
    // 매개변수 data는 필수이지만,
    // next는 입력하지 않는다면 null이 할당된다.
    constructor(data, next = null){
        this.data = data;
        this.next = next;
    }
} 

    아래와 같이 자기 참조 변수를 만들어준 후 추상자료형에서 나열한 함수들을 만들어볼게.

    class LinkedList{
    constructor(){
        this.head = null; // 연결리스트의 시작 노드
        this.count = 0; // 총 저장된 노드의 수
    }

  • insertAt(index, data);

insertAt(index, data){
        // 예외 처리
        if(index > this.count || index < 0){
            throw new Error("범위를 넘어갔습니다.");
        }

        let newNode = new Node(data);

        // 리스트의 가장 앞부분에 삽입하는 경우
        if(index == 0){
            newNode.next = this.head; // next 노드 설정
            this.head = newNode; // 새 노드를 head로 설정
        } else {
            // 목표 index의 전 노드까지 도달
            let currentNode = this.head;

            for(let i = 0; i < index - 1; i++){
                currentNode = currentNode.next;
            }
            newNode.next = currentNode.next; // next 노드 설정
            currentNode.next = newNode; // 전 노드와 연결
        }
        this.count++;
    }

  • printAll()

printAll(){
    let currentNode = this.head;
    let text = "[";

    while(currentNode != null){
        text += currentNode.data;
        currentNode = currentNode.next;

        if(currentNode != null){
            text += ", ";
        }
    }

    text += "]";
    console.log(text);
}

  • clear()

clear(){
    this.head = null;
    this.count = 0;
}

  • insertLast(data);

     

    insertLast(data){
        // insertAt(index, data)
        this.insertAt(this.count, data);
    }

  • deleteAt(index);

deleteAt(index){
    // 예외 처리
    if(index >= this.count || index < 0){
        throw new Error("제거할 수 없습니다.");
    }

    let currentNode = this.head;

    if(index == 0){ // 첫번째 노드를 제거하는 상황
        let deletedNode = this.head;
        this.head = this.head.next; // head 노드 변경
        this.count--; // count 줄여줌
        return deletedNode;
    } else {
        for(let i = 0; i < index - 1; i++){ // 제거할 노드의 이전 노드까지 순회
            currentNode = currentNode.next;
        }

        let deletedNode = currentNode.next;
        currentNode.next = currentNode.next.next; // 노드 연결
        this.count--;
        return deletedNode;
    }
}

  • deleteLast();

deleteLast(){
    return this.deleteAt(this.count - 1);
}

  • getNodeAt(index);

getNodeAt(index){
    // 예외 처리
    if(index >= this.count || index < 0){
        throw new Error("범위를 넘어갔습니다.");
    }

    let currentNode = this.head;
    for(let i = 0; i < index; i++){
        currentNode = currentNode.next;
    }

    return currentNode;
}

 스택

FILO의 리스트 형태야. ctrl+z를 구현할 때 스택이 사용되지!

FILO의 조건만 충족한다면 어떤 자료구조로 구현하던지 상관없어.

즉, 배열이나 연결리스트 각각으로 스택을 구현할 수 있어. 지금은 만들어놓은 연결리스트로 스택을 구현해볼게.

새로 들어온 노드를 head로 지정해주면 돼.

 

스택의 추상자료형

push - 데이터 삽입

pop - 데이터 제거

peek - 데이터 참조

isEmpty - 비었는지 체크

 

구현

class Stack{
    constructor(){
        this.list = new LinkedList();
    }

    push(data){
        // 0 인덱스에 data 삽입
        this.list.insertAt(0, data);
    }

    pop(){
        try{
            return this.list.deleteAt(0);
        } catch(e){ // 빈 리스트 지울 경우
            return null;
        }
    }

    peek(){
        return this.list.getNodeAt(0);
    }

    isEmpty(){
        return (this.list.count == 0);
    }
}


큐

FIFO의 형태야. 마찬가지로 연결리스트로 구현해보자.

이번에도 삽입하는 노드를 head로 지정하는 대신, 삭제하기 쉽도록 tail 이라는 변수를 하나 더 만들어서 가장 처음 삽입한 노드를 가리키도록 하자.

이렇게했을때 처음 삽입한 노드를 삭제하게되면 tail은 전 노드를 가리켜야해.

하지만 우리는 단방향 연결리스트를 구현했기 때문에 전 노드를 알 수 없어. 즉, 이중연결리스트로 수정해야해!

 큐의 추상자료형

enqueue - 데이터 삽입

dequeue - 데이터 제거

front - 데이터 참조

isEmpty - 비었는지 확인

DoublyLinkedList.mjs

  • node 수정

     

class Node{
    constructor(data, next = null, prev = null){
        this.data = data;
        this.next = next;
        this.prev = prev; // 이전 노드 추가
    }
}

  • 프로퍼티 추가

class DoublyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null; // tail 추가
        this.count = 0;
    }

  • insertAt(index, data) 수정

    • 데이터가 삽입될 때 이전 노드를 가리키는 코드를 추가하자.

insertAt(index, data){
    if(index > this.count || index < 0){
        throw new Error("범위를 넘어갔습니다.");
    }

    let newNode = new Node(data);

    if(index == 0){ // head에 삽입하는 경우
        newNode.next = this.head;
        if(this.head != null){
            this.head.prev = newNode;
        }
        this.head = newNode;
    }else if(index == this.count){ // tail에 삽입하는 경우
        newNode.next = null;
        newNode.prev = this.tail;
        this.tail.next = newNode;
    }else {
        let currentNode = this.head;

        for(let i = 0; i < index - 1; i++){
            currentNode = currentNode.next;
        }
        newNode.next = currentNode.next;
        newNode.prev = currentNode;
        currentNode.next = newNode;
        newNode.next.prev = newNode;
    }

    if(newNode.next == null){ // 새로 삽입한 노드가 마지막 노드라면
        this.tail = newNode;
    }
    this.count++;
} 

  • deleteAt(index) 수정

deleteAt(index){
    if(index >= this.count || index < 0){
        throw new Error("제거할 수 없습니다.");
    }

    let currentNode = this.head;

    if(index == 0){
        let deletedNode = this.head;
        if(this.head.next == null){ // 데이터가 1개일 때
            this.head = null;
            this.tail = null;
        } else {
            this.head = this.head.next;
            this.head.prev = null;
        }
        this.count--;
        return deletedNode;
    } else if(index == this.count - 1){ // 마지막 노드를 제거할 경우
        let deletedNode = this.tail;
        this.tail.prev.next = null;
        this.tail = this.tail.prev;
        this.count--;
        return deletedNode;
    } else {
        for(let i = 0; i < index - 1; i++){
            currentNode = currentNode.next;
        }

        let deletedNode = currentNode.next;
        currentNode.next = currentNode.next.next;
        currentNode.next.prev = currentNode;
        this.count--;
        return deletedNode;
    }
}

 Queue.mjs

class Queue{
    constructor(){
        this.list = new DoublyLinkedList();
    }

    enqueue(data){ // 데이터 삽입
        this.list.insertAt(0, data);
    }

    dequeue(){ // 데이터 제거
        try{
            return this.list.deleteLast();
        } catch(e){
            return null;
        }
    }

    front(){ // 데이터 참조
        return this.list.tail;
    }

    isEmpty(){ // 비었는지 확인
        return (this.list.count == 0);
    }
}

 

 

 

 

 

참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

  • 2주차 회고

    • 칭찬하고 싶은 점 : 기한을 지켰다 😅

    • 아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.

    • 다음 주에는 권장 커리큘럼을 지켜 수강하는 것이 목표입니다!

댓글을 작성해보세요.

채널톡 아이콘