[자료구조] Linked List in JavaScript

정의

배열과 마찬가지로 선형 구조를 가지는 자료구조. Linked List(연결 리스트)에서 Element는 'Node'라고 한다. 순차적으로 저장되는 배열과 달리 각 Node는 'Data(자료)'와 다음 Node를 가리키는 'Pointer'로 구성되어 있다.

 

위키백과 정의를 보자.

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.
연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.
연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

---

연산

1. addToTail() 새로운 노드를 이전 노드의 포인터에 연결한다. 
2. remove(data) data가 일치하는 노드를 삭제한다.
3. getNodeAt(index) 해당 index의 노드를 return 한다.
4. contains(data) data가 있으면 true를, 없으면 false를 반환한다.  
5. indexOf(data) data가 위치한 노드의 index를 반환한다.
6. size() 노드의 크기를 반환한다.

---

구현

addToTail 연산이 일어날 때마다 새로운 노드가 추가되기 때문에 class로 만들어 준다.

class Node {
  constructor(data) { //노드는 생성될 때 data와 다음 노드를 가리키는 pointer를 가진다
    this.data = data;
    this.pointer = null;
  }
}

const linkedList = {
    head: null,
    size: 0;
 }

addToTail()

const addToTail = (data) => {
    let node = new Node(data);
    let currentNode;

    if (linkedList.head === null) {
      linkedList.head = node;
    } else {
      currentNode = linkedList.head;
      while (currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }
    linkedList._size++;
  }

remove(data)

const remove = (data) => {
    let current = linkedList.head;

    while (current) {
      if (current.data === data) {
        linkedList.head = current.next;
        linkedList._size--;
      }
      current = current.next;
    }
    return -1;
 }

getNodeAt(index)

 getNodeAt(index) {
    let count = 0; //연결리스트의 index를 확인하기 위한 변수
    let current = linkedList.head;

    while (current !== null) {
      if (count === index) { //일치하는 노드를 반환해준다.
        return current;
      } else {
        current = current.next;
        count++;
      }
    }
  }

contains(data)

 contains(data) {
    let current = linkedList.head;

    while (current.next) { // 자식 노드가 있을 경우에만 실행
      if (current.data === data) {
        return true;
      }
      current = current.next;
    }
    return false;
  }

indexOf(data)

 indexOf(data) {
    let index = 0;
    let current = linkedList.head;

    while (current !== null) {
      if (current.data === data) return index; //data가 일치하면 index를 반환한다.
      index++;
      current = current.next;
    }
    return -1;
  }

size()

const size = () => (linkedList.size)