Linked List

연결 리스트는 노드의 연결로 이루어진 자료구조로 각각의 노드는 데이터와 다음 노드의 주소를 가지고 있어 서로를 연결한다.
노드는 크기가 동적인 자료구조로, 자료구조를 구성하는 요소이다.

Linked List 구현

• Linked List 메서드

  1. addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가한다.
  2. remove(value) - 주어진 값을 연결 리스트에서 제거한다.
  3. getNodeAt(index) - 주어진 index의 노드를 찾아 반환한다, 해당 index에 노드가 존재하지 않는 다면 undefined를 반환한다.
  4. contains(value) - 주어진 값을 가지고 노드의 존재여부를 반환한다.
  5. indexOf(value) - 주어진 값의 index를 반환한다. 없을 경우 -1을 반환한다.
  6. size() - Node의 size를 반환한다.

  1. addToTail(value)

  

  위 그림과 같이 새로운 노드를 추가를 하게되면 b는 c를 바라보게 되고 c가 tail이 되면서 c의 next는 null이 된다.

addToTail(value) {
    const node = new Node(value);
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this._size++;
    return this;
  }

2. remove(value)

위 그림과 같이 tail에 값을 삭제하면 그 이전의 node가 tail이 되고 next는 null이 된다.

remove(value) {
    if (this.head === null) {
      return undefined;
    } else if (value === this.head.value) {
      this.head = this.head.next;
    } else {
      this.head.next = this.head.next.next;
    }
    this._size--;
  }

3. getNodeAt(index)

  getNodeAt(index) {
    let count = 0;
    let node = this.head;
    while (count !== index) {
      count++;
      node = node.next;
      if (index > this._size) {
        return undefined;
      }
    }
    return node;
  }

4. contains(value)

contains(value) {
    let count = 0;
    let node = this.head;
    while (node.value !== value) {
      count++;
      node = node.next;
      if (this._size <= count) {
        return false;
      }
    }
    return true;
  }

5. indexOf(value)

  indexOf(value) {
    let count = 0;
    let node = this.head;
    while (node.value !== value) {
      count++;
      node = node.next;
      if (this._size <= count) {
        return -1;
      }
    }
    return count;
  }

추가로 할 수 있는 작업

• 원하는 index에 node추가하기
• 중간 값 remove하기
• 양뱡향 Linked List 구현하기