이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌10 - Algorithm - 2년 전 등록 / 10달 전 수정

자료구조(연결 리스트, linked list)

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요. 이번 시간부터는 잠깐 화제를 돌려 자료구조에 대해 알아보고 가겠습니다.

자료구조는 데이터의 표현 및 저장 방법을 의미합니다. 알고리즘은 그 저장된 데이터를 처리하는 과정이고요. 즉, 자료구조를 알아야 알고리즘을 배울 수 있습니다. 하지만 지금까지 우리는 자료구조를 배우지 않았는데도 알고리즘을 배웠습니다. 제가 또 거짓말을 한 걸까요? 지난 시간에 우리는 계속 자료구조를 썼습니다. 다만 그게 자료구조였다는 것을 눈치채지 못했을 뿐이죠.

바로 배열이 자료구조 중 하나입니다. 그리고 자료구조의 대부분을 혼자서 다 해먹습니다. 자료구조에는 연결리스트, 스택, 큐 등이 있는데 자바스크립트의 배열은 훌륭하게도 이 모든 것을 표현할 수 있습니다. 그래서 문제가 되는 것이 자료구조를 배울 때 자바스크립트는 도움이 되지 않습니다. 이미 만능 배열이 있거든요. 굳이 연결리스트, 스택, 큐를 직접 구현할 필요가 적습니다. 하지만 그렇다고 해서 배울 필요가 아예 없다는 것은 아닙니다.

이번 시간에는 가장 기본인 연결 리스트에 대해 배워봅시다. 연결 리스트는 여러 개의 노드로 이루어져 있습니다. 각각의 노드는 데이터와 다음 노드가 뭔지 알려주는 주소를 가지고 있습니다. 또한 연결 리스트는 새로운 데이터를 추가하거나, 데이터의 위치를 찾거나, 제거하는 기능이 있어야 합니다.

1->2->3->4->5 라는 연결 리스트가 있다면 1,2,3,4,5는 데이터고 ->는 주소입니다. 안타깝게도, 이미 자바스크립트에는 이것이 구현되어 있습니다. 바로 배열입니다. [1,2,3,4,5]가 있으면 1,2,3,4,5는 데이터이고, array[0], array[1] 등은 데이터가 담긴 위치를 말해주고 있죠. 또한, array.push();를 통해 데이터를 추가할 수 있고, array.splice();를 통해 데이터를 제거할 수 있습니다.

하지만 이렇게 바로 배열을 써버리면 공부가 안 되겠죠? 우리는 조금 고통을 받더라도 객체를 통해 직접 구현할 겁니다. 즉, 자바스크립트의 배열을 우리 손으로 직접 만드는 과정입니다.

일단 연결 리스트와 노드를 만들어봅시다.

var LinkedList = (function() {
  function LinkedList() {
    this.length = 0;
    this.head = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  return LinkedList;
})();

LinkedList에는 length와 head가 있습니다. length는 노드의 개수를 표현하는 부분이고, head가 바로 첫 노드의 주소를 가리키는 부분입니다. 이제 데이터를 추가, 검색, 삭제하는 메소드를 구현해봅시다.

var LinkedList = (function() {
  function LinkedList() {
    this.length = 0;
    this.head = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  LinkedList.prototype.add = function(value) {
    var node = new Node(value);
    var current = this.head;
    if (!current) { // 현재 아무 노드도 없으면
      this.head = node; // head에 새 노드를 추가합니다.
      this.length++;
      return node;
    } else { // 이미 노드가 있으면
      while(current.next) { // 마지막 노드를 찾고.
        current = current.next;
      }
      current.next = node; // 마지막 위치에 노드를 추가합니다.
      this.length++;
      return node;
    }
  };
  LinkedList.prototype.search = function(position) {
    var current = this.head;
    var count = 0;
    while (count < position) { // position 위치만큼 이동합니다.
      current = current.next;
      count++;
    }
    return current.data;
  };
  LinkedList.prototype.remove = function(position) {
    var current = this.head;
    var before;
    var remove;
    count = 0;
    if (position == 0) { // 맨 처음 노드를 삭제하면
      remove= this.head;
      this.head = this.head.next; // head를 두 번째 노드로 교체
      this.length--;
      return remove;
    } else { // 그 외의 다른 노드를 삭제하면
      while (count < position) {
        before = current;
        remove = current.next;
        count++;
        current = current.next;
      }
      before.next = remove.next;
      // remove 메모리 정리
      this.length--;
      return remove;
    }
  };
  return LinkedList;
})();

물론 추가할 때는 굳이 마지막에 추가하지 않아도 되고, 중간에 끼워넣는다든지, 맨 처음에 끼워넣어도 되겠죠? 직접 구현해보세요. 이제 테스트를 한 번 해볼까요?

var list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.length; // 3
list.search(0); // 1
list.search(2); // 3
list.remove(1);
list.length; // 2

배열과 비슷하게 동작하는 것을 확인할 수 있습니다. 특수한 연결 리스트도 있습니다. 현재 연결 리스트는 한 쪽 방향으로만 이동합니다. 그래서 다시 뒤로 가기는 불편하죠. 이걸 해결한 리스트가 이중 연결 리스트입니다. next외에 this.prev를 넣어 이전 노드를 가리키게 한 겁니다. 구현은 조금 더 복잡해지지만, 한 번 구현하면 그 뒤로는 편하게 앞과 뒤로 노드를 왔다갔다할 수 있습니다. 또 지금은 하나의 데이터씩만 연결되지만 한 노드에서 여러 노드를 연결하는 다중 연결 리스트도 있습니다. this.next를 노드들의 배열로 만들면 되겠죠? 필요에 따라 조금씩 변형해서 쓰시면 됩니다.

다음 시간에는 스택에 대해서 알아보겠습니다!

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

2개의 댓글이 있습니다.
10달 전
remove 기능에서 while(count< position) { 아랫줄에 current = current.next; 가 빠진 것 같습니다!
10달 전
감사합니다~
일 년 전
LinkedList.length 값은 length가 예약어여서 값이 제대로 반영되지 않습니다. (node v7.3.0 에서 테스트)
일 년 전
음 이상하네요. length는 배열이나 유사배열일 경우만 예약어이거든요. node v7.10.0에서 해봤는데 잘 작동합니다.