연결 리스트

단일 연결 리스트

class SinglyLinkedListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

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

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

  print() {
    let cur = this.head;
    const datas = [];
    while (cur) {
      datas.push(cur.data);
      cur = cur.next;
    }
    return datas;
  }

  // 삽입
  insert(val) {
    if (this.head === null) {
      this.head = new SinglyLinkedListNode(val);
    } else {
      const temp = this.head;
      this.head = new SinglyLinkedListNode(val);
      this.head.next = temp;
    }
    this.size += 1;
  }

  // 값에 의한 삭제
  remove(val) {
    let cur = this.head;
    if (cur.data === val) {
      this.head = cur.next;
      this.size -= 1;
    } else {
      while (cur.next) {
        const next = cur.next;
        if (next.data === val) {
          cur.next = next.next;
          this.size -= 1;
          break;
        } else {
          cur = next;
        }
      }
    }
  }

  // 헤드 항목 삭제
  deleteAthHead() {
    let toReturn = null;
    if (this.head !== null) {
      toReturn = this.head.data;
      this.head = this.head.next;
      this.size -= 1;
    }
    return toReturn;
  }

  // 검색
  find(val) {
    const cur = this.head;
    while (cur) {
      if (cur.data === val) return true;
      cur = cur.next;
    }
    return false;
  }
}

이중 연결 리스트

class DoublyLinkedListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

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

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

  print() {
    let cur = this.head;
    const datas = [];
    while (cur) {
      datas.push(cur.data);
      cur = cur.next;
    }
    return datas;
  }

  // 헤드에 항목에 삽입하기
  addAtFront(val) {
    if (this.head === null) {
      this.head = new DoublyLinkedListNode(val);
      this.tail = this.head;
    } else {
      const temp = new DoublyLinkedListNode(val);
      temp.next = this.head;
      this.head.prev = temp;
      this.head = temp;
    }
    this.size += 1;
  }

  // 테일에 항목 삽입하기
  insertAtTail(val) {
    if (this.tail === null) {
      this.tail = new DoublyLinkedListNode(val);
      this.head = this.tail;
    } else {
      const temp = new DoublyLinkedListNode(val);
      temp.prev = this.tail;
      this.tail.next = temp;
      this.tail = temp;
    }
    this.size += 1;
  }

  // 헤드의 항목 삭제하기
  deleteAtHead() {
    const toReturn = null;
    if (this.head !== null) {
      toReturn = this.head.data;
      if (this.tail === this.head) {
        this.head = null;
        this.tail = null;
      } else {
        this.head = this.head.next;
        this.head.prev = null;
      }
      this.size -= 1;
    }
    return toReturn;
  }

  // 테일의 항목 삭제하기
  deleteAtTail() {
    const toReturn = null;
    if (this.tail !== null) {
      toReturn = this.tail.data;
      if (this.tail === this.head) {
        this.head = null;
        this.tail = null;
      } else {
        this.tail = this.tail.prev;
        this.tail.next = null;
      }
      this.size -= 1;
    }
    return toReturn;
  }

  // 검색
  findStartingHead(val) {
    const cur = this.head;
    while (cur.next) {
      if (cur.data === val) return true;
      cur = cur.next;
    }
    return false;
  }

  findStartringTail(val) {
    const cur = this.tail;
    while (cur) {
      if (cur.data === val) return true;
      cur = cur.prev;
    }
    return false;
  }
}