javaScript로 Linked list 구현

연결 리스트(linked list)

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

단일 연결 리스트의 구조(출처:위키백과)

• 배열과 달리 원소 추가/삭제 시 다른 원소들을 움직이지 않아도 된다는 장점이 있다
• 원소를 찾을 때까지 처음(head)부터 루프를 반복해야 한다

메서드

• append(원소) : 리스트의 맨 끝에 원소 추가
• insert(위치, 원소) : 해당 위치에 원소 삽입
• remove(원소) : 원소 삭제
• indexOf(원소) : 해당 원소의 인덱스 반환, 존재하지 않을 경우 -1을 반환
• removeAt(위치) : 해당 위치의 원소 삭제
• isEmpty() : 원소가 하나도 없으면 true, 아니면 false를 반환
• size() : 원소의 개수 반환
• getHead() : head 노드 반환

구현

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

  append(element) {
    let node = new this.Node(element);
    let current;

    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }

  removeAt = function (position) { //삭제할 원소의 위치를 인자로 받음
    if (position > -1 && position < this.length) {
    //위치 값이 유효한지 확인(유효하지 않으면 null 반환)
      let current = this.head,
        previous,
        index = 0;
      if (position === 0) {
      //첫 번째 원소를 삭제하는 경우
        this.head = current.next;
      } else {
        while (index < position) {
          previous = current;
          current = current.next;
          index++;
        }
        previous.next = current.next;
      }
      this.length--;
      return current.element;
    } else {
      return null;
    }
  };

  insert(position, element) {
    if (position >= 0 && position <= this.length) {
      let node = new this.Node(element); // 노드를 추가하는 헬퍼 생성자 함수를 사용했음
      let current = this.head,
        previous,
        index = 0;
      if (position === 0) {
        node.next = current;
        head = node;
      } else {
        while (index < position) {
          previous = current;
          current = current.next;
          index++;
        }
        node.next = current;
        previous.next = node;
      }
      length++;
      return true;
    } else {
      return false;
    }
  }

  toString() {
    let current = this.head;
    let string = "";

    while (current) {
      string += current.element;
      current = current.next;
    }
    return string;
  }

  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.length; i++) {
      if (element === current.element) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }

  remove(element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }

  getHead() {
    return this.head;
  }
}

// 리스트에 node를 추가하는 헬퍼 클래스
LinkedList.prototype.Node = class {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
};