본문 바로가기
Computer Science/Algorithm, Data Structure

자바스크립트 자료구조 연결 리스트(Linked List)

by Write and Remember 2019. 5. 26.

 

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

 

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

 

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

 

출처: Wikipedia

 

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

 

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

 

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

 

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

 

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

 

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

 

출처: Wikipedia

 

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

 

출처: Wikipedia

 

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

 

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

 

function LinkedList() {
  this.length = 0;
  this.head = null;
}

LinkedList.prototype = {
  add(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(position) {
    let current = this.head
    let count = 0;
    while (count < position) {
      current = current.next
      count++;
    }
    return current.data;
  },

  remove(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 linkedList = new LinkedList();

linkedList.add(1) // 1 첫번째 노드에 1 추가
linkedList.add(2) // 2 두번째 노드에 2 추가
linkedList.add(3) // 3 세번째 노드에 3 추가
linkedList.find(0) // 1 첫 번째 노드 검색
linkedList.remove(1) // 두 번째 노드 2 삭제
linkedList.find(0) // 1
linkedList.find(1) // 3 
linkedList.length // 2

 

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

 

코드를 살펴보면,

 

LinkedList라는 생성자 함수를 선언한다.

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

댓글0