[Day 3] JavaScript 주요 문법(3)

 

자료구조와 알고리즘

1. 뜻

1) 자료구조 : 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것

- 메모리를 효율적으로 사용하고 빠르게 안정적으로 데이터를 처리하는 것이 목표

 

2) 알고리즘 : 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것

- 특정 문제를 효율적이고 빠르게 해결하는 것이 목표

 

자료구조의 종류

1. 단순 구조 

- 정수, 실수, 문자열, 논리

 

2. 선형 구조

: 자료들이 선형(한 원소뒤엔 하나의 원소)으로 나열되어 있는 구조 

- 배열, 연결리스트, 스택, 큐

 

3. 비선형 구조

: 원소 간 다대다 관계를 가지는 구조(계층형, 망형)

- 트리, 그래프 

 

시간 복잡도

[Algorithm] 시간복잡도 이해하기 (tistory.com)

[Algorithm] 시간복잡도 이해하기

- 예전에 내가 정리한 거 -

 

* 자바스크립에서 성능 측정

- Date 객체를 이용하여 시작시간과 끝 시간을 구해 빼면 로직이 작동한 시간을 알 수 있다.

 

 

배열

1. 배열

1) 의미

- 연관된 데이터를 연속적인 형태로 구성한 구조

- 배열에 포함된 원소는 순서대로 index가 붙는다.

 

2) 특징

- 고정된 크기를 가지며 일반적으로 동적으로 크기를 늘릴 수 없다

* 자바스크립트는 동적으로 크기가 증감 가능하다

• O(1)에 k번째 원소 확인, 변경 가능
• 추가적으로 소모되는 메모리의 양이 거의 없음 
• 데이터들이 붙어있으므로 캐시지역성(cache hit rate)이 좋음
• 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림
• 임의의 위치에 원소에 삽입/삭제하기 위해서는 O(N) 시간이 걸림

2. 자바스크립트에서 배열

- 자바스크립트의 배열에서 index는 number가 아니여도 된다

but number로 하지 않은 값들은 length에 잡히지 않는다.

 

 

연결 리스트

1. 연결 리스트

: 각 요소를 포인터로 연결하여 관리하는 선형 자료 구조

- 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

 

1) 특징

- k번째 원소를 확인/변경 하기 위해 O(k)가 필요함

- 임의의 위치에 원소를 추가/임의 위치에 원소 제거는 O(1)

- 원소들이 메모리상에 연속되어 있지 않아 캐시지역성이 낮지만 할당이 쉬움

 

2) 종류

- 단일 연결 리스트 : 다음 원소의 주소 들고있음

- 이중 연결 리스트 : 각 원소가 이전 원소, 다음 원소 주소 둘 다 들고 있음

- 원형 연결 리스트 : 맨 마지막 원소가 처음 원소로 연결

 

 

