[TIL] JavaScript 주요 문법(3)

---

자료구조?
메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.

단순 구조
1. 정수
2. 실수
3. 문자열
4. 논리

선형 구조 : 한 원소 뒤에 하나의 원소만이 존재하는 형태의 자료들이 선형으로 나열되어 있는 구조
1. 배열
2. 연결 리스트
3. 스택
4. 큐

비선형구조 : 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절
1. 트리
2. 그래프

---

배열?
연관된 데이터를 연속적인 형태로 구성된 구조

배열의 특징

• 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없다.
  자바스크립트처럼 대부분의 스크립트 언어는 동적으로 크기가 증감되도록 만들어져 있다.
• 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다.
• 원소를 삭제하면 해당 index에 빈자리가 생긴다.

배열의 추가와 삭제는 O(n)이 소요되므로 추가와 삭제가 반복되는 로직이라면 배열 사용을 권하지 않는다

배열 생성

let arr1 = [];
console.log(arr1); // [];

let arr2 = [1, 2, 3, 4, 5];
console.log(arr2); // [1, 2, 3, 4, 5];

let arr3 = Array(5).fill(0);
console.log(arr3); // [0, 0, 0, 0, 0]

let arr4 = Array.from({ length: 5 }, (_, i) => i);
console.log(arr4); // [0, 1, 2, 3, 4]

배열의 요소 추가, 삭제

const arr = [1, 2, 3];
console.log(arr); // [1, 2, 3]

arr.push(4);
arr.push(5, 6);
console.log(arr); // [1, 2, 3, 4, 5, 6]

arr.splice(3, 0, 128);
console.log(arr); // [1, 2, 3, 128, 4, 5, 6]

arr.splice(3, 1);
console.log(arr[3]); // 4

배열의 특이점 : 자바스크립트의 배열은 객체타입이다.

const arr = [];
console.log(arr); // []
arr.push(1);
arr.push(1);
arr.push(2);
arr.push(3);
console.log(arr); // [1, 1, 2, 3]
console.log(arr.length); // 4

arr["string"] = 10;
arr[false] = 0;
console.log(arr); // [ 1, 1, 2, 3, string: 10, false: 0]
console.log(arr.length); // 4
arr[4] = 5;
console.log(arr.length); // 5

---

연결 리스트(Linked List)

1. 각 요소를 포인터로 연결하여 관리하는 선형 자료구조를 의미한다.
2. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

연결 리스트의 특징

- 메모리가 허용하는한 요소를 제한없이 추가할 수 있다.
- 탐색은 O(n)이 소요된다.
- 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
- Singly Linked List, Dubly Linked List, Circular Linked List가 존재한다.

Singly Linked Lists
Head에서 Tail까지 단방향으로 이어지는 연결리스트

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;
    while (curNode.value !== value) {
      curNode = curNode.next;
    }
    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(prevNode, newValue) {
    const newNode = newNode(newValue);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
  }
  
  remove(prevNode) {
    if(prevNode.next.next !== null) {
      prevNode.next = prevNode.next.next;
    } else {
      prevNode.next = null;
    }
  }
  
  display() {
    let currNode = this.head;
    let displayString = "[";
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }
}   

Doubly Linked List

• 양방향으로 이어지는 연결리스트
• Singly Linked List보다 자료구조의 크기가 조금 더 크다.

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  
  find(value) {
    let curNode = this.head;
    while (curNode.value !== value) {
      curNode = curNode.next;
    }
    return curNode;
  }
  
  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(prevNode, newValue) {
    const newNode = new Node(newValue);
    newNode.next = prevNode.next;
    newNode.prev = prevNode;
    prevNode.next.prev = newNode;
    prevNode.next = newNode;
  }
  
  remove(prevNode) {
    if(prevNode.next.next !== null) {
      prevNode.next.next.prev = prevNode;
      prevNode.next = prevNode.next.next;
    } else {
      prevNode.next = null;
    }
  }
  
  display() {
    let currNode = this.head;
    let displayString = "[";
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }
}   

Circular Linked List

• Singly 혹은 Doubly Linked List에서 Tail이 Head로 연결되는 연결리스트
• 메모리를 아껴쓸 수 있다.
• 원형 큐 등을 만들때도 사용된다.

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

class CircularLinkedList {
  constructor() {
    this.head = null;
    this.tail = head;
    this.size = 0;
  }
  
  find(value) {
    let curNode = this.head;
    let cnt = 0;
    while (curNode.value !== value && cnt !== this.size) {
      curNode = curNode.next;
    }
    return curNode;
  }
  
  append(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
      this.size += 1;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
      newNode.next = this.head;
      this.size += 1;
    }
  }
  
  insert(node, newValue) {
    const newNode = newNode(newValue);
    newNode.next = node.next;
    node.next = newNode;
    this.size += 1;
  }
  
  remove(prevNode) {
    if(prevNode.next.next !== this.head) {
      prevNode.next = prevNode.next.next;
      this.size -= 1;
    } else {
      prevNode.next = this.head;
      this.size -= 1;
    }
  }
  
  display() {
    let currNode = this.head;
    let displayString = "[";
    let cnt == 0;
    while (cnt !== this.size) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }
}   

---

스택

• Last In First Out이라는 개념을 가진 선형 자료구조

Array로 구현

const stack = []

stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // [1, 2, 3]

stack.pop();
console.log(stack); // [1, 2]

console.log(stack[stack.length - 1]); //2

Linked List로 구현

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