head: 연결리스트의 시작점
노드의 정보를 알아서 바로 삭제, 추가 할때는 O(1)
노드를 찾아야할때는 O(n)

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

createList, add

class ListNdoe {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class List {
  constructor() {
    this.head = null;
  }
}

List.prototype.add = function (val) {
  let curr = this.head;
  const newNode = new Node(val);

  if (!curr) {
    this.head = newNode; // this.head
  } else {
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = newNode;
  }
};

List.prototype.createList = function (arr) {
  const dummy = new ListNdoe(null);
  let curr = dummy;

  while (arr.length) {
    curr.next = new ListNdoe(arr.shift());
    curr = curr.next;
  }
  return dummy.next;
};

const list = new List();
const linkedList = list.createList([1, 2]);

모든노드 출력하기 traverse (print all node)

let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
// console.log(head);

1. Iteration

function interatePrint(node) {
  let curr = node;
  while (curr) {
    console.log(curr.value);
    curr = curr.next;
  }
}
// interatePrint(head); // 1,2,3,4

2. Recursive

function recursivePrint(node) {
  console.log(node.value);
  if (node.next) {
    recursivePrint(node.next);
  }
}
recursivePrint(head);

---

create linked list

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function createList(arr) {
  const dummy = new Node(null);
  let curr = dummy;

  while (arr.length) {
    const aNode = new Node(arr[0]);
    curr.next = aNode;
    curr = curr.next;
    arr.shift();
  }
  return dummy.next;
}

---

single linked list 기본

head 앞에 삽입

// O(1)
  addToHead(value) {
    const newNode = new Node(value); // 새로운 노드 만들기
    newNode.next = this.head; // head앞에 새로운노드 넣기
    this.head = newNode; // 새로운 노드를 head로 바꾸기
  }

tail뒤에 삽입

 // O(n)
  addToTail(value) {
    const newNode = new Node(value);
    // 아무것도 없음 그냥 넣어줌
    if (!this.head) {
      this.head = newNode;
    } else {
      let curr = this.head;
      while (curr.next) {
        curr = curr.next;
      }
      curr.next = newNode;
    }
  }

노드 찾기

// O(n)
  findNode(target) {
    let curr = this.head;
    while (curr) {
      if (curr.value === target) {
        // console.log("found!", target, curr);
        return curr;
      }
      curr = curr.next;
    }
    // console.log("can't find", target);
    return;
  }

target node뒤에 노드 추가

// O(1)
  addAfter(targetNode, value) {
    const newNode = new Node(value);
    newNode.next = targetNode.next; // 새로운 노드랑 원래 다음 노드 연결
    targetNode.next = newNode; // 타겟노드와 새로운 노드 연결
  }

target node뒤에 삭제

deleteAfter(prevNode) {
    if (prevNode.next) {
      if (prevNode.next.next) {
        prevNode.next = prevNode.next.next;
      } else {
        prevNode.next = null;
      }
    }
  }