- 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가 적용된다.
- 결과는 위 그림과 같다.
- 순서
- MyStack을 전달해 SomeStack으로 Shallow Copy를 한다.
- 이때 SomeStack의 top은 MyStack과 같은 위치의 값을 가리킨다.
- 이때 SomeStack.Pop(item)으로 인해 SomeStack은 Pop을 하고 6000의 주소값을 가리킨다.
- 하지만, 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;
}