Array & LinkedList / Stack & Queue

Array와 LinkedList 

배열과 링크드리스트는 데이터를 저장하고 관리하는데 사용되는 두 가지 기본적인 자료구조이다.

배열

연속된 메모리 공간에 데이터를 저장한다.

인덱스를 사용해 원소에 빠르게 접근할 수 있다. 

고정된 크기를 가지며, 크기변경이 어렵다. 미리 할당된 메모리 크기를 초과하면 새로운 메모리 공간을 할당하고 데이터를 복사해야합니다.

원소를 삽입하거나 삭제할때, 원소들을 이동시켜야 하므로 시간이 오래 걸릴 수 있습니다. 

메모리 사용이 효율적이다. 각 원소는 인덱스로 접근되며, 추가적인 메모리를 사용하지 않는다.

 

링크드 리스트

각 노드가 데이터와 다음 노드에 대한 참조포인터를 포함하며, 노드들이 연속되지 않은 메모리 공간에 저장된다.

원소에 접근하기 위해서 리스를 순차적으로 탐색해야 한다.

크기변경이 쉽다. 새 노드를 동적으로 할당하거나 제거함으로 리스트의 크기 변경이 가능

원소를 삽입하거나 삭제할때, 포인터만 업데이트 하면 되므로 상대적으로 빠른 시간에 처리할 수 있다.

단, 삽입이나 삭제할 위치를 찾는 과정은 O의 시간 복잡도를 가진다.

메모리 사용이 비효율적일 수 있다. 각 노드는 데이터와 포인터를 저장해야하므로, 추가적인 메모리를 사용한다.

 

=> 배열은 인덱스를 사용한 빠른 접근이 필요하거나 크기가 고정된 경우에 적합하며, 링크드 리스트는 데이터의 삽입과 삭제가 빈번하게 발생하거나 크기가 가변적인 경우에 적합합니다.

Stack과 Queue

	스택	큐
자료구조	LIFO (Last In, First Out)	FIFO (First In, First Out)
연산	push(삽입), pop(삭제)	enqueue(삽입), dequeue(삭제)
활용 사례	함수 호출, 괄호 짝 맞추기, 후위 표기법 계산 등	프린터 대기열, 버퍼 관리, 스케줄링 알고리즘 등
구현 방법	배열, 연결리스트	배열, 연결리스트

 

스택은 LIFO 구조를 가진 자료구조로, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조이다.(뒤로가기)

반면, 큐는 FIFO 구조를 가지며, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조이다.(대기인원이 있는 화면) 이러한 차이로 인해 스택과 큐는 서로 다른 상황에서 활용된다.

 

연산의 차이

스택은 데이터를 삽입하는 push, pop 연산을 제공한다. 데이터는 항상 스택의 가장 상단에 추가되거나 제거된다.

반면, 큐는 데이터를 삽입하는 enqueue연산과 데이터를 삭제하면 dequeue 연산을 제공한다.

데이터는 큐의 뒤쪽에 추가되고, 앞쪽에서 제거됩니다.