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;
}