개념 정리 : 스택, 큐, 리스트, 해시맵 개념과 사용코드(삽입, 삭제 등) 정리

밀라 알고리즘 스터디 1주차 개념 정리 

 

🖋️스택

: 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조

추상 자료형
- push() : 스택 맨 위에 항목을 삽입
- pop() : 스택 맨 위에 항목을 삭제
- isEmpty() : 스택이 비어있는지 확인
- isFull() : 스택이 가득 차있는지 확인
- getSize() : 스택에 있는 요소 수를 반환

 

Push

1. 스택이 가득 찼는지 확인

2. 스택이 가득 찼으면 오류 발생 후 종료

3. 스택이 가득 차지 않았으면 Top 증가 시킴

4. Top이 가리키는 위치에 데이터 추가

 

Pop

1. 스택이 비어있는지 확인

2. 스택이 비어있으면 오류가 발생하고 종료

3. 스택이 비어 있지 않으면 Top이 가리키는 데이터 제거 

4. Top값 감소

 

시간복잡도

push(),pop(),isEmpty(),peek() 모두 O(1)의 시간을 가짐

 ⇒ 삽입,삭제는 항상 Top에서만 일어남

 

🌟CODE

class Stack {
  constructor() {
    this.storage = new Object();
    this.size = 0;
  }

  push(element) {
    this.size++;
    this.storage[this.size] = element;
  }

  pop() {
    let removed = this.storage[this.size];
    delete this.storage[this.size];
    this.size--;
    return removed;
  }

  top() {
    return this.storage[this.size];
  }
}

const stack = new Stack();

stack.push("Apple");
stack.push("Banana");
stack.push("Carrot");

console.log(stack.pop()); 
console.log(stack.top());

 

 

🖋️큐

: 선입선출의 원칙을 따르는 선형 자료구조

 

추상자료형

- add() : 데이터를 추가하는 작업

- delete() : 데이터를 꺼내 사용하는 작업
- rear : 가장 최근에 추가한 데이터를 지시하는 포인터 또는 인덱스

- front : 사용할 데이터를 지시하는 포인터 또는 인덱스

- overflow : 끝까지 add()된 경우 , rear==SIZE-1일 때 add() 시도하면 발생
- underflow : 더 이상 꺼낼 수 없는 경우, front>rear일 때 delete() 시도하면 발생

 

큐의 종류

- 선형 큐 (Linear Queue) 
 : 데이터를 FIFO 순서로 처리하는 가장 기본적인 큐

- 환형 큐(Circular Queue)
 : 큐의 마지막 요소가 첫 요소와 연결된 큐로 원형으로 순환

- 우선순위 큐 (Priority Queue)
 : 각 데이터 요소에 우선순위를 할당하고 해당 우선순위에 따라 데이터를 처리하는 큐

-데큐(De Queue) 
 : 양쪽에서 삽입, 삭제가 가능한 구조

 

시간복잡도

삽입, 삭제의 시간 복잡도 : O(1) 
=> front, rear 의 위치로 데이터 삽입 삭제가 바로 이루어지기 때문에 원소 

 

🌟CODE

class Queue {
  constructor() {
    this.storage = new Object();
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front;
  }

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear++;
  }

  dequeue() {
    let removed = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;

    if (this.front === this.rear) {
      this.front = 0;
      this.rear = 0;
    }

    return removed;
  }
}

let queue = new Queue();

queue.enqueue("Dog");
queue.enqueue("Cat");
queue.enqueue("Pig");
queue.enqueue("Cow");

queue.dequeue(); // Dog
queue.dequeue(); // Cat

console.log(queue); // { storage: { '2': 'Pig', '3': 'Cow' }, front: 2, rear: 4 }
console.log(queue.size()); // 2

 

🖋️리스트(순차 리스트,연결 리스트)

💐순차 리스트
: 특정 자료형이 메모리 공간상에 연속적으로 이루어져 있는 자료구조

 

특징

- 메모리 상에 연속적으로 저장 -> 데이터 접근 속도 빠름
- 인덱스를 통해 접근하기 때문에 어떤 열에 접근하더라도 속도가 같음
- 배열의 최대크기를 변경할 수 없음
- 삽입/삭제 시 자료의 이동 발생
   : 데이터를 삽입하거나 삭제하고 나면, 연속적인 물리적 위치를 유지하기 위해 원소를 옮기는 추가 작업이 필요하기 때문

 

💐 연결 리스트
 : 여러 개의 흩어진 노드들이 연결된 형태의 자료구조
 : 어떤 object를 갖는 노드를 담고 있고 다음에 어떤 노드를 가리키는지 나타냄

 

특징
- 하나의 노드는 자료와 링크로 구성
- 특정 노드를 삽입, 삭제할 때 노드의 링크 필드만 수정하면 되므로 순차 리스트에 비해 연산 속도가 빠름
- 자료들 외에 링크를 저장하는 변수가 필요함으로 배열보다 메모리 효율이 떨어짐
- 이전 노드를 통해서만 다음 노드를 참조할 수 있음
   : 리스트의 처음부터 다음 노드들을 탐색해야해서 속도가 느림
- 링크가 중간에 끊어지면 다음 노드를 찾기 어려움

 

종류
1. 단순연결리스트(singly linked list) : 한 쪽 방향의 ptr

