컴퓨터 과학 총론, 휴먼싸이언스, 이광수 외 3명 공역 Chapter 08 데이터 추상화

리스트: 기본 데이터 구조로 순차적으로 배열되어 있는 항목들의 집합

헤드: 리스트의 시작, 테일: 리스트의 다른 쪽 끝

스택과 큐: 리스트의 항목들에 접근하는 방식을 제한함으로써 스택과 큐라는  특별한 유형의 리스트

스택: 헤드에서만 항목들을 제거(pop)하거나 삽입(push)할 수 있는 리스트이다. LIFO(last-in-first-out)구조

상단: 스택의 헤드, 하단: 스택의 테일

-> 순서와 반대의 순서로 꺼내야 할 항목들을 저장할 때 스택이 이상적이라는 것을 의미, 예로는 재귀법이 있다.

큐: 항목에 대한 제거는 헤드에서만 이루어지며, 새로운 항목의 추가는 테일에서만 이루어지는 리스트, FIFO(First-In, First-out)

트리: 계층적 구성을 갖는 항목들의 집합이다. (회사 조직도와 비슷)

노드: 트리상의 각 위치

루트 노드: 최상단의 노드 (사장 위치)

단말 로드(terminal node, leaf node): 루트의 반대쪽 끝에 있는 노드

트리의 깊이: 루트 노드에서 단말 노드에 이르는 최장 경로에 있는 노드의 개수

자식노드: 어떤 노드의 바로 아래의 자손노드

부모노드: 어떤 노드의 바로 위의 조상노드

형제 노드: 동일한 부모노드를 가지는 노드

2진 트리: 각 부모 노드가 둘 이하의 자식을 갖는 트리

서브 트리:  임의로 노드를 선택하면, 선택된 노드와 그 아래노드들이 트리 구조를 갖는데, 이러한 작은 트리를 말한다.

가지:  루트, 예로 부모노드에서 왼쪽 노드는 왼쪽 가지, 오른쪽 노드는 오른쪽 가지

리스트의 저장

이름 리스트를 컴퓨터의 주기억장치에 저장하기 위한 기법을 생각해보자

연속형 리스트: 전체 리스트를 연속된 주소를 갖는 메모리 셀 블록에 저장하는 것이다.

중요한 점은 전체 리스트가 하나의 큰 메모리블록에 저장되며, 연속된 항목들은 인접한 메모리 셀에 차례로 저장된다는 점이다.

연속형 리스트는 정적인 리스트를 구현하기 위한 편리한 저장구조이지만, 이름의 삭제나 삽입으로 인해 여러 항목들이 이동해야 하는 동적 리스트의 경우에는 불리하다.

연결리스트: 각 이름을 8글자 이내인 이름 리스트를 저장하는 문제를 생각해보자

처음 9개의 셀은 이름 자체를 저장하기 위해 사용되며, 마지막 셀은 리스트상의 다음 이름에 대한 포인터로 사용된다. 이러한 방식을 사용할 경우 리스트 항목들은 포인터로 연결된 여러 개의 작은 9-셀 블록들에 흩어져 있을 수 있다. 연결 방식을 사용한다는 점에서 이러한 구성을 연결리스트라고 부른다

(여기서 Pointer는 마지막 셀이 리스트상의 다음 이름에 대한 포인터역할을 한다) 

연결리스트의 시작 위치를 나타내기 위해 첫 번째 항목, 즉 , 리스트 헤드의 주소를 저장하는 별도의 포인터를 두는데 이를 헤드 포인터라고 부른다.

연결리스트의 끝을 표시하기 위해 null 포인터를 사용하는데, 이것은 리스트에 더 이상의 항목이 없다는 것을 표시하기 위함이다.

연속형 리스트에서의 삭제 항목 한 개 삭제 하면 빈자리를 만들게 되며, 따라서 삭제된 항목 뒤에 오는 항목들은 리스트의 연속성을 유지하기 위해 모두 앞쪽으로 이동해야한다

그러나 연결리스트에서 삭제는 한 개의 포인터만 변경하면 된다.

