[TDL] 07/20 Today's-Done-List

- 유데미 알고리즘 단일 연결 리스트

유데미 강사는 제로베이스 강사와 다르게 class로 연결 리스트를 구현한다.

https://dev-minju.tistory.com/193

내가 정리한 건데 왜 잘 모르겠지^^..
어쨌든 제로베이스 강사의 방식은 append, insert, remove, removeAt으로 노드의 삽입과 삭제를 구현한다.
유데미 강사는 기존의 push, pop, shift, unshift를 이름으로 구현하는데,
사실 이름은 뭘 하든 상관없는 거고 구현 방식이 중요한 거라서 클래스형과 함수형의 구현 방식의 차이에 대해 이해하고, 내가 어떤 방식으로 할 때 더 이해하기 쉬운지 판단해야 할 것 같다.

---

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

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

연결 리스트의 중점은 노드 클래스의 val, next와 연결 리스트 생성자 함수 안에 있는 head, tail, length의 흐름을 잘 파악해야 되는 것 같다.

생성하는 push와 unshift일 때는 val을 받아서, newNode에 생성자 함수를 만들고,
다른 점이 있다면 push는 끝 쪽에 삽입되므로, head가 있다면 tail에 받은 val을 넣고 unshift는 head에 받은 val을 넣는다.

제거하는 pop과 shift일 때는 만약 리스트가 없어서 head가 없을 경우 undefined를 리턴해주고,
pop에서 리스트가 한 개 있어서 pop으로 제외한 후 length가 0이라면 head와 tail을 null 처리해준다.
리스트가 두 개 이상일 경우에는, current.next로 리스트의 끝으로 가서 newTail에 current를 넣고, current에 current.next를 할당한다. 그 후에, tail에 newTail을 대입해주고 tail.next에 null을 넣어서 current.next인 current를 제외시킨다. 
shift에서 head에 기존의 head의 next값을 집어넣어서 기존의 head값을 제외시킨다.

---

- 인프런 함수형 프로그래밍 강의

지금까지 map, filter, forEach 함수를 만들었음.
오늘은 reduce함수를 만들어보자.

reduce는 축약시키는 함수이고, reduce 함수는 복잡하거나 어려운 로직을 단순하게 할 수 있게 도와준다.
첫 번째 인자의 데이터들을 두 번째 인자를 통해 축약시켜서 원하는 새로운 결과를 만들 때 사용한다. 대부분의 경우에는 원래 들어온 자료와는 다르게, 새로운 데이터를 리턴할 때 사용한다.

function _each(list, iter) {
  for(let i = 0; i < list.length; i++) {
    iter(list[i]);
  }
  return list;
}

function add(a, b) {
  return a + b
}

function _reduce(list, iter, memo) {
  _each(list, function(val) {
     memo = iter(memo, val);
  });
  return memo;
}

console.log(
  _reduce([1, 2, 3], add, 0)); // 6

이전에 만들어둔 each함수를 이용해서 리스트 안에 있는 모든 값들을 순회하면서 return 할 memo를 계속 덮어 씌우는 것.
iter를 실행하면서 이전의 memo와 새로 받은 val값을 넣어주면 된다.

---

function _each(list, iter) {
  for(let i = 0; i < list.length; i++) {
    iter(list[i]);
  }
  return list;
}

function add(a, b) {
  return a + b
}

let slice = Array.prototype.slice;
function _rest(list, num) {
  return slice.call(list, num || 1);
}

function _reduce(list, iter, memo) {
  if (arguments.length == 2) {
    memo = list[0];
    list = _rest(list);
  }
  _each(list, function(val) {
     memo = iter(memo, val);
  });
  return memo;
}

console.log(
  _reduce([1, 2, 3], add)); // 6

(아랫부분이 수정된 코드여서 따로 구분을 했음)
만약 reduce함수에 memo를 넘겨주지 않을 경우에는 콘솔의 값들을 예로 들면
add(add(1, 2), 3)을 해주면서, 배열 안의 3이 memo의 역할을 하면서 동작하도록 구현을 해야 한다.

function _reduce(list, iter, memo) {
  if (arguments.length == 2) {
    memo = list[0];
    list = list.slice(1);
  }

위의 코드처럼 _reduce함수에서 arguments의 length가 2일 경우 (memo가 없을 경우) slice를 해주면 되지 않느냐고 생각할 수 있는데, 그렇게 사용할 경우 배열은 제대로 작동하지만, 배열이 아닌 경우에는 사용을 하지 못하는 _reduce함수가 되어버린다.

let slice = Array.prototype.slice;
function _rest(list, num) {
  return slice.call(list, num || 1);
}

따라서 _rest함수를 만들어, 유사 배열 객체일 경우에도 _reduce함수를 사용할 수 있도록 한 것.
변수 slice에 Array.prototype.slice를 할당하고
list, num을 인자로 받아, slice.call을 사용하여 list를 num만큼 슬라이스 해준다. 만약 list 또는 num이 없을 경우 1을 리턴.

---

[ 출처 : JavaScript 알고리즘 & 자료구조 마스터클래스,
자바스크립트로 알아보는 함수형 프로그래밍 (ES5) ]