[JS/Linked List] 자바스크립트로 Single Linked List 구현하기

https://im-developer.tistory.com/121?category=828401

[자료 구조] Data Structure - (1) Stack / Queue / Linked List

지난번 포스팅에서 정리한 Linked List는 대충 아래와 같이 생겼다.

 

 

Linked list는 배열과 비교했을때 특정 데이터를 검색하는데 시간이 오래 소요된다. 그 이유는 배열은 각 공간의 주소가 인덱스라는 것으로 정해져있기 때문이다. 따라서 어떤 값의 주소만 알고 있다면 값을 찾는 것은 쉽다. 그러므로 배열에서 값을 읽는 것에는 O(1)이 소요된다.

 

그러나 Linked List는 값들이 모두 링크로 연결되어있고 각 요소들은 다음 요소의 주소만을 가지고 있기 때문에 어떤 값을 찾기 위해서는 링크를 타고 가야한다. 그러므로 값을 읽으려면 최악의 경우 모든 요소를 다 검사해야하기 때문에 O(n) 시간만큼 소요된다.

 

반면 배열 중간에 어떤 요소를 삽입할 때는 배열보다 Linked List가 훨씬 간단하다. 그 이유는 배열에서는 어떤 요소를 중간에 끼워넣으면 그 요소 다음 요소들의 위치를 모두 바꿔야하기 때문이다.

그러나 Linked List에서는 중간에 삽입하더라도 바로 옆 공간에 넣을 필요가 없다. 아무데나 데이터를 넣은 다음 이전 요소가 새로운 요소를 가리키도록, 그리고 새로운 요소가 다음 요소를 가리키도록 링크의 연결만 조정해주면 쉽게 요소를 중간에 끼워넣을 수 있다. 그러므로 배열에서 요소를 중간에 삽입하는 것은 O(n)의 시간이 소요되고 Linked List에서는 O(1)이 소요된다.

 

	배열	Linked List
읽기	O(1)	O(n)
삽입	O(n)	O(1)

 

Linked List에서 특정 요소를 검색하기 위해서는 앞에서부터 탐색할수밖에 없다. 링크가 바로 다음 요소의 정보만을 가지고 있기 때문이다. 이러한 특징의 단점을 보완하기 위해서 링크가 한 방향이 아닌 양 방향을 모두 가리키고 있는 double Linked List도 있다.

 

 

 

 

아래 소스는 이 Linked List를 아주 단순하게 구현한 자바스크립트 소스이다.

한 쪽 방향의 정보만 가지고 있는 Single linked list이며

새로운 노드를 linked list 맨 마지막에 삽입하고

맨 앞의 head 노드를 삭제하고

특정 값이 이 list에 있는지 없는지 체크해주는 기능까지 구현한 소스이다.

 

var LinkedList = function() {
  var list = {};
  list.head = null;
  list.tail = null;

  list.addToTail = function(value) {
    var newNode = Node(value);

    if (! list.head) {
      list.head = newNode;
      list.tail = newNode;
    } else {
      var formerTail = list.tail;
      list.tail = newNode;
      formerTail.next = list.tail;
    }
  };

  list.removeHead = function() {
    if (list.head) {
      var prevHeadVal = list.head.value;
      list.head = list.head.next;
      if (list.head === null) {
        list.tail = null;
      }
    }
    return prevHeadVal;
  };

  list.contains = function(target) {
    var headNode = list.head;
    while (headNode) {
      if (headNode.value === target) {
        return true;
      }
      headNode = headNode.next;
    }
    return false;
  };

  return list;
};

var Node = function(value) {
  var node = {};

  node.value = value;
  node.next = null;

  return node;
};

 

 

---

 

내가 쓴 코드에 몇 가지 문제가 있어 피드백을 받았다.

 

1. !와 같은 Logical Operator는 붙여서 쓰는 것이 일반적이다.

if (! list.head)라고 썼는데 if (!list.head)가 좀 더 일반적인 방법이라고 한다. 이 부분 사실 항상 띄어쓰는 것이 좋을지 안좋을지 고민했던 부분인데 앞으로는 붙여서 써야겠다.

 

2. 아래 코드에서 list.head가 true인 경우에만 prevHeadVal 변수를 선언하고 

모든 경우에 return prevHeadVal을 하기 때문에 false인 경우에는 undefined를 리턴한다.

list.removeHead = function() {
  if (list.head) {
    var prevHeadVal = list.head.value;
    list.head = list.head.next;
    if (list.head === null) {
      list.tail = null;
    }
  }
  return prevHeadVal;
};

 

---

피드백받은 사항을 고려하여 다시 코드를 작성하였다.

 

var LinkedList = function() {
  var list = {};
  list.head = null;
  list.tail = null;

  list.addToTail = function(value) {
    var newNode = Node(value);

    if (!list.head) {
      list.head = newNode;
      list.tail = newNode;
    } else {
      var formerTail = list.tail;
      list.tail = newNode;
      formerTail.next = list.tail;
    }
  };

  list.removeHead = function() {
    if (!list.head) {
      return null;
    } else {
      var prevHeadVal = list.head.value;
      list.head = list.head.next;
      if (list.head === null) {
        list.tail = null;
      }
      return prevHeadVal;
    }
  };

  list.contains = function(target) {
    var headNode = list.head;
    while (headNode) {
      if (headNode.value === target) {
        return true;
      }
      headNode = headNode.next;
    }
    return false;
  };

  return list;
};

var Node = function(value) {
  var node = {};

  node.value = value;
  node.next = null;

  return node;
};