=> 2019.07.28 : 대체 이걸 어떻게 한 챕터에 정리하겠다고 몰아넣었는지...후회가...😭

📚 Data Structure

오늘은 Data Structrue에 대해서 스스로 알아보고 공부해야합니다!

먼저, 순서대로 강의내용을 정리하고 공부해봅시다! 👀

---

🔎 사전 학습 내용

1. 자료구조

• 자료를 어떻게 효율적으로 저장하고 관리할 것인지,
• 데이터 값의 모임, 또는 데이터 간의 관계, 데이터에 적용할 수 있는 함수
• 취업할 때, 주로 알고리즘을 자주 물어보는데, 알고리즘의 기반은 자료구조!

2. Pseudo Code

• 프로그램을 작성할 때 프로그램이 작동하는 논리를 표현하는 코드
• 특정 언어의 문법이 아니라, 일반적인 언어로 코드를 흉내내어 알고리즘을 적는!
• 코드같지 않은 코드? 😅

---

👩🏻‍💻 Self Study

1. Stack (스택)

시작은 스택입니다. 번역하면 쌓다. 쌓다올리다. 그런 느낌이죠.

이게 그림으로 보면 정말 간단합니다. (처음이라 한번 그려봤습니다...🤫)

번호대로 순서대로 들어가고(PUSH), 제일 위에서 부터 꺼낼 수 있습니다.(POP)

이런걸 멋있게 LIFO(Last In First Out) 이라고 합니다!

동작을 보면 JavaScript에서 Array메소드인 Push와 Pop이 스택 용어와 동일합니다!

코드로 간단한 예시를 들어보겠습니다.

// 1.
const add = (a, b) => a + b;
// 2.
const printNumber = (x, y) => {
    let num = add(x, y);
    return num;
}
// 3.
printNumber(5, 10) // 15

1. printNumber가 먼저 콜스택에 들어갑니다.(PUSH)
2. add함수를 호출하므로 add함수가 콜스택에 들어갑니다.(PUSH)
3. num을 계산하고 나면 add가 콜스택에서 빠져나옵니다.(POP)
4. 모든 실행이 끝났으므로 printNumber가 콜스택에서 빠져나옵니다.(POP)

그럼 이제 간략하게 구현해봅시다!

먼저 pseudo Code를 작성해보겠습니다!

사실 처음이다보니 pseudo Code라기보단 순서만 적은 것에 가깝습니다.

/* pseudo Code */
1. Stack 껍데기 생성
2. 빈 배열을 생성
3. PUSH 구현 -> arr.push(item) 
4. POP 구현 -> arr.pop()
5. size 구현 -> 배열의 길이

---

1-1. Stack - functional 코드

실제 코드는 수업을 진행하고 작성하였습니다.

psuedo Code와는 다르게 객체를 사용해야 하서 상당 부분 변경하였습니다.

설명은 주석이 좋을 것 같습니다 :)

// Stack
const Stack = function () {
  // 1. 메소드를 담을 인스턴스 객체, 저장소, 카운트를 선언합니다. 
  const someInstance = {};
  const storage = {};
  var count = 0;

  // 2. PUSH 동작 : storage에 {count, value} 값으로 추가하고, count++
  someInstance.push = function (value) {
    storage[count] = value;
    count++;
  };

  // 3. POP 동작 : 값이 존재할 때, storage에서 key에 맞춰 지우고, 그 값을 리턴합니다.
  someInstance.pop = function () {
    if (count > 0) {
      count--;
      let popNumber = storage[count];
      delete storage[count];
      return popNumber;
    } else {
      return undefined
    }
  };

  // 4. SIZE 동작 : count를 사용하여 크기를 확인합니다.
  someInstance.size = function () {
    return count;
  };

  return someInstance;
};

1-2. Stack - pseudoclassical 코드

이번엔 객체의 prototype에 메서드를 추가하는 방식으로 작성해 보겠습니다.

제가 느끼기에 더 직관적이고 간편합니다 :)

각 객체의 prototype에 직접 구현하면 되니까요!

// 1. Stack클래스에 store(저장소)와 count 변수를 생성한다.
const Stack = function() {
  this.store = {};
  this.count = 0;
};

// 2. Stack객체의 prototype에 push메서드를 구현한다.
Stack.prototype.push = function(item){
  this.store[this.count] = item; 
  this.count++; 
};

