[Topic #자료구조 02] Singly Linked List 구현 with JavaScript

// node.js
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

module.exports = Node;

 

// singly-linked-list01.js
const Node = require('./node');

// Singly Linked List 01 - Head만 가지고 있는 경우
class SinglyLinkedList01 {
  // S.C: O(1)
  constructor() {
    this.head = null;
    this.cnt = 0;
  }
  // T.C: O(1)
  insertHead(item) {
    const node = new Node(item);
    this.cnt += 1;
    node.next = this.head;
    this.head = node;
  }
  // T.C: O(n)
  insertTail(item) {
    const node = new Node(item);
    this.cnt += 1;
    if (!this.head) {
      this.head = node;
      return;
    }
    let curr = this.head;
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = node;
  }
  // T.C: O(n)
  insertIndex(idx, item) {
    const node = new Node(item);
    this.cnt += 1;
    if (!this.head) {
      this.head = node;
      return;
    }
    let curr = this.head;
    let prev = null;
    let order = 0;
    while (idx !== order) {
      prev = curr;
      curr = curr.next;
      order += 1;
    }
    if (!prev) {
      if (idx > 0) {
        this.head.next = node;
      } else {
        node.next = curr;
        this.head = node;
      }
    } else {
      prev.next = node;
      node.next = curr;
    }
  }
  // T.C: O(1)
  deleteHead() {
    if (!this.head) return;
    this.cnt -= 1;
    this.head = this.head.next;
  }
  // T.C: O(n)
  deleteTail() {
    if (!this.head) return;
    this.cnt -= 1;
    let curr = this.head;
    let prev = null;
    while (curr.next) {
      prev = curr;
      curr = curr.next;
    }
    if (prev) prev.next = null;
    else this.head = null;
  }
  // T.C: O(n)
  deleteIndex(idx) {
    if (!this.head) return;
    this.cnt -= 1;
    let curr = this.head;
    let prev = null;
    let order = 0;
    while (order !== idx) {
      prev = curr;
      curr = curr.next;
      order += 1;
    }
    if (!prev) this.head = null;
    else prev.next = curr.next;
  }
  // O(1)
  count() {
    // O(n)
    // let count = 0;
    // let curr = this.head;
    // while (curr) {
    //   count += 1;
    //   curr = curr.next;
    // }
    return this.cnt;
  }
  // O(n)
  printAll() {
    let curr = this.head;
    while (curr) {
      process.stdout.write(curr.data + ' ');
      curr = curr.next;
    }
    console.log();
  }
}

// Simple Test Case
const sll01 = new SinglyLinkedList01();
sll01.insertHead('A');
sll01.insertHead('B');
sll01.insertHead('C');
sll01.insertTail('D');
sll01.insertTail('E');
sll01.insertTail('F');
sll01.printAll();
sll01.deleteHead();
sll01.deleteTail();
sll01.printAll();
sll01.insertIndex(0, 'G');
sll01.printAll();
sll01.deleteIndex(3);
sll01.printAll();
console.log(sll01.count());

 

// singly-linked-list02.js
const Node = require('./node');

// Singly Linked List 02 - Head, Tail 모두 가지고 있는 경우
class SinglyLinkedList02 {
  // S.C: O(1)
  constructor() {
    this.head = null;
    this.tail = null;
    this.cnt = 0;
  }
  // T.C: O(1)
  insertHead(item) {
    const node = new Node(item);
    this.cnt += 1;
    if (!this.head) {
      this.head = node;
      this.tail = node;
      return;
    }
    node.next = this.head;
    this.head = node;
  }
  // T.C: O(1)
  insertTail(item) {
    const node = new Node(item);
    this.cnt += 1;
    if (!this.head) {
      this.head = node;
      this.tail = node;
      return;
    }
    this.tail.next = node;
    this.tail = node;
  }
  // O(n)
  insertIndex(idx, item) {
    const node = new Node(item);
    this.cnt += 1;
    if (!this.head) {
      this.head = node;
      this.tail = node;
      return;
    }
    let curr = this.head;
    let prev = null;
    let order = 0;
    while (idx !== order) {
      prev = curr;
      curr = curr.next;
      order += 1;
    }
    if (!prev) {
      if (idx > 0) {
        this.head.next = node;
      } else {
        node.next = curr;
        this.head = node;
      }
    } else {
      prev.next = node;
      node.next = curr;
      if (!curr) this.tail = node;
    }
  }
  // O(1)
  deleteHead() {
    if (!this.head) return;
    this.cnt -= 1;
    if (!this.head.next) this.tail = null;
    this.head = this.head.next;
  }
  // O(n)
  deleteTail() {
    if (!this.head) return;
    this.cnt -= 1;
    let curr = this.head;
    let prev = null;
    while (curr.next) {
      prev = curr;
      curr = curr.next;
    }
    if (!prev) {
      this.head = null;
      this.tail = null;
    } else {
      prev.next = null;
      this.tail = prev;
    }
  }
  // O(n)
  deleteIndex(idx) {
    if (!this.head) return;
    this.cnt -= 1;
    let curr = this.head;
    let prev = null;
    let order = 0;
    while (idx !== order) {
      prev = curr;
      curr = curr.next;
      order += 1;
    }
    if (!prev) {
      this.head = null;
      this.tail = null;
    } else {
      prev.next = curr.next;
      if (!prev.next) this.tail = prev;
    }
  }
  // T.C: O(1)
  count() {
    return this.cnt;
  }
  // T.C: O(n)
  printAll() {
    let curr = this.head;
    while (curr) {
      process.stdout.write(curr.data + ' ');
      curr = curr.next;
    }
    console.log();
  }
}

// Simple Test Case
const sll02 = new SinglyLinkedList02();
sll02.insertHead('A');
sll02.insertHead('B');
sll02.insertHead('C');
sll02.insertTail('D');
sll02.insertTail('E');
sll02.insertTail('F');
sll02.printAll();
sll02.deleteHead();
sll02.deleteTail();
sll02.printAll();
sll02.insertIndex(2, 'G');
sll02.printAll();
sll02.deleteIndex(4);
sll02.printAll();
console.log(sll02.count());

 

// singly-linked-list03.js
const Node = require('./node');

// Singly Linked List 03 - Tail 노드만 가지고 있고 circular 하게 만드는 경우
class SinglyLinkedList03 {
  // S.C: O(1)
  constructor() {
    this.tail = null;
    this.cnt = 0;
  }
  // T.C: O(1)
  insertHead(item) {
    const node = new Node(item);
    this.cnt += 1;
    if (!this.tail) {
      node.next = node;
      this.tail = node;
      return;
    }
    node.next = this.tail.next;
    this.tail.next = node;
  }
  // T.C: O(1)
  insertTail(item) {
    const node = new Node(item);
    this.cnt += 1;
    if (!this.tail) {
      node.next = node;
      this.tail = node;
      return;
    }
    node.next = this.tail.next;
    this.tail.next = node;
    this.tail = node;
  }
  // T.C: O(n)
  insertIndex(idx, item) {
    const node = new Node(item);
    this.cnt += 1;
    if (!this.tail) {
      node.next = node;
      this.tail = node;
      return;
    }
    let curr = this.tail.next;
    let prev = null;
    let order = 0;
    while (order !== idx) {
      prev = curr;
      curr = curr.next;
      order += 1;
    }
    if (!prev) {
      if (idx > 0) {
        node.next = this.tail.next;
        this.tail.next = node;
        this.tail = node;
      } else {
        node.next = this.tail.next;
        this.tail.next = node;
      }
    } else {
      let head = this.tail.next;
      prev.next = node;
      node.next = curr;
      if (node.next === head) this.tail = node;
    }
  }
  // T.C: O(1)
  deleteHead() {
    if (!this.tail) return;
    this.cnt -= 1;
    if (this.tail.next === this.tail) {
      this.tail = null;
      return;
    }
    this.tail.next = this.tail.next.next;
  }
  // T.C: O(n)
  deleteTail() {
    if (!this.tail) return;
    this.cnt -= 1;
    if (this.tail.next === this.tail) {
      this.tail = null;
      return;
    }
    let curr = this.tail.next;
    let prev = null;
    while (curr.next) {
      prev = curr;
      curr = curr.next;
      if (curr === this.tail) break;
    }
    if (!prev) this.tail = null;
    else {
      prev.next = this.tail.next;
      this.tail = prev;
    }
  }
  // T.C: O(n)
  deleteIndex(idx) {
    if (!this.tail) return;
    this.cnt -= 1;
    if (this.tail.next === this.tail) {
      this.tail = null;
      return;
    }
    let curr = this.tail.next;
    let prev = null;
    let order = 0;
    while (order !== idx) {
      prev = curr;
      curr = curr.next;
      order += 1;
    }
    if (!prev) this.tail = null;
    else {
      let head = this.tail.next;
      prev.next = curr.next;
      if (curr.next === head) this.tail = prev;
    }
  }
  // T.C: O(1)
  count() {
    return this.cnt;
  }
  // T.C: O(n)
  printAll() {
    if (!this.tail) return;
    let curr = this.tail.next;
    while (curr) {
      process.stdout.write(curr.data + ' ');
      curr = curr.next;
      if (curr === this.tail.next) break;
    }
    console.log();
  }
}

// Simple Test Case
const sll03 = new SinglyLinkedList03();
sll03.insertHead('A');
sll03.insertHead('B');
sll03.insertHead('C');
sll03.insertTail('D');
sll03.insertTail('E');
sll03.insertTail('F');
sll03.printAll();
sll03.deleteHead();
sll03.deleteTail();
sll03.printAll();
sll03.insertIndex(2, 'G');
sll03.printAll();
sll03.deleteIndex(4);
sll03.printAll();
console.log(sll03.count());

---

자세한 내용은 추후 업데이트 하겠습니다.