[알고리즘] 2-2. 배열과 리스트

# 배열(Array)

- 가장 기본적인 자료구조다.

- 여러 개의 변수를 담는 공간으로 이해할 수 있다.

- 배열은 인덱스(index)가 존재하며, 인덱스는 0부터 시작한다.

- 특정한 인덱스에 직접적으로 접근 가능 -> 수행 시간: O(1)

 

# 배열의 특징

- 컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다.

 장점: 캐시(cache) 히트 가능성이 높으며, 조회가 빠르다.

 단점: 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.

 

# 연결리스트(Linked List)

- 연결 리스트는 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다.

- 배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능하다.

  장점: 포인터(pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다.

  단점: 특정 번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다.

- 연결 리스트를 직접 구현하지 않아도 대부분의 알고리즘 문제를 해결하기에는 어려움이 없다.

 

# 자바스크립트의 배열

- 자바스크립트의 배열은 일반 배열처럼 임의의 인덱스를 이용해 직접적인 접근이 가능하다.

- 자바스크립트의 배열은 동적 배열의 기능을 제공하여, 맨 뒤의 위치에 원소 추가가 가능하다.

- 자바스크립트의 배열 자료형은 동적 배열이다.

- 배열의 용량이 가득 차면, 자동으로 크기를 증가시킨다.

- 내부적으로 포인터(pointer)를 사용하여, 연결 리스트의 장점도 가지고 있다.

- 배열(array) 혹은 스택(stack)의 기능이 필요할 때 사용할 수 있다.

- 큐(queue)의 기능을 제공하지 못한다.(비효율적)

 

# 자바스크립트 배열 초기화

1. 대괄호 사용하기

- 자바스크립트에서는 대괄호를 이용해 간단히 배열을 생성할 수 있다.

//빈 배열 생성
let arr = [];

arr.push(7);
arr.push(8);
arr.push(9);

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


결과
// 7
// 8
// 9

 

2. Array() 사용하기

- 자바스크립트에서는 Array()를 이용해 간단히 배열을 생성할 수 있다.

let arr = new Array();

arr.push(7);
arr.push(8);
arr.push(9);

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

결과
// 7
// 8
// 9

 

3. 

- 자바스크립트의 배열은 일반적인 변수 외에도 객체를 담을 수도 있다.

let arr = ["Hello", 777, true];
console.log(arr);

결과
// ['Hello', 777, true]

 

4.

- 자바스크립트에서는 임의의 크기를 가지는 배열을 만들 수 있다.

- 원하는 값을 직접 입력하여 초기화 할 수 있다.

- 크기가 N인 1차원 배열을 만드는 방법은 다음과 같다.

// 원하는 값을 직접 입력하여 초기화
let arr1 = [0, 1, 2, 3, 4];
console.log(arr1);

// 하나의 값으로 초기화
let arr2 = Array.from({ length: 5}, ()=> 7);
console.log(arr2);

결과
// [0, 1, 2, 3, 4]
// [7, 7, 7, 7, 7]

 

# 크기가 N X M인 2차원 리스트(배열) 만들기 ①

- 2차원 배열이 필요할 때는 다음과 같이 원하는 값을 직접 넣어 초기화할 수 있다.

// 원하는 값을 직접 입력하여 초기화
let arr1 = [
 [0, 1, 2, 3],
 [4, 5, 6, 7],
 [8, 9, 10, 11]
];
console.log(arr1);


결과
[
  [0, 1, 2, 3],
  [4, 5, 6, 7],
  [8, 9, 10, 11]
]

 

# 크기가 N X M인 2차원 리스트(배열) 만들기 ②

- 최신 자바스크립트 환경(ES6 이상)에서 사용할 수 있는 문법이다.

- 한 줄로 2차원 배열을 초기화할 수 있다.

- 배열의 각 원소에 크기가 5인 배열을 할당한다.

let arr = Array.from(Array(4), () => new Array(5))

console.log(arr);


결과
[
  [ <5 empty items > ],
  [ <5 empty items > ],
  [ <5 empty items > ],
  [ <5 empty items > ]
]

 

# 크기가 N X M인 2차원 리스트(배열) 만들기 ③

- 다음과 같이 반복문을 이용해 2차원 배열을 초기화할 수 있다.

// 반복문을 이용해 배열 초기화
let arr2 = new Array(3);
for(let i=0; i< arr2.length; i++){
  arr2[i] = Array.from(
    { length: 4 },
    (undefined, j) => i * 4 + j
  );
}
console.log(arr2);


결과
[
  [0, 1, 2, 3],
  [4, 5, 6, 7],
  [8, 9, 10, 11]
]

 

# 자바스크립트 배열 다루기

- 자바스크립트의 배열은 동적 배열이다.

- 배열이 생성된 이후에도 배열의 크기를 임의로 변경할 수 있다.

- push() 메서드를 통해 배열의 가장 뒤쪽에 새로운 원소를 추가할 수 있다.

let arr = [5, 6, 7, 8, 9];
arr.length = 8;
arr[7] = 3;
arr.push(1);

for(let x for arr) {
  console.log(x);
}


결과
5
6
7
8
9
undefined
undefined
3
1

 

# 자바스크립트 배열의 대표적인 메서드①

- concat(): 여러 개의 배열을 이어 붙여서 합친 결과를 반환한다. O(N)

let arr1 = [1, 2, 3, 4, 5];
let arr2 = [6, 7, 8, 9, 10];
let arr = arr1.concat(arr2, [11, 12], [13]);

console.log(arr);


결과
[
  1,2,3,4,5,6
  7,8,9,10,11,12,13
]

 

# 자바스크립트 배열의 대표적인 메서드②

- slice(left, right): 특정 구간의 원소를 꺼낸 배열을 반환한다. O(N)

let arr = [1,2,3,4,5];
let result = arr.slice(2,4);

console.log(result);


결과
[3, 4]

 

# 자바스크립트 배열의 대표적인 메서드③

- indexOf() : 특정한 값을 가지는 원소의 첫째 인덱스를 반환한다. O(N)

- 만약 해당하는 원소가 없는 경우 -1을 반환한다.

let arr = [7, 3, 5, 6, 6, 2, 1];

console.log(arr.indexOf(5));
console.log(arr.indexOf(6));
console.log(arr.indexOf(8));


결과
2
3
-1

 

# 연결 리스트(Linked List)

- 각 노드가 한 줄로 연결되어 있는 자료 구조다.

- 각 노드는 (데이터, 포인터) 형태를 가진다.

- 포인터: 다음 노드의 메모리 주소를 가리키는 목적으로 사용된다.

 

- 연결성: 각 노드의 포인터는 다음 혹은 이전 노드를 가리킨다.

 

- 연결 리스트를 이용하면 다양한 자료구조를 구현할 수 있다.

- 예시) 스택, 큐 등

- 자바스크립트는 연결 리스트를 활용하는 자료구조를 제공한다.

- 그래서 연결 리스트를 실제 구현해야 하는 경우는 적지만, 그 원리에 대해서 이해해야할듯하다.

 

# 연결리스트 vs 배열

- 특정 위치의 데이터를 삭제할 때, 일반적인 배열에서는 O(N)만큼의 시간이 소요된다.

- 하지만, 연결 리스트를 이용하면 단순히 연결만 끊어주면 된다.

- 따라서 삭제할 위치를 정확히 알고 있는 경우 O(1)의 시간이 소요된다.