[Javascript] 자료구조 - 배열(Array)과 리스트(List)

배열(Array)

가장 기본적인 자료구조

여러개의 변수를 담는 공간

배열은 인덱스(index)가 존재, 인덱스는 0부터 시작

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

 

배열의 특징

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

• 장점: 캐시 히트 가능성이 높으며 조회가 빠르다.
• 단점: 배열의 크기를 미리 지정해야하는것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.

 

연결 리스트(Linked List)

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

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

• 장점: 포인터(pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다.
• 단점: 특정 번째의 원소를 검색 할 때, 앞에서부터 원소를 찾아야 해서 데이터 검색 속도가 느리다.

 

Javascript에서는 배열 기능 제공

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

**큐의 기능은 제공하지 못한다.(비효율적)

 

Javascript 배열 초기화

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() 사용

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

 

* 일반적인 변수 외에도 객체를 담을 수 있다.

let arr = ["Hello", 777, true];

console.log(arr);

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

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

 

* 2차원 배열 또한 직접 값을 넣어 초기화 가능

//최신 Javascript 환경에서 한줄로 2차원 배열을 초기화 할 수 있음

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

console.log(arr);

//출력
[
    [ <5 empty items> ],
    [ <5 empty items> ],
    [ <5 empty items> ],
    [ <5 empty items> ]
]

//반복문을 이용해 배열 초기화
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]
]

 

* 배열 값 추가

let arr = [0,1,2,3];

arr.length = 5; // 배열 갯수 변경

arr[5] = 5
arr.push(6);

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

// 출력
0
1
2
3
undefined
5
6

 

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); // index 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)); // 2
console.log(arr.indexOf(8)); // -1

 

연결 리스트(Linked List)

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

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

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

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

- 삽입(Insert)연산 : 삽입할 위치를 알고있다면 물리적 위치를 한 칸씩 옮기지 않아도 삽입할 수 있다.

- 삭제(Remove)연산 : 삽입할 위치를 알고있다면 물리적 위치를 한 칸씩 옮기지 않아도 삭제입할 수 있다.

- 뒤에 붙이기(Append)연산 : 마지막 노드의 다음 위치에 원소를 넣으면 된다.