[자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 - 자바스크립트 자료구조(배열과 리스트)

[자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 -  자바스크립트 자료구조(배열과 리스트)

오늘은 자바스크립트 자료구조 중에서 배열과 리스트에 대해 공부했다.

당장 이해되지 않고 모르는 것이 많더라도 킵고잉 ~~ :)

 

 

[자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 - 자바스크립트 자료구조(배열과 리스트)

 

 

 

자바스크립트 자료구조 - 배열과 리스트

 

1. 배열(Array)

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

2. 여러개의 변수를 담는 공간으로 배열은 인덱스(index)가 존재한다. ⇒ 배열의 인덱스는 0부터 시작

3. ⭐️ 특정 인덱스에 직접적으로 접근이 가능하다.

• 수행시간 O(1) - 상수시간

4. 컴퓨터 메모리상에서 배열은 연속적으로 할당된다.

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

배열 자료구조 메모리 저장 형태

 

 

 

---

 

 

 

 

2. 연결리스트(Linked list)

1. 어떤 데이터들을 일렬로 보관할 때 사용

2. 컴퓨터 메모리상에서 배열과 달리 주소가 연속적이지 않는다.

3. 크기가 정해져있지않다. ⇒ 즉, 리스트의 크기는 동적이다.

• 장점: 포인터를 통해 다음 데이터의 위치를 가리킨다는 점에서 데이터의 추가 삭제가 간편.
• 단점: 특정 n번째 원소를 찾을 때에는 앞에서 부터 원소를 찾은 뒤 포인터를 따라 검색해야 하므로 데이터의 검색 속도가 느리다.

연결리스트 자료구조 메모리 저장 형태

 

 

요약: 배열은 조회가 빠르고 연결리스트는 데이터의 추가 삭제가 간편하다.

 

 

 

---

 

 

 

참고: 자바스크립트에서의 배열은

1. 동적 배열이다.
2. 용량이 가득차면 자동으로 크기를 키운다.
3. 내부적으로 포인터 기능이 있어서 연결리스트의 장점을 보유하고 있다.
4. array / stack 기능이 필요할 때 사용 가능하다.
5. 하지만, 큐(queue)의 기능이 없다. (비효율적)

 

 

 

---

 

 

코딩테스트에 주로 사용되는 배열 메서드

1. from() - 중첩배열
2. push() - 마지막 원소 추가
3. concat() - 배열끼리 이어붙임
4. slice() - 특정 구간 원소를 꺼내서 반환
5. indexOf() - 배열 내 특정값 중에 첫번째 index

 

 

---

 

 

반응형

 

 

3. 데이터의 삽입과 삭제 - 배열 vs 연결리스트

1. 배열

- 특정 위치의 데이터 추가/삭제시 일반배열은 O(n)의 시간 소요.

배열의 데이터 삽입

위와 같이, 삽입 시 데이터의 메모리 주소가 한 칸씩 이동하므로 배열에서의 데이터 삽입/삭제는 비효율적

 

2. 연결리스트

- 연결리스트는 단순히 연결만 끊어주면 되어서 효율적

- 삭제 위치를 ‘정확히’ 알고 있다면 O(1)의 시간 소요.

연결리스트의 데이터 삽입

위와 같이 기존 데이터와의 연결을 끊고 새로운 포인터를 지정하면 되므로 데이터의 삽입/삭제에 용이