Linked List 구현

• 개념 이해에 도움이 되었던 링크

  Linked List는 사실 JS에서는 실감하기 어려운 데이터 구조이다. 왜냐면 linked list보다 훨씬 편한 array라는 데이터 타입이 있기 때문이다. 특정 인덱스도 각각 배정되어 있고, 배열 전체가 연결되어 있다. 그러나 linked list는 서로 분산된 데이터들을 일부러 pointer로 연결한 개념이기 때문에 순회하는 것도, 특정 인덱스의 값을 찾는 것도 까다롭다.

  그럼에도 불구하고 알아야할 필요성을 점점 느끼는 것은 다른 데이터 구조도 결국에는 linked list 개념을 바탕으로 만든 것이 많기 때문이다.(Tree, graph 등등) 또한 JS 외에 C 처럼 미리 선언할 때 메모리를 할당해주는 언어의 경우는 필수적인 데이터 구조라고 생각한다.

  하지만 평소에 array에만 익숙해진 나로서는 너무 익숙하진 않은 패턴이었다.

일단 기본적으로 제공되었던 코드는 아래와 같다

class Node {  
//선형노드 방식 
//노드를 만드는 cunstructure. 각각의 노드는 value와 다음 노드를 가리키는 포인터가 있음.
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }
};

코드 분석

제공된 코드를 이용해서 LinkedList 객체의 메소드를 구현해야 한다.

제일 먼저 헤멨던 것은 이것이 singly linked list 인지 doubly linked list인지 정확하게 구분이 되지 않았다는 것이었다. LinkedList의 포인터가 head와 tail 두개가 있었기 때문이다. 각각의 포인터와 어떤 종류인지를 페어와 함께 거의 반나절을 헤메다가 기본 제공된 코드를 다시 정독해 보고서나 singly linked list임을 이해하였다.

기본 제공된 class를 살펴보면 LinkedList를 이용해서만 구현하는 것이 아니라 크게는 LinkedList를 이용하지만 내부적인 node들은 Node 객체를 이용해서 구현되는 것이었다. 즉 head와 tail은 전체 linked list의 처음과 끝을 의미하는 것이었고 실질적으로 데이터를 연결하는 포인터는 Node 객체의 next 하나였던 것이다.

때문에 대략적인 결과를 그려보자면

node 1개 : [head] → node ←[tail] head와 tail 모두 node를 가리킴

node 2개 : [head] → node 1 -(next)→node 2 ←[tail]

node 3개 : [head] → node 1 -(next)→node 2 -(next)→node 3←[tail]

의 형태로 진행된다. 즉 haed 포인터는 제일 앞에 고정되고, 모든 데이터들이 haed에 담겨있다. 이 데이터들은 next를 이용해서만 연결되는 구조이다.

좀더 실질적으로 표현을 해보자면

• 첫 LinkedList 실행 : LinkedList {head: null, tail: null, _size: 0}

• 노드 두개 추가 : {head: Node, tail: Node, _size: 2}

  

• 노드 세개 추가 : {head: Node, tail: Node, _size: 3}

이런식으로 객체 안에 객체가 있는 모습이다.