ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 자바스크립트 자료구조 연결 리스트(Linked List)
    Computer Science/Algorithm, Data Structure 2019.05.26 20:36

     

    모든 자바스크립트 개발자가 알아야 하는 33가지 개념

     

    지난 글에서 Stack과 Queue에 대해 알아보았고

     

    오늘은 연결 리스트(Linked List)를 알아보자.

     

    출처: Wikipedia

     

    배열과 마찬가지로 연결 리스트는 데이터를 순차적으로 저장한다.

     

    연결 리스트는 색인(index)을 유지하는 대신 다른 요소에 대한 포인터를 보유한다.

     

    우선 단일 연결 리스트(단방향) 생각해보자.

     

    첫 번째 노드(데이터를 저장)는 머리(head), 마지막 노드는 꼬리(tail)라 한다.

     

    첫 번째 노드가 다음 노드를 가리키고 이어서 또 다음 노드를 가리키는 방식이다.

     

    노드는 데이터를 저장할 공간과 다음 노드의 포인터 공간으로 나누어진다.

     

    출처: Wikipedia

     

    이중 연결 리스트(양방향)는 이전 노드, 다음 노드 주소를 함께 저장한다.

     

    출처: Wikipedia

     

    원형 연결 리스트는 단일 연결 리스트에 마지막 노드와 처음 노드를 연결시킨 원형 구조다.

     

    스택과 큐보다 구현하기가 까다롭지만 단일 연결 리스트를 천천히 구현해 보자.

     

    function LinkedList() {
      this.length = 0;
      this.head = null;
    }
    
    LinkedList.prototype = {
      add: function(data) {
        const node = {
          data: data,
          next: null
        }
        let current;
    
        if (this.head === null) {
          this.head = node;
        }
        else {
          current = this.head
    
          while (current.next) {
            current = current.next
          }
          current.next = node;
        }
    
        this.length++;
      },
    
      find: function(position) {
        let current = this.head
        let count = 0;
        while (count < position) {
          current = current.next
          count++;
        }
        return current.data;
      },
    
      remove: function(position) {
        let current = this.head;
        let before;
        let remove;
        let count = 0;
        if (position === 0) {
          remove = this.head;
          this.head = this.head.next
          this.length--;
          return remove;
        } else {
          while (count < position) {
            before = current;
            count++;
            current = current.next
          }
          remove = current;
          before.next = remove.next;
    
          this.length--;
          return remove;
        }
      }
    }
    
    const list = new LinkedList();
    
    list.add(1) // 1 첫번째 노드에 1 추가
    list.add(2) // 2 두번째 노드에 2 추가
    list.add(3) // 3 세번째 노드에 3 추가
    list.find(0) // 1 첫 번째 노드 검색
    list.remove(1) // 두 번째 노드 2 삭제
    list.find(0) // 1
    list.find(1) // 3 
    list.length // 2
    

     

    위의 방법말고도 다양한 방법이 있고 클래스를 사용해서도 구현 가능하다.

     

    코드를 살펴보면,

     

    LinkedList라는 함수를 생성한다.

     

    length는 노드의 개수, head는 첫 노드의 포인터(주소)이다.

     

    이 함수의 프로토타입으로 add(추가), find(탐색, remove(제거) 메서드를 생성한다.

     

    add 메서드는 data를 추가하고 current라는 변수를 선언하고 이미 노드가 있다면

     

    while로 마지막 노드를 찾고 그 위치에 노드를 추가하는 역할을 수행한다.

     

    find 메서드는 들어오는 position(값)의 노드를 찾아 들어있는 데이터를 반환한다.

     

    remove 메서드는 들어오는 position(값)의 노드를 제거하고

     

    만약 중간 노드를 삭제한다면 이전 노드와 나머지 노드를 연결하는 역할을 한다.

     

    2학년 1학기 자료구조 수업에서

     

    연결 리스트를 C언어로 구현하는게 너무 힘들었는데

     

    아직도 구현하기가 힘들다.

     

    다음은 Hash Table에 대해 알아보자.

    댓글 0

Posted by JeongWoo