1. 선형 메모리 (Linear Memory)
선형 메모리는 데이터가 연속적으로 저장되는 구조이다. 메모리 주소가 연속적이고 순차적으로 접근할 수 있다. 즉, 한 번에 데이터에 접근하는 것이 효율적이다. 선형 메모리의 예시는 **배열(Array)**와 **스택(Stack)**이 있다.
ex)
배열(Array): 배열은 메모리에서 연속적으로 할당된다. 배열의 인덱스를 통해 순차적으로 데이터를 읽고 쓸 수 있다. 배열의 각 원소는 메모리에서 연속적인 위치를 차지한다.
스택(Stack): 스택은 후입선출(LIFO) 방식으로 데이터를 저장한다. 스택은 메모리 상에서 연속적으로 데이터를 쌓아가며, 스택에 들어간 데이터는 나중에 들어간 데이터부터 빠져나온다.
메모리 배치:
- 스택(Stack): 함수 호출 시 생성되는 지역 변수들이 스택에 저장된다. 스택은 연속적인 메모리 공간을 사용하여, 함수가 끝나면 자동으로 메모리가 해제된다.
- 배열: 배열의 요소들은 메모리 상에서 연속된 위치에 저장되어, 배열 인덱스를 통해 빠르게 접근할 수 있다.
장점
- 빠른 접근 속도
- 데이터가 연속적으로 배치되어 있기 때문에, 메모리 내에서 인덱스를 통해 즉시 접근이 가능하다.
- 예측 가능한 성능
- 메모리 구조가 단순하므로, 성능 예측이 용이하다. 예를 들어, 배열이나 스택은 크기와 구조가 고정적이어서 특정 연산의 시간 복잡도를 쉽게 예측할 수 있다.
- 메모리 사용 효율
- 연속된 메모리 공간을 할당받기 때문에 메모리 단편화가 적고, 공간을 효율적으로 사용할 수 있다.
단점
- 유연성 부족
- 크기가 고정된 배열은 크기를 변경할 수 없기 때문에, 데이터를 추가하거나 삭제하는 데 유연성이 떨어진다. (스택과 큐도 유사)
- 공간 낭비
- 배열을 생성할 때 고정된 크기를 지정해야 하므로, 실제 사용되지 않는 공간이 발생할 수 있다.
- 동적 크기 할당의 어려움
- 동적으로 크기가 변하는 데이터를 처리할 때 배열을 사용하면 복잡도가 증가한다
2. 비선형 메모리 (Non-linear Memory)
비선형 메모리는 데이터가 연속적이지 않고, 논리적으로 연결된 방식으로 저장된다. 데이터가 메모리 상에서 비연속적으로 배치되고, 각 데이터 항목은 **포인터(혹은 참조)**를 통해 서로 연결된다. 비선형 메모리에서는 데이터들이 독립적인 메모리 공간에 저장되며, 포인터를 통해 연결된다.
ex)
링크드 리스트(Linked List): 링크드 리스트는 각 노드가 서로 다른 메모리 위치에 저장되며, 각 노드는 다음 노드를 가리키는 포인터를 포함한다. 데이터가 메모리 상에서 연속적으로 배치되지 않지만, 포인터를 통해 연결되어 있다.
트리(Tree): 트리 구조는 각 노드가 부모-자식 관계를 가지고 있으며, 각 노드는 자식 노드를 가리키는 포인터를 포함한다. 트리 구조는 여러 수준(level)으로 나뉘어 있고, 그 데이터들이 연속적이지 않게 메모리에 배치된다.
그래프(Graph): 그래프는 노드와 엣지로 이루어져 있으며, 노드들 간의 관계가 다양하게 연결된다. 노드들이 메모리 상에서 비연속적으로 저장되며, 포인터를 통해 서로 연결된다.
메모리 배치:
- 힙(Heap): 객체 인스턴스가
new키워드로 생성될 때 힙 메모리에 할당된다. 객체는 연속된 메모리 공간에 저장되지 않으며, 각 객체는 메모리 상에서 분리된 위치에 할당된다. 그 후, 객체들 간의 연결 관계를 포인터나 참조를 통해 관리한다.- 링크드 리스트(Linked List): 각 노드는 데이터와 함께 다음 노드를 가리키는 포인터를 가지고 있으며, 메모리 상에서 연속적이지 않게 저장된다. 예를 들어, 첫 번째 노드는 두 번째 노드를 가리키고, 두 번째 노드는 세 번째 노드를 가리키는 방식이다.
장점
- 유연한 크기 조정
- 링크드 리스트와 같은 비선형 구조는 동적으로 크기를 변경할 수 있어 데이터를 추가하거나 삭제하는 데 매우 유연하다.
- 효율적인 메모리 사용
- 비선형 구조는 필요할 때마다 노드를 동적으로 할당하므로 메모리 낭비가 적고, 데이터가 점점 추가될 때 유리하다.
- 복잡한 관계 표현
- 트리나 그래프와 같은 구조는 복잡한 데이터 간의 관계를 표현하는 데 강력하다. 예를 들어, 계층 구조나 관계망을 모델링할 때 유용하다.
단점
- 느린 접근 속도
- 데이터를 순차적으로 탐색해야 하므로, 인덱스를 통해 즉시 접근할 수 없는 경우가 많다. 예를 들어, 링크드 리스트에서는 데이터를 순차적으로 따라가야 하므로 접근 속도가 느리다.
- 메모리 관리 복잡성
- 메모리가 동적으로 할당되므로, 개발자가 메모리 관리에 신경을 써야 한다. 예를 들어, 링크드 리스트에서는 노드가 하나씩 연결되는데, 메모리 해제가 제대로 이루어지지 않으면 메모리 누수가 발생할 수 있다.
- 복잡한 구현
- 비선형 구조는 구현이 상대적으로 복잡하다. 트리나 그래프는 여러 연결을 다루어야 하기 때문에 배열에 비해 구현이 더 복잡하다.
3. 선형 메모리와 비선형 메모리의 차이점
특징 선형 메모리 (Linear Memory) 비선형 메모리 (Non-linear Memory) 데이터 배치 방식 데이터가 연속적으로 배치 데이터가 비연속적으로 배치 데이터 접근 방식 순차적 접근 (배열, 스택 등) 논리적 관계에 따라 접근 (링크드 리스트, 트리 등) 메모리 구조 배열, 스택, 큐 등 링크드 리스트, 트리, 그래프 등 성능 접근 속도가 빠르고 예측 가능 데이터 간의 관계를 따라가야 하므로 접근이 느림 메모리 관리 자동 관리 (스택은 함수 종료 시 자동 해제) 수동 관리 (힙 메모리에서 동적 할당 필요) 예시 배열, 스택, 큐, 버퍼 등 링크드 리스트, 트리, 그래프 등 결론
선형 메모리는 데이터가 연속적으로 저장되는 구조로, 배열이나 스택처럼 데이터가 순차적으로 쌓이거나 배열된 형태이다. 메모리 상에서 순차적으로 접근하는 데 효율적이다.
비선형 메모리는 데이터가 연속적이지 않고, 논리적으로 연결된 방식으로 저장되는 구조이다. 링크드 리스트, 트리, 그래프처럼 데이터 간의 관계를 포인터나 참조를 통해 연결하며, 데이터를 접근할 때 더 복잡한 방식으로 접근해야 한다.
따라서, 힙 메모리와 스택 메모리는 각각 선형과 비선형 메모리의 구조를 잘 보여주는 예시이다. 스택은 선형적인 구조이고, 힙은 비선형적인 방식으로 메모리를 할당하며 관리한다.
- 선형 메모리 구조는 빠르고 간단하지만, 데이터 크기가 고정적이거나 유연성이 부족할 수 있다.
- 비선형 메모리 구조는 복잡한 관계를 표현하고, 동적 메모리 할당이 가능하지만, 성능과 구현이 상대적으로 더 복잡하고 느릴 수 있다.
