<230120 TIL> 배열, 연결리스트, 스택

Hisu(히수)·2023년 1월 25일

배열 스택 스택오버플로우 연결리스트 자료구조

TIL

목록 보기

7/9

✨배열의 특징

데이터를 차례대로 나열한 선형 자료구조이다.
동일한 타입의 데이터를 저장하고 고정된 크기를 가지고 있다.
연속적인 메모리 공간에 순차적으로 데이터를 저장한다
유연하진 않지만, 값을 찾을 때 빠르다.
읽기/쓰기(참조)에 좋다.
추가/제거(수정)에는 좋지 않다.

✨연결리스트의 특징

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있다.
비연속적 주소값과 크기가 동적으로 변한다.
유연하지만, 값을 찾을 때 빠르진 않다.
읽기/쓰기(참조)에 좋지 않다.
추가/제거(수정)에 좋다.

그림처럼 추가 하거나 삭제하는데 매우 용이하다.

🔍배열과 연결리스트 비교

종류	크기	참조	수정	공간복잡도	시간복잡도
배열	고정적이다.	좋다	안좋다	좋다	O(1)
연결리스트	동적이다.	안좋다	좋다	안좋다	O(n)

✨스택의 특징

LIFO(Last In First Out, 후입선출) 구조의 자료구조이다.
구조가 단순해서 구현하기 쉽다.
읽기/쓰기(참조)에 좋다.
데이터 크기를 미리 정해야 된다.
저장공간의 낭비가 생길 수 있다.

🔔스택오버플로우(Stack Over flow)

콜스택에 데이터 입력이 계속 들어와서 한계치에 도달하면 오류가 발생한다.
함수에서 너무 큰 지역 변수를 선언했을 때 발생한다.
함수를 재귀로 무한하게 호출하면 발생한다.

const recur = (num) => {
  if (num === 0) return num;
  return num + recur(num - 1);
};
try {
    console.time(recur)
    recurRes = recur(50000);
    console.timeEnd(recur)
} catch (error) {
    console.error(error);
};

🔍스택의 추상자료형

Method name	params	rule	description
Push	push(Stack, Element);	데이터 삽입	스택의 가장 윗 부분에 추가
Pop	pop( Stack )	데이터 제거	스택의 가장 윗 부분 제거
Peek	peek( Stack )	데이터 참조	스택의 가장 위에 있는 항목 반환
IsEmpty	isEmpty()	비어있는지 확인	스택이 비어있다면 true 반환