(data-structure) Linked List(연결 리스트) 코드로 구현하기

연결리스트 구현하기

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

linked List에는 length와 head가 있다. length는 노드의 개수를 표현하는 부분이고, head가 바로 첫 노드의 주소를 가리키는 부분이다.

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 { // 이미 노드가 있다면 
      whie(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;
    var count = 0;
    if (position === 0) { // 맨 처음 노드를 삭제하면 
      remove = this.head;
      this.head = this.head.next; // head를 두 번째 노드로 교체 
      this.length++;
      return remove;
    } else { // 그 외의 다른 노드를 삭제하면 
      while (count < position) {
        before = current;
        count++
        current = current.next;
      }
      remove = current;
      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를 넣어 이전 노드를 가리키게 한것) 이외에도 다중 연결 리스트도 있다.

출처

자료구조(연결리수트, 제로초 블로그)