컴퓨터 메모리 상의 리스트

위의 자료구조를 컴퓨터의 메모리에 어떤 식으로 존재하는 지에 대해 생각한다.
모든 자료 및 자료구조는 메모리 공간 상의 특정 주소에 위치하며 존재한다.
그리고 메모리는 0 부터 n 까지의 크기를 가진다는 사실을 염두에 둔다.

메모리 상의 배열과 연결리스트

• 배열은 순서를 가진, 고정된 배치를 가지고 있으며 각 요소는 index와 value를 가진다. 배열은 내용의 요소가 서로 딱 붙은 채로 존재하기 때문에, 하나의 배열은 고정적으로 연결된 덩어리 형태로 메모리 공간을 차지한다. 따라서, 하나의 배열 내 배열 요소의 메모리 주소 값 또한 순서가 있는 연속적인 주소를 갖는다.

• 연결 리스트는 배열과 달리 유기적인 형태를 띄고 있으며, 포인터를 통한 유기적인 연결관계를 가진다. 따라서 연결 리스트의 노드의 주소 값은 서로 떨어져 있을 수 있으나, 포인터를 가지고 있어 특정 노드의 앞 뒤 포인터를 통해 포인터가 기억하는 앞 뒤 노드의 주소로 접근할 수 있다. 연결 리스트에서 가장 기억해야 할 것은, 첫번째 노드 값과 마지막 노드 값이다.

컴퓨터 사용자는 프로그램을 실행할 때에 Memory Allocator(메모리 할당 관리자)에게 start(메모리 공간 사용 시작 지점)와 + offset(얼만큼까지 쓸 것인가)의 형태로 사용 공간을 요청한다. 예를 들어 사용자는 컴퓨터로 어떠한 작업을 할 때에, MA에게 "얼마만큼의 메모리 공간을 줘"하고 요청하는 것이다. 그렇게 하면 MA는 사용자의 작업에 필요한 메모리 공간을 딱 start+offset 만큼 할당해준다.

배열의 연산이 어떻게 일어나는가?

배열의 주요 연산은 아래와 같다.

• 조회
• 삽입
• 삭제

조회 연산의 경우: 배열의 요소가 index가 메모리 상의 주소값을 가리키기 때문에 요소 간의 관계와 상관없이 주소값으로 바로 원하는 요소에 접근할 수있다.

삽입 연산의 경우: 배열의 요소는 맨 앞, 맨 뒤, 혹은 요소 사이에 삽입될 수 있다.
맨 뒤에서 요소가 삽입되는 경우, 새로운 요소의 추가 이외 일어나는 작업이 없기 때문에, 연산 작업은 최선의 상수 시간복잡도를 가진다. 그러나 최악의 경우인, 배열의 맨 앞에서 새로운 요소가 삽입되면, 원래 있던 기존의 요소들이 모두 배열의 한 칸씩 뒤로 밀려나기 때문에 배열의 길이 n만큼의 작업이 생겨 최악의 O(n) 시간 복잡도를 가진다.

삭제 연산의 경우: 맨 뒤 요소가 삭제될 경우 요소 하나만 삭제가 일어나 최선의 상수 시간복잡도이지만, 맨 앞 요소를 삭제할 경우, 배열은 아무것도 없는 빈 공간을 허용하지 않기 때문에 O(n) 시간 복잡도를 가진다.

연결 리스트의 연산이 어떻게 일어나는가?

연결 리스트의 주요 연산 또한 아래와 같다.

• 조회
• 삽입
• 삭제

조회 연산의 경우: 연결 리스트에서 각 노드는 포인터를 통한 연결 관계를 가지며, 앞 뒤 포인터로 메모리 주소에 접근하는 방법으로만 원하는 값을 찾아다니며 조회할 수 있다.