2. 이중 연결리스트(doubly linked list) : 양쪽 방향의 ptr
3. 환형 연결리스트(circular linked list) : 순환

 

🌟CODE

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

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

  //첫번째 삽입
  insertFirst(data) {
    this.head = new Node(data, this.head) //head에 새로운 node가 들어가고 기존의 해드는 next로 밀려난다.
    this.size++;
  }

  //마지막 삽입
  insertLast(data) {
    let node = new Node(data);
    let current;

    if (!this.head) {
      this.head = node;
    } else {
      current = this.head;

      while (current.next) { 
        current = current.next; 
      }

      current.next = node; 
    }
    this.size++; 
  }

  // 중간 삽입
  insertAt(data, index) {
    //인덱스가 size 범위 넘어서면 아무것도 리턴 하지 않는다.
    if (index > 0 && index > this.size) {
      return;
    }

    if (index === 0) {
      this.head = new Node(data, this.head) //index 0에 삽입시 해당 노드를 넣고 다 한칸식 뒤로 미룸
      this.size++
      return;

    }

    const node = new Node(data);
    let current, previous;

    current = this.head;
    let count = 0;

    while (count < index) {
      previous = current; //node before index
      count++;
      current = current.next; //node after index
    }

    node.next = current;
    previous.next = node;

    this.size++;
  }

  getAt(index) {
    let current = this.head;
    let count = 0;

    while (current) {
      //해당 data의 값을 가져오기 위해 index와 값이 같아질때까지 loop한다.
      if (count == index) {
        console.log(current.data);
      }
      count++;
      current = current.next;
    }
    return null;
  }

//index 삭제 
  removeAt(index) {
    if (index > 0 && index > this.size) {
      return;
    }

    let current = this.head; //current는 현재 첫번째 노드임
    let previous;
    let count = 0;

    if (index === 0) {
      this.head = current.next;
    } else {
      //loop를 통해 해당 index의 연결고리를 끊는다.
      while (count < index) {
        count++;
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }

    this.size--;
  }

  //메모리자체에는 데이터가 남아있겠지만 보여주기 위해서 func 만들었다.
  clearList() {
    this.head = null;
    this.size = 0;
  }
  //data값만 따로
  printListData() {
    let current = this.head; // 현재 노드를 나타냄

    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}
const linkedList = new LinkedList();

linkedList.insertFirst(100);
linkedList.insertFirst(200);
linkedList.insertFirst(300);
linkedList.insertLast(400);
linkedList.insertAt(500, 1)

linkedList.removeAt(2)

linkedList.printListData();

linkedList.getAt(2);

console.log(linkedList)

 

🖋️해시맵

: 키(key)와 값(value) 쌍을 저장하는 자료구조

 

핵심 단어

키
  : 키를 사용하여 해당하는 값을 빠르게 검색
해싱함수
  : 키를 받아서 정수값인 해시코드를 반환하고 반환된 해시코드는 해시 배열의 각 요소인 버킷의 인덱스

 

특징
- 키를 사용하여 값을 빠르게 검색하거나 수정할 수 있음
- 내부적으로 키의 순서를 보장하지 않음 
- 같은 키를 중복해서 사용 불가 / 이미 존재하는 키에 대해 값을 저장하면 기존 값이 덮어 씌워짐
- 해시맵은 null 키와 null 값을 저장하지만 중복은 불가하므로 null 키는 하나만 저장 가능

- 어떤 객체든 키로 사용 가능

🌟CODE

const {LinkedList} = require("./LinkedList.js");

class HashMap {
    #size = 100
    #bucket

    constructor(size) {
        if (size) {
            this.#size = size
        }
        this.#bucket = Array(this.#size).fill(null)
    }

    values() {
        return this.#flatten().map(obj => obj.value)
    }

    forEach(callback) {
        this.entries().forEach(callback)
    }

    entries() {
        return this.#flatten().map(obj => [obj.key, obj.value])
    }

    keys() {
        return this.#flatten().map(obj => obj.key)
    }

    set(key, value) {

        const index = this.#getIdxByKey(key)

        if (!this.#bucket[index]) {
            this.#bucket[index] = new LinkedList()
        }
        const linkedList = this.#bucket[index]
        linkedList.append(key, value)
    }

    size() {
        return this.#bucket.filter(item => !!item).reduce((total, linkedList) => total + linkedList.size(), 0)
    }

    get(key) {
        const linkedList = this.#getLinkedListByKey(key)
        if (!linkedList) return null
        const node = linkedList.search(key)
        if (!node) return null
        return node.getValue()
    }

    has(key) {
        return !!this.get(key)
    }

    delete(key) {
        const linkedList = this.#getLinkedListByKey(key)
        linkedList.delete(key)

    }

    #flatten() {
        return this.#bucket.filter(item => item).reduce((arr, linkedList) => arr.concat(linkedList.getAll()), [])
    }
    #getLinkedListByKey(key) {
        const idx = this.#getIdxByKey(key)
        const node = this.#bucket[idx]
        return node
    }

    #getIdxByKey(key) {
        return this.#hash(key) % this.#size
    }

	  #hash(key) {
	    if (!(typeof key === "string")) throw new Error("key should be a string");
	    let code = 0;
	    for (let i = 0; i < key.length; i++) {
	      code += key.charCodeAt(i);
	    }
	    return code;
	  }

}