DS-L06

• toc {:toc}

Sorted List using Doubly Linked List

• 이전 단방향 linked list 에서는 NodeType 에 next 만 적용되어 있는 반면 doubly linked list 는 back, next 2 가지가 적용되어 이전 포인터도 저장하는 구조를 갖는다.

FindItem

• InsertItem, DeleteItem, RetrieveItem 모두 특정 item 을 찾는 과정이 필요하기 때문에 FindItem 함수를 적용한다.(return location, found)
• FindItem precondition : 리스트는 비어있지 않는다.

template<class ItemType>
void FindItem(NodeType<ItemType>* listData, ItemType item,
	NodeType<ItemType>* &location, bool &found){
 
	bool moreToSearch = true;
	location = listData;
	found = false;
 
	while(moreToSearch && !found){
		if(item < location->info)
			moreToSearch = false;
		else if(item == location->info)
			found = true;
		else{
			// location = location->next   맨 끝에 둘 수 없기에 아래로 변경
			// moreToSearch = location!=NULL;
			if(location->next == NULL)
				moreToSearch = false;
			else
				location = location->next;
		}
	}
}

• 순회하며 item 보다 작다면 다음으로, 같다면 found flag 를 통해서 while 문 탈출
• 정렬되어 있는 상태이기 때문에 item 보다 순회하는 값이 더 크다면 item 에 맞는 값이 없는 것이므로 탐색할 필요가 없다.
• location, found 는 &로 받아 pass by reference 로 함수 안에서 지정되는 값을 그대로 받아올 수 있도록 한다.

InsertItem

template<class ItemType>
void InsertItem(ItemType item){
	NodeType<ItemType>* newNode;
	NodeType<ItemType>* location;
    bool = found;
 
    newNode = new NodeType<ItemType>;
    newNode->info = item;
    if(listData != NULL){   // list가 차 있는 경우
        FindItem(listData, item, location, found);
        if(location->info > item){  // item이 중간에 위치한 경우
            newNode->back = location->back;
            newNode->next = location;
            if(location != listData){       
                location->back->next = newNode;
            }
            location->back = newNode;
        }
        else{       // item이 end에 위치한 경우
            newNode->back = location;
            location->next = newNode;
            newNode->next = NULL;
        }
    }
    else{           // list가 빈 경우
        listData = newNode;
        newNode->next = NULL;
        newNode->back = NULL;
    }
    length++;
}

• 이전, 다음 노드를 가리키는 포인터를 변경할 때 보유한 값이 사라지지 않도록 순서에 유의해야 한다.
  • newNode→back = location→back 우선
  • location→back = newNode 다음

Headers and Trailers

• 시작, 끝 지점에서 예외가 발생하기 때문에 Header 와 Trailer 를 사용해서 예외를 배제하는 방식을 사용하기도 한다.
• Idea : 리스트의 양 끝 단에 절대 삽입, 삭제를 하지 않도록 만든다.
• Method : 양 끝 단에 가능한 값의 범위를 초과한 dummy 노드를 만든다.
• Header : 가능한 리스트 값보다 더 작은 값을 포함한다.
• Trailer : 가능한 리스트 값보다 더 큰 값을 포함한다.

Shallow Copy / Deep Copy

• Shallow Copy : 클래스 멤버 데이터만 복사하고, 가리키고 있는 데이터는 복사하지 않는다. 즉, 가리키고 있는 데이터는 본래 클래스 객체와 공유한다.
• Deep Copy : 클래스 멤버 데이터 뿐만 아니라 가리키고 있는 데이터도 따로 저장한다. 본래 클래스 객체의 데이터의 위치와 다른 곳에 데이터를 저장하고 가리킨다.

Shallow Copy

• 다음의 경우 어떻게 될까?

void Func(StackType<ItemType> SomeStack){
	ItemType item;
	SomeStack.Pop(item);
}
 
// main
StackType<int> MyStack;
Func(MyStack);

• Func 의 파라미터로 전달된 스택은 pass by value 로 전달됐다.
• 다음의 경우에는 Shallow Copy 가 적용된다.

• 결과는 위 그림과 같다.
• 순서

1. MyStack 을 전달해 SomeStack 으로 Shallow Copy 를 한다.
2. 이때 SomeStack 의 top 은 MyStack 과 같은 위치의 값을 가리킨다.
3. 이때 SomeStack.Pop(item) 으로 인해 SomeStack 은 Pop 을 하고 6000 의 주소값을 가리킨다.
4. 하지만, MyStack 의 경우 여전히 7000 주소값을 가리키고 있게 된다.

Deep Copy

• 기본 생성자를 사용할 경우 pass by value 로 생성된다.
• 포인터가 동적 데이터를 가리킬 때 pass by value 즉, Shallow Copy 의 경우 포인터가 가리키는 값을 복사하지 못하므로 위와 같은 문제가 발생한다.
• 다른 메모리 공간에서 동적 데이터의 Deep Copy 를 만드는 copy constructor 를 클래스에 만들어 사용해야 한다.
• Copy constructor
  • Pass by reference 를 사용한다.
  • Copy constructor 를 만들어 둔 경우, pass by value 로 복사를 하더라도 암묵적으로 copy constructor 가 호출되어 복사된다.

template<class ItemType>
class StackType{
public:
	StackType(){
		cout << "Default Constructor" << endl;
	};
	StackType(const StackType<ItemType>& anotherStack);
	// Copy constructor
	{
		cout << "Copy Constructor" << endl;
		.
		.
		.
	}
	~StackType();
private:
	NodeType<ItemType>* topPtr;
}
 
int main(){
	StackType<int> SomeStack;
	SomeStack.Push(1);
	StackType<int> AnotherStack(SomeStack);
}
 
// Result
// Default Constructor
// Copy Constructor

• 왜 파라미터를 const 로 지정할까?
• const 로 파라미터를 지정하면 해당 파라미터는 변형을 가할 수 없다.
• 하지만 copy constructor 의 경우 값을 변화시키지 않고 복사를 하는 역할을 하기 때문에 const 로 명확하게 명시한다.
• Copy constructor 는 다음의 3 가지 상황에서 암묵적으로 호출되는 특수한 멤버 함수이다.
  • 객체 파라미터를 value 로 전달하는 경우
  • 선언에서 객체 변수를 초기화하는 경우
  • 함수의 반환값으로 객체를 반환하는 경우

Assignment Operator =

• 만약, 클래스가 동적 데이터를 가리키는 데이터 멤버 포인터를 가지고 있다면 동적 데이터의 Deep Copy 를 만드는 할당 연산자를 작성해야 한다.

template<class ItemType>
class StackType{
public:
	StackType();
	StackType(const StackType<ItemType>& anotherStack);
	// Copy constructor
	void operator= (const StackType<itemType>& originalStack);
	~StackType();
private:
	NodeType<ItemType>* topPtr;
}