삽입 연산의 경우: 연결 리스트의 삽입 연산에서는 원하는 자리에 새로 추가하는 노드를 넣기 전, 기존에 그 위치를 차지하던 노드의 포인터 연결 관계를 해제한 후 새로운 노드의 주소값을 가리키고, 기존 노드의 뒤에 위치한 노드의 주소를 새로운 노드의 포인터로 가리켜 새로운 연결 관계를 만들면 요소의 삽입이 이루어진다.

삭제 연산의 경우: 삽입과 반대로 생각하면 된다. 삭제할 노드의 앞 뒤 포인터 연결관계를 해제하고, 삭제한 노드 이전 노드의 포인터가 삭제한 노드 뒤에 위치했던 노드의 주소값을 가리키게 한 후 요소를 삭제하면 삭제 연산이 이루어진다.

주의: 위의 내용만 생각하면 될까?

꼭 그렇지 만은 않다.

요소 특히 요소 삭제에 있어서는 다양한 방법론이 존재하기 때문이다. 특정 요소를 지운 효과를 주고 싶다면, (기존의 배열에서 0과 -1이라는 값을 사용하지 않는다면, 해당 인덱스에 0이나 -1으로 값을 교체하고 0 값이나 -1 값을 무시하면 삭제와 같은 효과를 볼 수 있다.

또는, 만일 4억~-4억 까지의 가능한 모든 Integer 값이 배열의 값에 들어갈 수 있는 조건이라면, 삭제처리를 하고 싶은 요소를 삭제할 값을 또 다른 삭제데이터용 배열에 저장하여, 그 배열에 든 값을 무시하는 방법을 사용할 수도 있다.

따라서 위와 같은 접근으로 삭제 연산을 구현한다면, 삭제 연산과 같은 효과를 보면서도 배열 내에서 기존요소를 n만큼 재배치하는 현상을 피할 수 있다.

메모리 상에서 스택

스택을 구현하는 대표적인 방법은 배열 자료 구조를 이용하는 것이다.
스택은 선입후출 형태의 자료구조이며, 요소를 삽입 삭제하는 특징을 가지고 있다. 컴퓨터 메모리 상에서 스택을 배열로 구현할 경우, 삽입 그리고 삭제 연산을 알아보자.

삽입

스택 자료구조를 메모리 상에 만들기 위해 먼저 Memory Allocator에게 메모리 공간을 start + offset의 형식으로 요청하면 스택 공간이 생긴다. 삽입을 하던 중 스택의 Memory Allocator가 할당해준 메모리 공간이 가득찬다면, 스택은 새로운 요소를 추가하기 위한 새로운 공간을 필요로 하게 된다.

아파트에 스택 자료구조 공간을 비유하자면, 우리는 아파트의 공간이 꽉 찼을 때, 필요한 공간을 허공에다 만들 수 없다. 공간이 더 필요하다면 우리는 더 큰 아파트로 이사를 간다. 이처럼 메모리 공간에 더 큰 스택의 공간이 필요하다면, 기존에 할당된 스택의 메모리 공간의 제곱만큼 큰 임의의 메모리 공간에 새로운 스택을 만들고, 기존 스택의 값을 복사하여 넣는 방법이 효율적인 방법의 한 가지 일 것이다. 이러한 식으로 스택의 요소 삽입이 진행된다.

삭제

그렇다면 삭제는 어떻게 하면 효율적일까? 요소의 삭제는 삽입의 반대라고 생각할 수 있다. 후입선출(LIFO)의 구조를 하고 있는 스택에서의 삭제 연산이 일어나면 나중에 삽입된 요소부터 공간에서 비워지면 필요없는 메모리 공간도 작아져야 한다. 그렇다고 삽입 때와 같이 원래 길이의 제곱만큼 메모리 공간이 줄어든다면, 요소 삭제 후 요소의 삽입이 일어났을 때 요소가 들어갈 공간이 없는 문제가 생긴다. 이를 방지하기 위해 삭제 연산 시에는 스택 크기의 1/3 혹은 1/4 만큼 메모리 공간이 뒤쪽부터 축소시키는 것이 효율적인 방법이다.