[Lecture] Chapter 05. Linked List

HEEJOON MOON·2021년 9월 15일

Linked List

Dynamic allocation이 가능하다는 장점이 있다

NodeType


template < class ItemType > 
struct NodeType {
	ItemType info;
	NodeType* next;
};

Linked List를 이용한 StackType!


template 
class LLStackType {
public:
	LLStackType();
	~LLStackType();
	bool IsFull();
	bool IsEmpty();
	void Push(ItemType);
	void Pop();
	ItemType Top();
private:
	NodeType* topPtr;
};


template 
LLStackType::LLStackType() {
	topPtr = nullptr;
}

Destructor

topPtr이 nullptr이 될 때까지, tempPtr로 지울 Node를 가리키고 지우면서 topPtr = topPtr->next를 가리킨다. (끝까지 가면서 지운다)
```
	
template 
LLStackType::~LLStackType() {
	NodeType tempPtr;
	while (topPtr!=nullptr) {
		tempPtr = topPtr;
		topPtr = topPtr->next;
		delete tempPtr;
	}
}
```

IsFull

새로운 Node를 만드는 것을 try 해보고 exceptrion이 발생하면 FullStack인 것을 알 수 있다


template 
bool LLStackType::IsFull() {
	NodeType* location;
	try {
		location = new NodeType;
		delete location;
		return false;
	}
	catch (FullStack) {
		return true;
	}
}

IsEmpty

새로운 Node를 만드는 것을 try 해보고 exceptrion이 발생하면 FullStack인 것을 알 수 있다
```
template 
bool LLStackType::IsEmpty() {
	return	(topPtr == nullptr);
}
```

Top

topPtr이 가리키는 node의 info를 return 한다



template 

ItemType LLStackType::Top() {

if (IsEmpty()) {

throw EmptyStack();

}

else {

return topPtr->info;

}

}

Push

tempPtr로 새로운 Node를 가리키고, 새 노드의 next를 topPtr->next(삽입 후 오른쪽 element)를 가리킨다

이후, 기존의 topPtr로 새로운 노드를 가리킨다



template 

void LLStackType::Push(ItemType item) {

NodeType* temp;

temp = new NodeType;

temp->info = item;

temp->next = topPtr;

topPtr = temp;

}

Pop

tempPtr로 topPtr이 가리키는 노드를 가리키고, topPtr = topPtr->next (다음 순서의 지울 원소를 가리킨다)

이후, 기존의 노드였던 tempPtr를 delete



template 

void LLStackType::Pop() {

if (IsEmpty())

throw EmptyStack();
NodeType<ItemType>* temp;
temp = topPtr;
topPtr = topPtr->next;
delete temp;
}

Linked List를 이용한 QueueType!


template 
class LLQueueType {
public:
	LLQueueType();
	~LLQueueType();
	bool IsFull() const;
	bool IsEmpty() const;
	void Enqueue(ItemType);
	void Dequeue(ItemType& item);
	void makeEmpty();

private:
	NodeType* front;
	NodeType* rear;
};

// Constructor!
template< class ItemType >
LLQueueType::LLQueueType() {
	front = nullptr;
	rear = nullptr;
}

Destructor

front != rear일 때까지, tempPtr로 지울 Node(front가 가리킨 노드)를 point한다
front = front -> next (다음 원소로 front이동)

기존 노드(tempPtr) 삭제


template< class ItemType >
LLQueueType::~LLQueueType() {
	while (!IsEmpty()) {
		NodeType* tempPtr;
		tempPtr = front;
		front = front->next;
		delete tempPtr;
	}
}

IsFull, IsEmpty

IsFull의 경우 stack과 동일

IsEmpty의 경우 front == rear이면 empty로 판단 가능하다



template< class ItemType >

bool LLQueueType::IsFull() const {

try {

NodeType* temp;

temp = new NodeType;

delete temp;

}

catch (FullQueue);

}

template< class ItemType >

bool LLQueueType::IsEmpty() const {

return (front == rear);}

Enqueue

1) tempPtr로 새로운 노드(next는 nullptr)를 가리키고, 기존의 rear의 next에 새로운 노드를 연결시킨다
2) 이후 rear = tempPtr(Newnode)을 통해 rear의 위치를 1증가시킨다!