// 3. Stack객체의 prototype에 pop메서드를 구현한다.
Stack.prototype.pop = function() {
  if (this.count <= 0) return undefined;
  this.count--;
  let popNumber = this.store[this.count];
  delete this.store[this.count];
  return popNumber;
};

// 4.  Stack객체의 prototype에 size메서드를 구현한다.
Stack.prototype.size = function() {
  return this.count;
}

2. Queue (큐)

스택과 항상 같이 언급되는 큐 입니다.

스택과 다른 점이라면 앞으로 나올 수 있는 선형이라는 겁니다!

PUSH동작은 enqueue이고, POP동작은 SHIFT로 바뀌고, dequeue라고 합니다.

먼저 enqueue한 것이 먼저 dequeue되어, FIFO(First In First Out)이라고 합니다.

저희가 만들 큐에서는 head와 tail을 구현할 것입니다.

enqueue에서는 각 노드의 tail에 값을 넣어주면 되지만,

dequeue에서는 tail이 아닌 head의 값을 지워야 하기 때문이죠!

실제 코드를 보시면 더 이해가 쉬울 겁니다.

스택때처럼 psuedo Code를 먼저 작성해봅시다!

/* psuedo code */
1. 큐 껍데기 생성
2. 빈 배열 생성
3. enqueue 구현 -> arr.push(item) 
4. dequeue 구현 -> arr.shift()
5. size 구현 -> arr.length()

그럼 위 논리에 맞추어 큐를 구현해 봅시다!

2-1. Queue - functional 구현

큐는 스택과 다르게 pop 대신 shift를 사용하면 됩니다!

마찬가지로, 수업 이후 코드를 추가하였고, 객체를 사용하게 되었습니다.

// Queue
const Queue = function () {
  
  // 1. 큐와 조금 다릅니다. 처음과 끝으로 head와 tail을 사용합니다.
  const someInstance = {};
  const storage = {};
  var head = 0;
  var tail = 0;
  var count = 0;

  // 2. enqueue 동작 : storage에 마지막을 뜻하는 {tail, value}을 추가합니다.
  someInstance.enqueue = function (value) {
    storage[tail] = value;
    tail++;
    count++;
  };

  // 3. dequeue 동작 : 값이 존재할 때, 맨 앞을 뜻하는 {head, value}를 삭제하고 리턴합니다.
  someInstance.dequeue = function () {
    if (count > 0) {
      // storage[head]의 값을 기억하여 리턴하기 위해서 따로 변수로 선언하였습니다.
      let headNumber = storage[head];
      delete storage[head];
      head++;
      count--;
      return headNumber;
    }
  };

  // 4. size 동작 : count를 사용하여 크기를 확인합니다.
  someInstance.size = function () {
    return count;
  };

  return someInstance;
};

코드만 보면 이해하기 어려울 수 있습니다.

아래의 순서에 따라 차근차근 따라가보세요!! ⚽️...

/* 진행과정. storage */
1. enq('a') : head: 0, tail: 0 {0: 'a'};          / 이후 head: 0, tail: 1
2. enq('b') : head: 0, tail: 1 {0: 'a', 1: 'b'};  / 이후 head: 0, tail: 2
2. deq()    : head: 1, tail: 2 {1: 'b'};          / 이후 head: 1, tail: 2
2. deq()    : head: 2, tail: 2 {};                / 이후 head: 2, tail: 2

2-2. Queue - pseudoclassical 코드

const Queue = function() {
  // Hey! Rewrite in the new style. Your code will wind up looking very similar,
  // but try not not reference your old code in writing the new style.
  this.storage = {};
  this.head = 0;
  this.tail = 0;
  this.count = 0;
};

Queue.prototype.enqueue = function (value) {
  this.storage[this.tail] = value;
  this.tail++;
  this.count++;
}

Queue.prototype.dequeue = function () {
  if (this.count > 0) {
    let headNumber = this.storage[this.head];
    delete this.storage[this.head];
    this.head++;
    this.count--;
    return headNumber;
  }
}

Queue.prototype.size = function () {
  return this.count;
}

3. Linked List (연결 리스트)

연결리스트는 여러 개의 노드로 구성되어 한 줄로 연결되어 있는 방식입니다!

각 노드는 데이터와 다음 노드를 가리키는 주소를 가지고 있구요.

연결리스트는 데이터를 추가, 삭제, 탐색 등을 할 수 있습니다.

저희는 추가, 삭제, 포함유무 를 구현해볼 것입니다.

