ksw_devlog

Array는 연속된 메모리 공간에 존재하고 Linked List는 메모리 상에서 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태로 존재한다. Array에 저장되어 있는 데이터를 조회할 때는 O(1)로 가능하지만 Linked List는 O(N)이 소요된다. Array에 데이터 추가 및 삭제할 때는 O(N)이 소요되지만 Linked List는 O(1)로 가능하다. 추가적으로 Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면 Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다. 또한 배열은 Stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.

스택 (Stack) 이란? 스택(Stack) 자료구조는, 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 의미한다. 즉, 후입선출(LIFO, Last In First Out) 방식의 자료구조이다. 스택의 특징 스택 내부의 데이터는, top 을 통해서만 접근할 수 있다. top 은 가장 최근(마지막)에 들어온 자료를 의미한다. 스택에 데이터를 삽입할 때는, top 위에 쌓게 되며 ('push' 연산) 스택에서 데이터를 삭제할 때는, top 에 위치한 데이터를 삭제하게 된다. ('pop' 연산) 즉, 스택은 시간 순서에 따라 데이터가 쌓이게 되므로, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 특징을 가지게 된다. 이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조..