💡 단일 연결리스트 구현(size(), 예외처리)

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

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

  find(value) {
    let curNode = this.head;

    // 연결리스트가 비어있을 때 예외처리
    if(curNode === null){
      console.log("연결리스트가 비어있습니다 !")
      return null;
    } 

    while(curNode.value !== value){
      curNode = curNode.next;
      // 없는 노드 찾기 예외처리
      if(curNode === null) {
        console.log(value + "는 연결리스트에 없습니다!");
        return null;
      }
    }
    return curNode;
  }

  // 끝 부분에 추가
  append(newValue) {
    const newNode = new Node(newValue);
    if(this.head === null){
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  insert(node, newValue){
    // node가 null 일때 예외처리
    if(node === null) {
      console.log("존재하지 않는 노드입니다 !");
      return;
    }
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
  }

  remove(value){
    let prevNode = this.head;

    // 삭제하려는 노드가 없을 때 예외처리
    if(prevNode === null) return;

    console.log(prevNode);
    while(prevNode.next.value !== value){
      prevNode = prevNode.next;
      if(prevNode.next === null) {
        console.log(value + "는 연결리스트에 없습니다!");
        return;
      }
    }
    if(prevNode.next !== null){
      prevNode.next = prevNode.next.next;
    }
  }

  display(){
    let curNode = this.head;
    console.log("===연결리스트 출력===");
    let displayStr = "";
    while(curNode !== null){
      displayStr += (curNode.value + ", ");
      curNode = curNode.next;
    }
    console.log(displayStr);
  }

  size(){
    let cnt = 0;
    let curNode = this.head;
    while(curNode !== null){
      cnt++;
      curNode = curNode.next;
    }

    console.log("연결리스트 크기: " + cnt);
  }
}

const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(3);
linkedList.append(4);
linkedList.append(2);
linkedList.append(9);
linkedList.size();
linkedList.display();
console.log(linkedList.find(10));
linkedList.remove(10);
linkedList.display();
linkedList.insert(linkedList.find(9), 10);
linkedList.display();

 

💡 이중 연결리스트 구현

 

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

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

  find(value) {
    // 중복 생략
  }

  // 끝 부분에 추가
  append(newValue) {
    const newNode = new Node(newValue);
    if(this.head === null){
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

  insert(node, newValue){
    // node가 null 일때 예외처리
    if(node === null) {
      console.log("존재하지 않는 노드입니다 !");
      return;
    }
    const newNode = new Node(newValue);
    newNode.next = node.next;
    newNode.prev = node;
    
    if(node.next !== null) node.next.prev = newNode;
    node.next = newNode;
  }

  remove(value){
    let curNode = this.find(value);
    if(curNode === null) return;
    else {
      curNode.prev.next = curNode.next;
      curNode.next.prev = curNode.prev;
    }
    
  }

  display(){
    // 중복 생략
  }

  size(){
    // 중복 생략
  }
}

 

💡 환형 연결리스트 구현

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

class CircularLinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  find(value) {
    let curNode = this.head;

    // 연결리스트가 비어있을 때 예외처리
    if(curNode === null){
      console.log("연결리스트가 비어있습니다 !")
      return null;
    } 

    let cnt = 0;
    while(curNode.value !== value){
      curNode = curNode.next;

      // 없는 노드 찾기 예외처리
      cnt++;
      if(cnt > this.length) {
        console.log(value + "는 연결리스트에 없습니다!");
        return null;
      }
    }
    return curNode;
  }

  // 끝 부분에 추가
  append(newValue) {
    const newNode = new Node(newValue);
    if(this.head === null){
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  insert(node, newValue){
    // node가 null 일때 예외처리
    if(node === null) {
      console.log("존재하지 않는 노드입니다 !");
      return;
    }
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
    this.length++;
  }

  remove(value){
    let prevNode = this.head;

    // 삭제하려는 노드가 없을 때 예외처리
    if(prevNode === null) return;

    let cnt = 0;
    while(prevNode.next.value !== value){
      prevNode = prevNode.next;

      console.log(prevNode);

      cnt++;
      if(cnt === this.length -1) {
        console.log(value + "는 연결리스트에 없습니다!");
        return;
      }
    }
    if(prevNode.next !== null){
      prevNode.next = prevNode.next.next;
    }
  }

  display(){
    let curNode = this.head;
    console.log("===연결리스트 출력===");
    let displayStr = "";

    let cnt = 0;
    while(cnt < this.length){
      displayStr += (curNode.value + ", ");
      curNode = curNode.next;
      cnt++;
    }
    console.log(displayStr);
  }

  size(){
    console.log("연결리스트 크기: " + this.length);
  }
}

 

 

스택

1. 스택

: Last In First Out 구조

 

1) 표현 방법

- Stack을 Array로 표현할 수 있음

- 연결리스트로 표현살 수 있음

 

2) 자바스크립트에서 스택

ⓐ 배열 사용 : push(), pop() 등의 메서드 사용 가능

ⓑ 연결리스트 사용

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

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
    this.size += 1;
  }

  pop() {
    const value = this.top.value;
    this.top = this.top.next;
    this.size -= 1;
    return value;
  }

  size() {
    return this.size;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());
stack.push(4);
console.log(stack.pop());
console.log(stack.pop());