배열

특징

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

  자바스크립트는 동적으로 크기가 변한다.

• 원하는 원소의 index를 알고 있다면, O(1)의 시간 복잡도로 원소를 찾을 수 있다.
• 원소를 삭제하면 해당 index에 빈자리가 생긴다.

자바스크립트 배열의 특징

• 자바스크립트의 배열은 동적으로 크기가 변할 수 있다.

const arr = []
arr.push(1)	// [1]
arr.push(2)	// [1, 2]

• 자바스크립트의 배열은 HashMap에 가깝다.

const arr = []
arr.a = 1	// [a: 1]
arr.push(1)	// [1, a: 1]

시간 복잡도

배열 요소 탐색

index를 알고 있는 요소를 탐색: O(1)
index를 모르는 요소를 탐색: O(n)

배열 요소 삭제

O(n)

배열 요소 추가

O(n)

추가와 삭제가 반복되는 로직이라면, 배열 자료구조는 적합하지 않음

구현

JavaScript

배열 생성

1. 배열 리터럴
2. 배열 생성자

let arr1 = []
let arr2 = [1, 2, 3, 4]
let arr3 = Array(4).fill(0)	// [0, 0, 0, 0]
let arr4 = Array.from({length: 4}, (_, i) => i)	// [0, 1, 2, 3]

배열 요소 추가, 삭제

let arr = []
arr.push(1)	// [1] O(1)
arr.push(2, 3)	// [1, 2, 3] O(1)
arr.splice(0, 0, 0)	// [0, 1, 2, 3]	O(n)
arr.pop()	// [0, 1, 2] O(1)
arr.splice(0, 1)	// [1, 2, 3] O(n)

배열 순회

const arr = [1, 2, 3, 4]

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i])
}

for (let num of arr) {
  console.log(num)
}

arr.forEach((num, idx) => console.log(num, idx))

연결 리스트

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

특징

• 메모리가 허용하는 한, 동적으로 요소를 추가할 수 있다.
• 탐색 소요 시간: O(n)
• 추가 / 삭제 소요 시간: O(1)

구현

JavaScript

단일 연결 리스트

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

class SinglyLinkedList {
  constructor() {
    this.head = null
    this.tail = null
    this.size = 0
  }
  
  append(value) {
    const newNode = new Node(value)
    if (this.head === null) {
      this.head = newNode
      this.tail = newNode
    } else {
      // 기존 tail에 위치한 노드의 next 포인터에 새 노드를 지정
      this.tail.next = newNode
      this.tail = newNode
    }
    this.size += 1
  }
  
  insert(node, value) {
    const newNode = new Node(value)
    // node - newNode - node.next
    newNode.next = node.next
    node.next = newNode
    this.size += 1
  }
  
  remove(value) {
    let pNode = this.head
    if (pNode.value === value) {
      this.head = pNode.next
      return
    }
    while (pNode.next.value !== value) {
	  pNode = pNode.next
    }
    pNode.next = pNode.next.next
    this.size -= 1
  }
}

이중 연결 리스트

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

class DoublyLinkedList {
  constructor() {
    this.head = null
    this.tail = null
    this.size = 0
  }
  
  append(value) {
    const newNode = new Node(value)
    
    if (this.head === null) {
      this.head = newNode
      this.tail = newNode
    } else {
      newNode.prev = this.tail
      this.tail.next = newNode
      this.tail = newNode
    }
    this.size += 1
  }
  
  remove(value) {
    let pNode = this.head
    if (pNode.value === value) {
      pNode.next.prev = null
      this.head = pNode.next
    }
    while (pNode.next) {
      if (pNode.next.value === value) {
        // pNode - pNode.next - pNode.next.next
        pNode.next = pNode.next.next
        pNode.next.next.prev = pNode
        this.size -= 1
      }
      pNode = pNode.next
    }
  }
}