자료구조 | 배열, 연결 리스트 추상 자료형

자료구조, 나한테 설명하며 공부해보자!

 

정성스러운 손 필기 ✍🏻 (클릭)

 

자료구조 - 배열

- (일반) 프로그래밍 언어에서의 배열의 특징

(일반적인) 프로그래밍 언어에서는 배열을 선언할 시 '배열의 크기'를 알려준다. 우리는 10개를 담아본다고 가정하자.

나: 10개의 데이터를 보관할 배열이 필요해.

 

운영체제는 배열 크기만큼 들어갈 수 있는 연속된 빈 공간을 메모리에서 찾아서 순서대로 할당한다.

(배열 크기는 지정되었고, 아직 할당하지 않은 부분에는 의미 없는 값이 저장되어 있는 상태이다.)

운영체제: 메모리에 연속된 빈 공간을 찾아보자. (찾는 중) 여기에 차례대로 할당할게~

 

할당 후 운영체제는 배열의 시작 주소만 기억한다.

(운영체제는 배열의 시작 주소를 알고 있기 때문에, 시작 주소로부터 얼마나 떨어진 곳에 데이터가 있는지 '바로' 알 수 있다.)

 

배열의 index 참조(읽기/쓰기)는 배열의 길이에 상관 없이 단번에 가져올 수 있기 때문에,

O(1)의 성능을 가진다.

 

그런데, 갑자기 해당 배열의 크기를 15로 늘리고 싶다.

나: 운영체제야. 배열 크기를 10이 아닌 15로 늘려야 할 것 같은데.

운영체제 : ??? 이미 10개 할당해둔 데이터 바로 뒤에는 중요한 데이터가 있어서 늘리기 어려운데... 잠시만....

 

운영체제는 크기 연속된 15의 데이터 공간을 메모리에서 다시 찾아야 한다.

그리고 이전에 기록해둔 데이터 값을 복사해 새로운 메모리에 다시 옮겨야 한다.

 

배열은 연속된 빈 공간을 갖는다는 특성 때문에, 데이터의 삽입/삭제 성능은 좋지 않다.

 

나: 처음부터 그냥 크게 만들면 되지 않아?

운영체제: 그러면 메모리가 낭비되잖아.

크기 예측도 어려워 메모리 낭비가 발생할 수 있다.

 

- 배열의 장점

 : O(1)의 성능을 가진다 = 배열의 참조(읽기/쓰기) 성능이 좋다

- 배열의 단점

 : 데이터의 삽입, 삭제 성능이 좋지 않다. 크기 예측이 어려워 메모리 낭비가 발생할 수 있다.

 

 

- JS에서 배열의 특징

왜 위의 제목을 '일반적인' 프로그래밍 언어에서의 배열이라고 했느냐라고 하면, JS에서는 배열이 조금 특별하다.

우리는 문법을 처음 접할 때 (이게 왜 쓰이는지는 아직 모르겠지만 이라는 마음으로) 배열의 데이터 삽입, 삭제 등을 공부한다.

 

JS에서 배열은 메모리 내 '불연속적'으로 할당된다고 생각하면 된다.

불연속적으로 할당된 메모리를 → 내부적으로 연결해서

 → 사용자는 '배열'처럼 느끼게 된다. (데이터를 연결해서 저장)

(위에 참조된 사진 내 그림 참고)

 

 

자료구조 - 연결 리스트

- 배열의 단점을 해결하기 위한 방법

과학자 : 데이터를 빈 메모리 공간에 분산 할당하고, 데이터를 서로 연결하자!

 

필요한 데이터만큼 빈 메모리 공간에 자유롭게 '노드'를 만들어 데이터를 저장하고,

 → 다른 노드를 가리켜(연결)

 

배열의 초기 크기를 알 필요가 없다!

 

 

- 연결 리스트로 데이터를 어떻게 저장해?

노드 생성 ( data, next ) : 데이터를 담는 변수와, 다음 누구를 연결하면 되는지 변수를 담는 노드를 생성

(이해하기 쉽게 소괄호로 묶었다)

노드 연결 : next에 어느 노드로 연결할지 정보를 담는다.

 

배열처럼 첫 노드의 주소를 알면 다른 노드에 (타고 타고 가서) 접근이 가능하다!

 

다만, 연결 리스트의 데이터를 참조(읽기/쓰기), 삽입, 삭제는 노드를 따라가서 확인해야 하므로

O(n)의 성능을 가진다.

 

 

배열 VS 연결리스트

- 데이터 수가 자주 바뀌지 않고, 참조가 자주 일어난다 : 배열 추천

- 데이터 삽입/삭제가 자주 일어나 데이터 수가 자주 바뀐다 : 연결 리스트 추천

 

 

연결 리스트의 추상 자료형(JS)

추상 자료형(Abstract Data Type)?

구현하고자 하는 구조의 구체적 기능의 진행 과정을 언급하는 것이 아닌, 데이터의 연산 기능을 표기하는 것
(규칙의 나열이라고 보면 이해하기 쉽다)

예) 세탁기 : 탈수..

 

추상자료형	설명
printAll()	1. 모든 데이터 출력
clear()	2. 모든 데이터 제거
insertAt(index, data)	3. 인덱스 삽입
insertLast(data)	4. 마지막 삽입
deleteAt(index)	5. 인덱스 삭제
deleteLast()	6. 마지막 삭제
getNodeAt(index)	7. 인덱스 읽기

 

 

다음 시간은 자료구조 - 스택(Stack)과 큐(Queue)에 대해 알아보자

:D