[ 자료구조 ] 배열 Array & 연결리스트 Linked List & 스택 Stack

비주얼고 ➡️시각적으로 볼 수 있다

배열 (Array)

• 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조
• 연속적 ➡️ index 를 통한 접근 용이하다
• 배열의 크기는 처음 생성할 때 정해지며 이후에 변경할 수 없다

연결리스트 (Linked List)

• 노드(data 와 link 필드를 갖고 있는 구조체)들이 연결되어있는 구조 ➡️ 노드들의 집합
• 각 노드는 다음에 올 노드의 정보(next pointer)를 갖고 있다 (다음 노드가 없는 경우 null 저장)
• 맨 앞을 Head, 맨 마지막을 Tail 이라고 한다
• 중간에 있는 노드는 추적하지 않는다 ➡️ 순차적으로 첫 노드부터 읽어나가야 한다
• 삽입과 삭제를 할 때 참조하고 있던 주소를 끊어주거나 연결해주면 되기 때문(간단)에 배열의 단점을 해결하는 자료구조이다(참조되지 않는 값은 garbage collector가 제거)

연결리스트 vs 배열 

	특징	크기	주소값	참조 (읽기/쓰기)	수정 (추가/제거) 재구성	시간복잡도 Big-O	공간복잡도	메모리 사용
배열	- 동일한 데이터 타입 - index(순서)가 있다 - 랜덤 엑세스가 빠르다	고정적	연속적	좋음	안 좋음	접근하고자 하는 데이터의 인덱스 값을 알고 있을 때 : O(n) 순차적으로 데이터에 접근 할 때: O(n)	좋음	비효율적 사용
연결리스트	- 각 데이터가 한 줄로(순차적으로) 연결 - 각각의 데이터는 자신의 바로 다음 참조 데이터 값과 본인의 값을 가지고 있음 - 대용량 데이터 처리에 적합하다	동적	비연속적	안 좋음	좋음	O(n)	안 좋음	효율적 사용

 

연결리스트의 시간복잡도

• 탐색: O(n)
• 삽입 및 삭제: 삽입과 삭제 자체는 O(1)이다
  • 연결리스트의 처음에 삽입 및 삭제: O(1)
  • 연결리스트의 중간에 삽입: O(n) (탐색시간 소요)
  • 연결리스트의 끝에 삽입 및 삭제:
    • 끝을 가리키는 별도의 포인터를 갖는 경우: O(1)
    • 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n)

연결리스트 구현

출처

class Node {

constructor(data, next = null) {

this.data = data;

this.next = next;

}

}



class LinkedList {

constructor() {

/** Head Node */

this.head = null;

/** 연결리스트 길이 */

this.count = 0;

}



/**

 * 모든 데이터 출력

 *

 * 1. currentNode에 head를 할당

 * 2. currentNode가 null이 아닐 때까지 반복

 * 3. currentNode의 data를 출력

 * 4. currentNode에 currentNode의 next를 할당

 * 5. 마지막에 text에 ']'를 추가

 * 6. text를 출력

 *

 */

printAll() {

let currentNode = this.head;

let text = '[';



while (currentNode !== null) {

text += currentNode.data;

currentNode = currentNode.next;



// 마지막 노드인지 확인

if (currentNode !== null) {

text += ',';

}

}



text += ']';

console.log(text);

}



/**

 *

 * 모든 데이터 제거

 *

 * 연결리스트의 상태를 초기화 해준다.

 *

 */

clear() {

this.head = null;

this.count = 0;

}



/**

 *

 * @param {number} index

 * @param {} msg

 *

 * 유효성 검사

 *

 * index가 0보다 작거나 count보다 크면 에러를 발생시킨다.

 *

 */

_validation(index, msg = '범위를 벗어났습니다.') {

if (index > this.count || index < 0) {

throw new Error(msg);

}

}



/**

 * 원하는 인덱스에 노드 삽입

 *

 * newNode 변수에 Node 생성자 인수에 data를 넣어서 할당

 *

 * case A. index가 0일 때

 * 1. 새로운 노드의 next에 head를 넣어준다.

 * 2. head에 새로운 노드를 넣어준다.

 *

 * case B. index가 0이 아닐 때

 * 1. currentNode를 head로 초기화

 * 2. for문을 통해 삽입하려는 곳의 이전 노드까지 이동

 * 3. newNode의 next를 currentNode(삽입 하려는 인덱스 바로 이전)의 next(삽입하려했던 인덱스)로 설정

 * 4. currentNode의 next를 newNode로 설정

 *

 * 정상적으로 동작 확인되어 count++

 *

 */

insertAt(index, data) {

this._validation(index);



let newNode = new Node(data);



if (index === 0) {

newNode.next = this.head;

this.head = newNode;

} else {

let currentNode = this.head; // 현재 노드에 head를 할당



for (let i = 0; i < index - 1; i++) {

currentNode = currentNode.next;

}



newNode.next = currentNode.next;

currentNode.next = newNode;

}



this.count++;

}


/**

 *

 * 연결리스트 마지막에 노드 삽입

 *

 * insertAt 메서드를 사용하여 마지막에 노드를 삽입한다.

 *

 */

insertLast(data) {

this.insertAt(this.count, data);

}



/**

 *

 * 인덱스 삭제

 *

 * index 유효성 검증

 *

 * case A. index가 0일 때

 * 1. head에 head의 next를 할당

 * 2. head의 next를 null로 설정

 *

 * case B. index가 0이 아닐 때

 * 1. 삭제하려는 인덱스의 이전까지 이동

 * 2. 삭제하려는 인덱스의 next를 삭제하려는 인덱스의 이전 노드의 next에 할당

 *

 * 삭제되었으니 카운트 감소

 */

deleteAt(index) {

this._validation(index, '제거할 수 없습니다.');



let currentNode = this.head;



if (index === 0) {

let deleteNode = this.head;

this.head = this.head.next;

this.count--;

return deleteNode;

} else {

for (let i = 0; i < index - 1; i++) {

currentNode = currentNode.next;

}



let deleteNode = currentNode.next;



currentNode.next = currentNode.next.next;

this.count--;

return deleteNode;

}

}



/**

 *

 * 마지막 삭제

 *

 * deleteAt 메서드를 사용하여 마지막 노드를 삭제한다.

 *

 */

deleteLast() {

return this.deleteAt(this.count - 1);

}



/**

 *

 * 인덱스 참조

 *

 * 1. index 유효성 검증

 * 2. 삭제하려는 index까지 이동

 *

 */

getNodeAt(index) {

this._validation(index);



let currentNode = this.head;

for (let i = 0; i < index; i++) {

currentNode = currentNode.next;

}



return currentNode;

}

}



