[Javascript] Linked List( 링크드 리스트) 자바스크립트 구현

0. 목차

1. 개요

2. 노드 구현

3. 링크드 리스트 구현

1. 개요

링크드 리스트란?

링크드 리스트(Linked List)란 노드(Node)들로 이어진 리스트를 말한다.

노드는 보통 데이터를 저장하는 부분과, 다음 노드를 가리키는 부분으로 구성된다.

 

때문에, 배열(Array)에 비해 Node의 삽입과 삭제에 용이 하다

 

2. 노드 구현

 

class Node {
  constructor(data, nextNode = null) {
    this.data = data;
    this.nextNode = nextNode;
  }

노드 구현은 매우 간단하다.
입력받은 data를 Node 의 데이터로 넣어주고,
nextNode는 입력받지 못한경우에는 null을 넣어준다.

3. 링크드리스트 구현

블로그를 몇개 뒤져보니 링크드 리스트를 구현 할 때
필수적으로 넣는것은 head 가 있었고,(당연)

부가적으로 tail 또는 size를 넣는 경우가 있던데,
나는 tail 과 size를 모두 넣어서 구현 해봤다.

  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

여기서 head는 링크드 리스트의 첫번째 노드를
tail은 링크드 리스트의 마지막 노드를 나타낸다.
그리고 size는 링크드 리스트를 구현하고 있는 node의 갯수를 나타낸다.

구현한 기능들은 아래와 같다.

1. log()

: 링크드 리스트를 구성하는 모든 노드의 데이터를 출력한다.

  log = () => {
    let node = this.head;
    while (node !== null) {
      console.log(node.data);
      node = node.nextNode;
    }
  };

2. unshiftNode(data)

: 링크드 리스트의 첫번째 노드를 삽입한다, 기존에 노드가 존재하면 삽입된 노드에 연결해준다. head가 변경된다.

  unshiftNode = (data) => {
    const newNode = new Node(data, this.head);
    this.head = newNode;
    if (this.tail === null) {
      // 기존의 링크드 리스트가 비어있었을 경우
      this.tail = newNode;
    }
    this.size++;
  };

3. pushNode(data)

: 링크드 리스트의 마지막 노드를 삽입한다. tail이 변경된다.

  pushNode = (data) => {
    const newNode = new Node(data);

    if (this.size === 0) {
      // 기존의 리스트가 비어있었을 경우
      this.head = newNode;
    } else {
      let tmpNode = this.head;

      while (tmpNode.nextNode !== null) {
        tmpNode = tmpNode.nextNode;
      }

      tmpNode.nextNode = newNode;
      this.tail = newNode;
    }

    this.size += 1;
  };

4. insertNode(data,idx)

: 링크드 리스트의 idx번째 자리에 노드를 삽입한다. 기존의 노드 연결을 변경한다.

  insertNode = (data, idx) => {
    if (idx < 0 || idx > this.size) {
      // idx 가 리스트의 범위를 벗어났을 경우
      console.log('인덱스 에러');
      return;
    }

    const newNode = new Node(data);

    if (idx === 0) {
      // idx가 0일때는 새로운 노드의 nextNode 만 신경쓰면 된다.
      newNode.nextNode = this.head;
      this.head = newNode;
      this.size += 1;
      return;
    }

    let count = 0;
    let tmpNode = this.head;

    while (count <= idx) {
      count += 1;
      if (count === idx) {
        newNode.nextNode = tmpNode.nextNode;
        tmpNode.nextNode = newNode;
        if (idx === this.size - 1) {
          // 마지막 Node로 삽입될 경우
          this.tail === newNode;
        }
        this.size += 1;
        return;
      }
      tmpNode = tmpNode.nextNode;
    }
  };

5. getDataAt(idx)

: idx번째 노드의 data를 리턴 한다.

  getDataAt = (idx) => {
    if (idx < 0 || idx >= this.size) {
      console.log('인덱스 에러');
      return;
    }

    let tmpNode = this.head;
    let count = 0;

    while (count < idx) {
      tmpNode = tmpNode.nextNode;
      count += 1;
    }

    return tmpNode.data;
  };

6. removeNodeAt(idx)

: idx 번째 Node를 삭제한다.

  removeNodeAt(idx) {
    if (idx < 0 || idx >= this.size) {
      console.log('인덱스 에러');
      return;
    }

    if (idx === 0) {
      this.head = this.head.nextNode;
    } else {
      let tmpNode = this.head;
      let count = 0;
      while (count < idx) {
        count += 1;
        if (count === idx) {
          tmpNode.nextNode = tmpNode.nextNode.nextNode;
          if (idx === this.size - 1) {
            // 리스트의 마지막 노드가 삭제되었을 경우
            this.tail = tmpNode.nextNode || tmpNode;
                // node가 하나일 경우 tail 은 tmpNode 가 된다. 
          }
        }
        tmpNode = tmpNode.nextNode;
      }
    }

    this.size -= 1;
    if (this.size === 0) {
      //삭제 후 리스트가 빈경우
      this.tail = null;
    }
  }

의식의 흐름대로 짜서 코드가 좀 너저분 하긴한데, 그래도 기술한데로 기능은 모두 잘 돌아간다.

전체코드는 깃허브에 올려둘거임.