interface INode {
  elm: any // <-- Node 의 값
  next: INode | null // <-- next 가 null 이면 리스트의 마지막 Node 이다
  //     그렇지 않다면 다음 Node 를 참조한다
}

interface ILinkedList {
  append(elm: any): INode // <-- Node 추가
  insert(elm: any, pos: number): INode // pos 에 해당하는 Node 추가
  remove(elm: any): INode | string // <-- 값에 해당하는 Node 삭제
  removeAt(pos: number): INode | string // <-- pos 에 해당하는 Node 삭제
  toString(): string // <-- Node 의 값들을 문자열로 나열
  indexOf(elm: INode): number // <-- Node 의 index 반환
  size(): number // <-- Node 의 갯수반환
  isEmpty(): boolean // <-- List 가 비어있으면 true, 아니면 false
  clear(): void // <-- List 를 초기화
}

class LinkedNode implements INode {
  public next = null // <-- 다음 원소의 Pointer 참조, 참조 하지 않는다면 null 이다
  constructor(public elm: any) {} // <-- LinkedNode 생성시 들어갈 원소값
}

class LinkedList implements ILinkedList {
  private head: INode | null = null // <-- LinkedList 의 첫번째 Node참조 변수
  private length: number = 0 // <-- LinkedList 의 길이

  append(elm: any) {
    let cur = null
    if (!this.head) {
      // this.head 가 없다면 아직 리스트 생성이 이루어지지 않았으므로
      // 첫번째 Node 생성
      this.head = new LinkedNode(elm)
      this.length += 1
      return this.head
    } else {
      // Node 가 있으므로. this.head 를 참조하여
      // next 값이 null 인 요소를 찾는다
      cur = this.head
      while (cur.next) {
        cur = cur.next
      }
      cur.next = new LinkedNode(elm) // next 에 새로운 LinkedNode 생성
      this.length += 1
      return cur.next
    }
  }

  insert(elm: any, pos: number) {
    let prev = null
    if (!this.head) {
      // <-- this.head 가 null 이면 this.head 에 새로운 Node 생성
      this.head = new LinkedNode(elm)
      this.length += 1
      return this.head
    }
    if (pos <= this.length) {
      // <-- pos 가 length 보다 작다면 요소를 찾는다
      let cur = null
      let idx = 1 // <-- 1 부터 시작

      cur = this.head
      while (idx < pos && cur.next) {
        prev = cur
        cur = cur.next
        idx += 1
      }
      // pos 값이 항상 idx 값보다 크지는 않다
      // 이럴경우 prev 가 존재하지 않을 수 있다.
      // 밑은 prev 값이 존재한다면 실행한다
      if (prev) {
        prev.next = new LinkedNode(elm)
        prev.next.next = cur
        this.length += 1
        return prev.next
      }
      // prev 값이 존재하지 않는다면, 첫번째 값이라고 가정한다.
      // perv 에 현재의 this.head 를 참조하고
      // this.head 에 새로운 Node 를 만든후 next 값을 prev 로 연결한다.
      prev = this.head
      this.head = new LinkedNode(elm)
      this.head.next = prev
      this.length += 1
      return this.head
    } // <--- pos 가 length 보다 크다면, linkedNode 끝에 추가
    prev = this.head
    while (prev.next) {
      prev = prev.next
    }
    prev.next = new LinkedNode(elm)
    this.length += 1

    return prev.next
  }

  // 이 다음 부터는 로직들이 거의 동일하므로 생략한다.

  remove(elm: any) {
    let cur = null
    let prev = null
    if (!this.head) return '삭제할 값이 없습니다'
    cur = this.head
    while (cur.elm !== elm && cur.next) {
      prev = cur
      cur = cur.next
    }

    if (cur.elm !== elm) {
      return '삭제할 값이 없습니다.'
    }

    if (prev) {
      prev.next = cur.next
      this.length -= 1
      return cur
    }

    this.length -= 1
    this.head = cur.next
    return cur
  }

  removeAt(pos: number) {
    if (!this.head) return '삭제할 값이 없습니다'
    if (pos <= this.length) {
      let cur: INode | null = null
      let prev: INode | null = null
      let idx = 1
      cur = this.head
      while (idx !== pos && cur.next) {
        prev = cur
        cur = cur.next
        idx += 1
      }
      if (prev) {
        prev.next = cur.next
        this.length -= 1
        return cur
      }
      this.head = this.head.next
      this.length -= 1
      return cur
    }
    return '삭제할 값이 없습니다'
  }

  indexOf(elm: any): number {
    let idx = 1 // <-- idx 값은 1부터 시작하는것으로 한다
    if (!this.head) return -1

    let cur = this.head
    while (cur.elm !== elm && cur.next) {
      cur = cur.next
      idx += 1
    }
    return idx
  }

  size(): number {
    return this.length
  }

  isEmpty(): boolean {
    if (!this.head) return true
    return false
  }

  clear(): void {
    this.head = null
    this.length = 0
  }

  toString(): string {
    if (!this.head) return '값이 없습니다.'
    let cur = this.head
    let str = ''
    while (cur.next) {
      str += `${cur.elm} `
      cur = cur.next
    }
    return str + cur.elm
  }
}

const lk = new LinkedList()

console.log(lk.append(1)) // LinkedNode { elm: 1, next: null }
console.log(lk.append(2)) // LinkedNode { elm: 2, next: null }
console.log(lk.toString()) // 1 2
console.log(lk.insert(3, 1))
/*
LinkedNode {
  elm: 3,
  next: LinkedNode { elm: 1, next: LinkedNode { elm: 2, next: null } }
}
*/
console.log(lk.toString()) // 3 1 2
console.log(lk.remove(3))
/*
LinkedNode {
  elm: 3,
  next: LinkedNode { elm: 1, next: LinkedNode { elm: 2, next: null } }
}
*/
console.log(lk.toString()) // 1 2
console.log(lk.remove(5)) // 삭제할 값이 없습니다
console.log(lk.toString()) // 1 2
console.log(lk.removeAt(1)) // LinkedNode { elm: 1, next: LinkedNode { elm: 2, next: null } }
console.log(lk.toString()) // 2
console.log(lk.insert(3, 1))
console.log(lk.size()) // 2
console.log(lk.toString()) // 3 2
console.log(lk.indexOf(3)) // 1 <-- index 는 0 부터가 아닌 1부터 시작