연결 리스트를 쉽게 말하면 1->2->3->4->5 순서로 연결되어 있다고 생각하면 됩니다.

위 설명만 보면 배열과 동일하다는 것을 알 수 있는데요!

거의 비슷하지만, 연결 리스트만의 장점이 있습니다!

[1, 2, 4, 5] 라는 배열에 순서에 맞게 3을 집어 넣는다면,

3이 들어가면서 인덱스가 2가 되고, 4와 5의 인덱스가 변경되어야 합니다.

하지만 연결리스트의 추가에서는 연결할 위치의 앞,뒤 노드와 연결하면 됩니다.

물론, 단점도 있습니다.

연결 리스트는 탐색을 위해 첫번째부터 탐색하므로 상황에 따라 느려질 수 있습니다.

따라서, 데이터 추가와 삭제가 많은 경우에만 사용하는 것이 좋겠죠? 👍🏻

그리고, 리스트의 종류는 총 4가지가 있는데요,

1. 단일 연결 리스트
2. 이중 연결 리스트
3. 원형 연결 리스트
4. 이중 원형 연결 리스트

오늘은 1번, 단일 연결 리스트에 대해서만 알아보겠습니다. ✍🏻

psuedo Code부터 작성해 보겠습니다.

/* psuedo Code */
1. Node 생성 ( Include data & addr)
2. LinkedList 껍데기 생성 
3. 비어있는 head, tail 생성
4. insert 구현
5. remove 구현
6. contain 구현

3-1. Linked List - Code 구현

과제를 완료 하고 난 뒤에 수정하고 있습니다.

위 pseudoCode와는 다를 수 있습니다.

각 코드에 대한 설명

head : 각 노드의 머리를 가리키는 head입니다.
tail : 각 노드의 꼬리를 가리키는 tail입니다.
addToTail : 새 노드를 생성하고, tail의 유무에 따라 newNode를 조건에 맞춰 대입합니다.
removeHead : tmp에 제거하려는 head를 저장하고, head의 next를 head에 덮습니다.
contain : target과 일치하는 값이 나올때 까지 head의 next에 head를 덮습니다.

insert동작만 이해하시면 나머진 간단할 듯 합니다.

설명보다는 코드 별 주석이 더 이해가 쉬울 것 같습니다!

// LinkedList
const LinkedList = function() {
  const list = {};
  list.head = null;
  list.tail = null;
  
  list.addToTail = function(value) {    // * INSERT 메서드 
    var newNode = new Node(value);      // * 새로운 노드 생성
    if (!list.tail) {                   // * list가 비었다면 list의 tail에 새 노드 생성
      list.tail = newNode;              // * list.tail은 Node1을 가리킵니다. head와 동일합니다.
      list.head = newNode;              // * 현재 상태 : list { head === tail { Node1 { next: null, value } } }
    } else {                            // * 
      list.tail.next = newNode;         // * tail의 Node2의 주소(null)로 Node3을 가리킴.
      list.tail = newNode;              // * tail을 Node3으로 대체.
    }
  };
  // ! 추가 설명 : 아래 예시를 보면, 이해에 도움이 됩니다. 왜 list에 head와 tail만 존재하는지에 대해 설명합니다.
  // 1. 만약 addToTail(5)와 (10)을 하였다고 하면, 아래와 같습니다.
  // list: { head { value: 5, next: { value: 5, next: null } } , tail { value: 10, next: null } }

  // 2. 여기에 addToTail(15)를 추가한다면,
  // list: { head { value: 5, next: { value: 10, next: null } } , tail { value: 15, next: null } }
  // 위 list에서 head의 next를 보시면 1번에서의 tail을 가리키고 있습니다.
  // 즉, 아래의 contain으로 target을 확인할 때, head.next를 타고 타고 타고 들어가면 
  // list.head.next.next === list.tail (==> { value: 15, next: null }) 이 되는 것입니다.

  list.removeHead = function() {   // REMOVE FIRST NODE
    if(!list.tail) return;
    let tmp = list.head;
    let removed = tmp.value;
    list.head = list.head.next;
    return removed;
  };

  list.contains = function(target) {  // SEARCH, but return true/false
    if (!list.tail) return undefined;
    let tmp = list.head;
    while(tmp.value !== target) {
      tmp = tmp.next;
      if (!tmp) return false;
    }
    return true;
  };
  return list;
};

const Node = function(value) {
  const node = {};
  node.value = value;
  node.next = null;
  return node;
};

---