template< class ItemType >
void LLQueueType::Enqueue(ItemType item){
	if (IsFull) { throw FullQueue(); }
	else {
		NodeType temp;
		temp = new NodeType;
		temp->info = item;
		temp->next = nullptr;
		if (rear == nullptr)
			front = temp; // front가 nullptr이다가 처음 Node를 가리키는 경우!
		else
			rear->next = temp; // (if rear-> next == nullptr인 경우, 위의 예외처리)
		rear = temp;
	}
}

Dequeue

1) tempPtr로 지울 노드(front가 가리키는 노드)를 먼저 가리킨다
2) front = front->next를 통해 front의 위치를 1증가시킨다
3) 기존의 노드(tempPtr)을 delete한다


template
void LLQueueType::Dequeue(ItemType& item) {
	if (IsEmpty) { throw EmptyQueue(); }
	else {
		NodeType* temp;
		temp = front;
		front = front->next;
		item = temp->info;
		if (front == nullptr) // 위의 action이후 front가 nullptr, front->next가 오류가 발생하므로 rear역시 null로 만들어주어 Isempty()조건에 걸리게 한다
			rear = nullptr; 
		delete temp;
	}
}

makeEmpty

Destructor처럼 front가 계속 rear쪽으로 이동하면서 기존 노드를 delete해야 한다

마지막 노드를 지우는 경우 front와 rear를 nullptr로 지정해준다


template< class ItemType >
void LLQueueType::makeEmpty() {
	while (!IsEmpty()) {
		NodeType* tempPtr;
		tempPtr = front;
		front = front->next;
		delete tempPtr;
	}
	rear = nullptr;
}

circular queue design

rear->next가 nullptr이 아닌 front를 가리키면 된다

Linked List를 이용한 UnsortedType!


template 
class UnsortedType {
public:
	UnsortedType();
	~UnsortedType();
	void makeEmpty();
	bool IsFull() const;
	int LengthIs() const;
	void RetrieveItem(ItemType& item, bool& found);
	void InsertItem(ItemType);
	void DeleteItem(ItemType& item);
	void ResetList();
	void GetNextItem(ItemType& item);
private:
	NodeType* listData;
	int length;
	NodeType* currentPos;
};

template 
UnsortedType::UnsortedType() {
	length = 0;
	listData = nullptr;
}

template 
int UnsortedType::LengthIs() const {
	return length;}

RetrireveItem(item, bool& found)

item이 list에 있으면 found가 true가 된다


template < class ItemType >
void UnsortedType::RetrieveItem(ItemType& item, bool& found) {
	bool moreToSearch;
	NodeType* location;
	location = listData; // listData의 첫번째 element를 가리킨다
	found = false;
	moreToSearch = (location != nullptr); // location이 끝까지 안갔을때까지 실행
	while (moreToSearch && !found) {
		if (item == location->info) {
			found = true;
			item = location->info;
		}
		else {
			location = location->next; // location ++
			moreToSearch = (location != nullptr);
		}
	}
}

InsertItem


template < class ItemType >
void UnsortedType::InsertItem(ItemType item) {
	NodeType* location;
	location = new NodeType;
	location->info = item;
	location->next = listData;
	listData = location;
	length++;
}

DeleteItem

-삭제할 node기준으로 좌우의 노드를 연결시켜줘야 한다->삭제할 노드를 가리키는 tempLoc, 삭제할 노드 이전을 가리키는 Loc을 알아야 한다
-Loc->next = tempLoc->next 한 이후에 노드를 삭제한다(순서 중요!)


template < class ItemType >
void UnsortedType::DeleteItem(ItemType& item) {
	NodeType* location = listData;
	NodeType* tempLoc;
	bool found = false;
	if (item == listData->info) {
		tempLoc = location;
		listData = listData->next; // Delete first node
	}

	else {
		while (!(item == (location->next)->info))
			location = location->next;

		RetrieveItem(item, found); // item이 있는지 확인한다!
		if (found) {
			// delete node at location->next
			tempLoc = location->next;
			location->next = (location->next)->next; // 삭제될 원소의 오른쪽 원소를 point!
			delete tempLoc;
			length--;
		}
		else {
			// item is not in list!
		}
	}
}

Linked List를 이용한 SortedType


template < class ItemType >
void SortedType< ItemType >::RetrieveItem(ItemType& item, bool& found){

NodeType< ItemType >* location; 
location = listData;
found = false;

while(location != nullptr && !found) {
	if(location->info != item){
	 	location = location->next;
		}
	else if(location->info == item){
		found = true;
		item = location -> info;
	 	}
	else{location = nullptr)
	}
}