연결리스트에서 항목삽입은 조금 더 복잡하다. 새로운 항목과 포인터를 저장하기에 충분히 크고 사용되지 않는 메모리 셀 브록을 찾고, 여기에 새로운 항목을 저장하고 포인터는 리스트 상에서 새로운 항목 뒤에 올 항목의 주소로 채운다. 마지막으로 새로운 항복 바로 앞에 올 항목의 포인터를 새로운 항목을 가리키도로 변경한다. 

가장 큰 상태의 스택을 수용하기에 충분한 크기의 메모리 블록을 잡아둔다.

항목들을 하단에서 push하거나 pop하면, 스택 상단의 위치는 잡아둔 메모리 셀 블록 내에서 앞 뒤로 이동하게 된다. 이 위치를 나타내기 위해 그 주소가 스택 포인터라고 불리는 메모리 셀에 저장된다(위치는 상단, 움직이는 걸 확인해야하니까)

두 개의 메모리 셀을 포인터로 사용하기 위해 사용된다.

헤드 포인터: 큐의 헤드를 나타내기 위해 사용

테일 포인터: 큐의 테일을 나타내기 위해 사용

큐가 비어있는 상태에서는 동일한 위치를 가리킨다.

항목을 큐에 삽입할 때마다 테일 포인터가 가리키는 곳에 저장되며, 테일 포인터는 사용되지 않고 있던 다음 위치를 가리키기 위해 조정된다. (테일은 가리키기만 하는 것, cpu의 프로그램 카운터와 비슷해보인다.)

큐가 메모리에서 계속 이동한다. 그래서 큐가 정해진 메모리 블록을 벗어나지 않게 만들 메커닌즘이 필요하다

해결방법: 큐가 블록안에서 이동하도록 허용한다

헤드와 테일을 서로 연결하는 큐를 만든다. 이걸 순환형 큐라고 함.

연결 리스트와 유사한 연결 구조를 사용하여 메모리에 저장된다.

메모리 트리를 저장하기 위해서는 노드들을 저장하기 위한 메모리 셀 블록을 찾는일과 원하는 트리 구조에 따라 노드들을 연결하는 일이 필요하다.(해당 노드가 없을 경우 null)

루트포인터: 루트 노드의 주소를 저장하는 특별한 위치인 루트 포인터를 위한 장소를 잡는다. 트리에 처음 접근하기 위해 사용되는 것

전체 트리를 하나의 연속된 메모리 셀블록을 사용하여 저장하는 방법

이 방식은, 트리의 루트 노드를 블록의 첫 셀에 저장한다.

루트의 왼쪽 자식을 2번 셀

오른쪽 자실을 4번셀에 저장

상당히 비효율적인 저장

기계어에서의 포인터

스택에서 한 개의 항목을 pop하여 범용 레지스터 중 하나에 저장하기 위한 프로그램을 기계어로 작성하기를 원한다고 하자

우리가 사용하는 기계어에는 레지스터에 값을 넣는 명령이 두 개 있는데 하나는 명령 코드 1, 명령코드 2이다. '1'은 피연사자 필드에 '레지스터에 들어갈 데이터의 주소'를 포함하고 '2'는 피연산자 필드는 레지스터에 들어갈 데이터를 포함한다.

명령 코드 1은 프로그램이 실행되면서 스택 상단의 주소는 변화하므로 주소가 무엇인지 알 수 없고, 어떤 내용이 들어 있을지 알 수 없으므로 명령 코드 2를 사용 못 한다.

그러나 스택 포인터의 주소는 알고 있다.

즉, 레지스터에 넣을 데이터의 주소가 들어 있는 곳의 위치를 알고 있다.

그래서 확장하여 명령 코드 D를 포함

명령은 DRXY(주소 XY에 들어 있는 주소가 가리키는 메모리 셀의 내용을 R번레지스트에 넣으라는 의미이다) 

D5AA라는 명령은 주소가 AA인 메모리 셀에 스택 포인터가 들어 있다면, 스택 상단의 데이터가 5번 레지스터에 들어가도록 만들 것이다. 그러나 이 명령이 pop연산을 완성하지는 못한다. 추가로 필요한 것은 스택 포인터에서 1을 빼서 새로운 상단 위치를 가리키도록 하는 것이다. 이것은 우리의 기계어 프로그램은 새로운 load 명령을 수행한 뒤에, 스택  포인터를 레지스터로 옮긴 다음 1을 빼고 그 결과를 다시 메모리에 저장하게 될 것임을 의미한다.

....