export { Node, LinkedList };

연결리스트 사용 예시

• 뮤직 플레이어
• 웹 브라우저에서 여러 사이트를 돌아다닐 때, 다른 사이트로 넘어갈 때, 이전 사이트의 정보(방문기록(history))를 가지고 넘어감

스택 Stack

• LIFO(Last In First Out,후입선출)의 자료구조 ➡️ 입구와 출구가 같다
• 제한적으로 접근할 수 있는 자료구조

스택의 추상자료형

method name	params	rule
pop()	{}	스택에서 가장 위에 있는 항목 제거 ➡️ 데이터 삽입
push(item)	{}	item 하나를 스택의 가장 윗 부분에 추가 ➡️ 데이터 제거
peek()	{}	스택의 가장 위에 있는 항복 반환 ➡️ 데이터 참조
isEmpty()	{}	스택이 비어 있을 때 true 반환 ➡️ 비어있는지 확인

 

 

스택의 장점

• 구조가 단순해서 구현이 쉽다
• 참조(읽기/쓰기)에 좋다

스택의 단점

• 데이터 크기를 미리 정해야 한다
• 저장 공간 낭비가 일어날 수 있다

스택오버플로우(Stack Overflow)

• 콜스택에 너무 많은 데이터가 쌓여 에러가 발생하는 상황
• 발생원인
  • 함수에서 너무 큰 지역 변수 선언
  • 재귀함수 무한정 호출
  • 상호 참조: 두 클래스 간에 생성을 위임하면서 체이닝을 이루게 되면 발생
  • 본인 참조: 본인 클래스 내에서 본인을 생성 ➡️ 무한 반복

스택 구현

출처

배열로 구현

class ArrayStack {

// static SIZE = 1000;

constructor(size = 1000) {

this.stack = new Float32Array(size);

this.top = -1;

this.size = size;

}



push(data) {

if (typeof data !== 'number') {

throw new Error('숫자를 입력해주세요');

}



if (this.top === this.size - 1) {

throw new Error('스택이 가득 찼습니다 (Stack Overflow) \n');

}



this.stack[++this.top] = data;

}



pop() {

if (this.top === -1) {

console.error('스택이 비어있습니다 (Stack Underflow)');

return null;

}



return this.stack[this.top--];

}



peek() {

return this.stack[this.top];

}



isEmpty() {

return this.top < 0;

}

}



export { ArrayStack };

 

연결리스트로 구현

import { LinkedList } from '../../00_LinkedList/index';



class Stack {

constructor() {

this.list = new LinkedList();

}



push(data) {

this.list.insertAt(0, data);

}



pop() {

try {

return this.list.deleteAt(0);

} catch (error) {

return null;

}

}



peek() {

return this.list.getNodeAt(0);

}



isEmpty() {

return this.list.count === 0;

}

}



export { Stack };

 

 

스택 사용 예시

• 재귀 알고리즘
• 웹 브라우저 방문기록(뒤로가기) : 나장 나중에 열린 페이지부터 다시 보여준다
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다
• 실행 취소(undo)
• 후위(postfix)표기법 계산
• 구문 분석 : 수식의 괄호 검사