배열
- 가장 기본적인 자료구조다.
- 여러 개의 변수를 담는 공간으로 이해할 수 있다.
- 배열은 인덱스(index)가 존재하며, 인덱스는 0부터 시작한다.
- 특정한 인덱스에 직접적으로 접근 가능 -> 수행 시간: O(1)
배열의 특징
- 컴퓨너의 메인 메모리에서
배열의 공간은 연속적으로 할당된다.
장점 : 캐시(cache) 히트 가능성이 높으며, 조회가 빠르다.
단점 : 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.
연결 리스트(Linked List)
- 연결 리스트는 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다.
- 배열과 다르게 크기가 정해져 있지 않고,
리스트의 크기는 동적으로 변경 가능하다.
장점: 포인터(pointer)를 통해다음 데이터 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다.
단점: 특정 번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다.
JavaScript의 배열
- JavaScript에서는 배열 기능을 제공한다.
- 배열의 용량이 가득 차면, 자동으로 크기를 증가시킨다.
👉🏻 배열의 사이즈를 정해둘 필요없이 뒤에 추가적으로 새 원소를 넣을 수 있다. - 내부적으로 포인터(pointer)를 사용하여, 연결 리스트의 장점도 가지고 있다.
- ✨배열(array) 혹은 스택(stack)의 기능이 필요할 때 동적 배열을 사용할 수 있다.
[참고] 큐(queue)의 기능을 제공하지 못한다.(비효율적)
👉🏻 큐는 별도로 따로 구현
알아둘 점
- 일반적인 프로그래밍 언어에서의 배열로 이해할 수 있다.
- JavaScript의 배열은
일반 배열처럼임의의 인덱스를 이용해 직접적인 접근이 가능하다. - JavaScript의 배열은 동적 배열의 기능을 제공하여, 맨 뒤의 위치에 원소 추가가 가능하다.
JavaScript 배열 초기화-1.대괄호 사용하기
- JavaScript에서는 대괄호를 이용해 간단히 배열을 생성할 수 있다.
// 빈 배열 생성
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
// 9JavaScript 배열 초기화-2.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
// 9JavaScript 배열 초기화
- JavaScript에서는 임의의 크기를 가지는 배열을 만들 수 있다.
- 원하는 값을 직접 입력하여 초기화 할 수 있다.
- 크기가 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 ]크기가 NxM인 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]
// ]- ES6 이상의 JavaScript에서 사용할 수 있는 문법
- 한 줄로 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> ]
]- 다음과 같이 반복문을 이용해 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]
]JavaScript 배열 다루기
- JavaScript의 배열은 동적 배열
- 배열이 생성된 이후에도 배열의 크기를 임의로 변경할 수 있다.
- push() 메서드를 통해
배열의 가장 뒤쪽에 새로운 원소를 추가할 수 있다.
let arr = [5,6,7,8,9];
arr.length = 8; // 길이 늘려주기
arr[7] = 3;
arr.push(1);
for (let x of arr) { // 특정 배열의 원소에 차례대로 접근할 때 사용할 수 있는 문법
console.log(x);
}
// 실행 결과
5
6
7
8
9
undefined
undefined
3
1JavaScript 배열의 대표적인 메서드
concat()
- concat() : 여러 개의 배열을 이어 붙여서 합친 결과를 반환한다. O(N)
👉🏻 모든 원소를 하나씩 확인해봐야한다는 측면에서 복잡도는 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()
- slice(left, right) : 특정 구간의 원소를 꺼낸 배열을 반환한다. O(N)
let arr=[1,2,3,4,5];
let result = arr.slice(2,4);
console.log(result);
// 실행 결과
[3, 4]indexOf()
- 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)
- 연결 리스트는 각 노드가 한 줄로 연결되어 있는 자료 구조다.
- 각 노드는 (데이터, 포인터) 형태를 가진다.
- 포인터 : 다음 노드의 메모리 주소를 가리키는 목적으로 사용된다.
- 연결성 : 각 노드의 포인터는 다음 혹은 이전 노드를 가리킨다.
- 연결 리스트를 이용하면 다양한 자료구조를 구현할 수 있다.
- 예시) 스택, 큐 등
- JavaScript는 연결 리스트를 활용하는 자료구조를 제공한다.
- 그래서 연결 리스트를 실제 구현해야 하는 경우는 적지만, 그 원리에 대해서 이해하는 것이 좋다.
연결 리스트(Linked List) vs 배열(Array)
- 특정 위치의 데이터를 삭제할 때, 일반적인 배열에서는 O(N)만큼의 시간이 소요된다.
- 하지만, 연결 리스트를 이용하면 단순히 연결만 끊어주면 된다.
- 따라서 삭제할 위치를 정확히 알고 있는 경우 O(1)의 시간이 소요된다.
연결 리스트(Linked List) : 삽입(Insert) 연산
- 삽입할 위치를 알고 있다면, 물리적인 위치를 한 칸씩 옮기지 않아도 삽입할 수 있다.
- 인덱스 2의 위치에 원소를 삽입
- 인덱스 2의 위치의 원소를 삭제
연결 리스트(Linked List) : 뒤에 붙이기(Append)연산
- 뒤에 붙일 때는 마지막 노드의 다음 위치에 원소를 넣으면 된다.
hello, world!