[알고리즘] Leetcode. Design Linked List

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1. 인덱스가 맞지 않으면 -1을 리턴
• void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
• void addAtTail(int val) Append a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted. 인덱스가 리스트 길이보다 길면 추가되지 않음
• void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

var MyLinkedList = function() {
  this.head = null;
  this.tail = null;
};

function createNode(val) {
  const node = {};
  node.value = val;
  node.next = null;

  return node;
}

MyLinkedList.prototype.get = function(index) {
  if (!index) {
    if (!this.head) return -1;
    return this.head.value;
  }

  let temp = this.head;
  for (let i = 0; i < index; i++) {
    if (!temp.next) return -1;
    temp = temp.next;
  }

  return temp.value;
};

MyLinkedList.prototype.addAtHead = function(val) {
  const node = createNode(val);

  if (!this.head) {
    this.head = node;
    this.tail = node;

    return;
  }

    node.next = this.head;
    this.head = node;
};

MyLinkedList.prototype.addAtTail = function(val) {
  const node = createNode(val);

  if (!this.head) {
    this.head = node;
    this.tail = node;

    return;
  }

  this.tail.next = node;
  this.tail = node;
};

MyLinkedList.prototype.addAtIndex = function(index, val) {
  if (!index) {
    return this.addAtHead(val);
  }

  if (!this.head && index > 0) return;

  let temp = this.head;

  for (let i = 0; i < index - 1; i++) {
    if (!temp.next) return;
    temp = temp.next;
  }

  if (!temp.next) return this.addAtTail(val);

  const node = createNode(val);
  node.next = temp.next;
  temp.next = node;
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
  if (!index) {
    if (!this.head.next) {
      this.head = null;
      this.tail = null;

      return;
    }

    this.head = this.head.next;
    return;
  }

  let temp = this.head;

  if (index === 1) {
    if (!this.head.next) return;

    temp = this.head.next;

    if (!temp.next) {
      this.head.next = null;
      this.tail = this.head;

      return;
    }

    this.head.next = temp.next;

    return;
  }

  for (let i = 0; i < index - 1; i++) {
    if (!temp.next) return;
    temp = temp.next;
  }

  if (!temp.next) return;

  const removeNode = temp.next;

  if (!removeNode.next) {
    temp.next = null;
    this.tail = temp;

    return;
  }
  temp.next = removeNode.next;
};

addAtIndex, deleteAtIndex 구현할 때 많이 애를 먹었다. 내 생각보다 생각해야 할 부분이 많았다.

index 1을 삭제하려고 할 때 index 0 ~ 1에 값이 있는가부터 사소한 것 하나하나 생각하고 처리해야 한다는 걸 배우게 되었다. 기본적으로 있겠지 라고 생각하지 말고 미리 에러 처리를 해두는 게 습관을 잡아가기에 도움이 될 것 같다.