배열(Array)

• 가장 기본적인 자료구조
• 여러 개의 변수를 담는 공간으로 이해할 수 있다.
• 배열은 인덱스(index)가 존재하며, 인덱스는 0부터 시작한다.
• 특정한 인덱스에 직접적으로 접근 가능 → 수행 시간 : O(1)

배열의 특징

• 컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다.
• 장점 : 캐시(cache) 히트 가능성이 높으며, 조회가 빠르다
• 단점 : 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.

JavaScript의 배열

• 일반 배열처럼 임의의 인덱스를 이용해 직접적인 접근이 가능하다
• 동적 배열의 기능을 제공하여, 맨 뒤의 위치에 원소 추가가 가능하다
• push() 메서드를 통해 배열의 가장 뒤쪽에 새로운 원소를 추가할 수 있다
• 배열의 용량이 가득차면, 자동으로 크기를 증가시킨다
• 내부적으로 포인터를 사용하여, 연결 리스트의 장점도 가지고 있다
• 배열 혹은 스택의 기능이 필요할 때 사용할 수 있다 (큐의 기능 ⇒ 비효율적)

배열 초기화

1. 대괄호 사용하기
2. Array() 사용하기
   • 크기가 N(5)인 1차원 배열 : Array.from({ length: 5}, () => null);
   • 크기가 N(4) X M(5)인 2차원 배열 : Array.from(Array(4), () => new Array(5));

   let arr2 = new Array(3);
   for (let i = 0; i < arr2.length; i++) {
   	arr2[i] = Array.from(
   		{length: 4},
   		(_,j) => i * 4 + j
   	);
   }
   console.log(arr2);
    
   // ---- 결과 -----
   [
   	[ 0, 1, 2, 3 ],
   	[ 4, 5, 6, 7 ],
   	[ 8, 9, 10, 11 ]
   ]

배열의 대표적인 메서드

• concat() : 여러 개의 배열을 이어 붙여서 합친 결과를 반환한다. O(N)
• slice(left, right): 특정 구간의 원소를 꺼낸 배열을 반환한다. O(N)
• indexOf() : 특정한 값을 가지는 원소의 첫째 인덱스를 반환한다. O(N)

연결 리스트(Linked List)

• 연결 리스트는 컴퓨터의 메인 메모리 상에서 주소가 연속적이지 않다.
• 배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능하다.
• 장점 : 포인터(Pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다
• 단점 : 특정 번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다.
• 각 노드가 한 줄로 연결되어 있는 자료 구조로, 각 노드는 (데이터, 포인터) 형태를 가진다.
• 포인터 : 다음 노드의 메모리 주소를 가리키는 목적으로 사용된다.
• 연결성 : 각 노드의 포인터는 다음 혹은 이전 노드를 가리킨다.

• 연결 리스트를 이용하면 다양한 자료구조를 구현할 수 있다 (예시: 스택, 큐 등)

연결 리스트 vs 배열

• 특정 위치의 데이터를 삭제할 때

  • 배열 : O(N)

  • 연결 리스트 : O(1) ← 위치를 정확히 알고 있는 경우, 단순히 연결만 끊어주면 되기 때문

    

• 삽입 연산을 실행할 때

  • 연결 리스트 : 앞에 있던 원소가 새 원소의 헤드를 가리키도록 만들어주고, 새 원소의 포인터가 기존 다음 원소를 가리키도록 만들기

    

• 뒤에 붙이기(Append) 연산
  • 연결 리스트 : 마지막 조드의 다음 위치에 새로운 원소를 추가