2. recursive Linkded List

kimkevin90·2021년 11월 16일
0

LinkedList

목록 보기
2/3
post-thumbnail

1. Linked List 재귀 구현


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

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

  append(val) {
    if(this.head === null) {
      this.head = new Node(val);
      return;
    }

    this._append(val, this.head)
  }

  _append(val, curr) {
    if(curr.next === null) {
      curr.next = new Node(val);
      return;
    }

    this._append(val, curr.next); 
  }

  print() {
    const output = this._print(this.head);
    console.log(output);
  }

  _print(curr) {
    if(curr === null) return '';
    return curr.val + this._print(curr.next);
  }

  contains(target) {
    return this._contains(target, this.head); 
  }

  _contains(target, curr) {
    if(curr === null) return false;
    if(curr.val === target) return true;
    return this._contains(target, curr.next);
  }
}

const list = new LinkedList();
// list.append('a');
// list.append('b');
// list.append('c');
// console.log(list.head);
// list.print()
// console.log(list.contains('a')) // true
// console.log(list.contains('d')) // false

2. Linked List Sum

While문 / 재귀

const list = new LinkedList();

list.append(11);
list.append(10);
list.append(12);

const sumList = (head) => {
  let curr = head;
  let sum = 0;
  while(curr !== null) {
    sum += curr.val;
    curr = curr.next;
  }
  return sum;
}; // O(n) time, O(1) space

const sumList = (head) => {
  if(head === null) return 0;
  return head.val + sumList(head.next);
}; // O(n) time, O(n) space

console.log(sumList(list.head));

참고 : codebyte - Recursive Linked List from Scratch

profile
Pay it forward

0개의 댓글