IMMERSIVE - #3. Stack, Queue, Linked List

geonhwiยท2019๋…„ 7์›” 24์ผ
0
post-thumbnail

=> 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;
};

profile
ggit

0๊ฐœ์˜ ๋Œ“๊ธ€