CH 05 Linked Structure

Node

A single Node

• .info: 실제 사용자의 데이터
• .next: 다음 노드를 가리키는 포인터
• node: 데이터 구조 중 한 요소
• 특정 노드 관점에서 보면 자신의 뒷 요소밖에 모름
• 사용자가 변수를 선언하는 시점에도 몇 개가 필요한지 모를 때 사용
• 새 요소를 만들 때마다 heap 공간에 new Operation 이용해 메모리 동적 할당
• delete 반드시 필요: 그렇지 않으면 Garbage로 남게 됨

Detructor

• 노드를 요소로 갖는 Local Variable의 topPtr에는 첫 노드의 주소 저장
• 함수가 종료되면 Local Variable 삭제
• 삭제된 Local Variable의 topPtr이 가리키던 노드들은 Garbage
• Local Variable 삭제 전에 노드 메모리 해제 필요

Unsorted List

Application Level

• Application Level에선 기존 Unsorted List와 변함없이 동일
• Operation을 가지지 않는 Node를 struct로 구현
• List의 앞을 나타내는 Pointer, 현재 위치 나타내는 Pointer 필요

InsertItem Method

• NodeType<ItemType>* location
  
• location = new NodeType<ItemType>
  
• location->info = item
  
• location->next = listData
  
• listData = location
  

DeleteItem Method

• 각 노드의 입장에서 보면 자신의 다음 노드에 대한 정보만 가지고 있음
• NodeType<ItemType>* location = listData
  
• NodeType<ItemType>* tempLocation
  
• if (location->info == item) // 처음에 item이 있을 때
  
  • tempLocation = location
    
  • listData = location->next
    
• else // item이 중간에 있을 경우
  • while( (location->next)->info != item) // 자신의 뒷 노드밖에 몰라서
    
    location->next = (location->next)->next
  • tempLocation = location->next // 찾은 경우
    
  • location->next = (location->next)->next
    
• delete tempLocation
  
• length--

UnsortedLinked.h

#include <cstddef>
#include <new>

template <class ItemType>
struct NodeType;

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

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

template<class ItemType>
UnsortedType<ItemType>::UnsortedType() {
	length = 0;
	listData = NULL;
}

template<class ItemType>
UnsortedType<ItemType>::~UnsortedType() {
	MakeEmpty();
}

template<class ItemType>
void UnsortedType<ItemType>::MakeEmpty() {
	NodeType<ItemType>* tempPtr;

	while (listData != NULL) {
		tempPtr = listData;
		listData = listData->next;
		delete tempPtr;
	}
	length = 0;
}

template<class ItemType>
bool UnsortedType<ItemType>::IsFull() {
	NodeType<ItemType>* location;
	try {
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch (std::bad_alloc exception) {
		return true;
	}
}

template<class ItemType>
int UnsortedType<ItemType>::LengthIs() {
	return length;
}

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

template<class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item) {
	NodeType<ItemType>* location;
	NodeType<ItemType>* tempLocation;
	location = listData;
	if (location->info == item) { // 처음에 item 존재
		tempLocation = location;
		listData = location->next;
	}
	else {// 중간에 item 존재
		while ((location->next)->info != item)
			location = location->next;
		tempLocation = location->next;
		location->next = (location->next)->next;
	}
	delete tempLocation;
	length--;
}

template<class ItemType>
void UnsortedType<ItemType>::ResetList() {
	currentPos = NULL;
}

template<class ItemType>
void UnsortedType<ItemType>::GetNextItem(ItemType& item) {
	if (currentPos == NULL) {
		currentPos = listData;
	}
	else {
		currentPos = currentPos->next;
	}
	item = currentPos->info;
}

template<class ItemType>
void UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool& found) {
	NodeType<ItemType>* location = listData;
	bool moreToSearch = (location != NULL);
	found = false;
	while (moreToSearch && !found) {
		if (location->info == item) {
			found = true;
			item = location->info;
		}
		else {
			location = location->next;
			moreToSearch = (location != NULL);
		}
	}
}

Big-O Comparision

Operation	Array Implementaion	Linked-list Implementation
Constructor	O(1)	O(1)
MakeEmpty	O(1)	O(N)
InsertItem	O(1)	O(1)
DeleteItem	O(N)	O(N)
IsFull	O(1)	O(1)
LengthIs	O(1)	O(1)
RetrieveItem	O(N)	O(N)
ResetList	O(1)	O(1)
GetNextItem	O(1)	O(1)
Destructor	O(1)	O(N)

Sorted List

Application Level

• Application Level에선 기존 Sorted List와 변함없이 동일
• Operation을 가지지 않는 Node를 struct로 구현
• List의 앞을 나타내는 Pointer, 현재 위치 나타내는 Pointer 필요

RetrieveItem Method

• Linked-list에서는 중간을 알 수 없음
  • Linked-list는 index를 가지지 않음
  • 한 노드의 관점에서 보면 자신의 다음 노드밖에 알 수 없음
• Binary Search 불가능
• length를 이용해 구현할 수 있지만 비효율적

InsertItem Method

• location Pointer 하나만 사용하는 경우
  • 각 노드는 자신의 다음 노드만 알고 있음
  • 새로운 item을 추가하면 item 전에 오는 노드의 next가 item을 가리킬 수 있도록 해야 함
  • 따라서 location이 아닌 (location->next)->info로 검색
  • 만약 item이 마지막에 들어가는 경우 참조 오류 발생
    
  • location->next 는 NULL 값이라 item 추가 불가능
  • item이 들어가기 바로 전 위치를 가리키는 preLoc Pointer 추가
• NodeType<ItemType>* newNode
  NodeType<ItemType>* location
  NodeType<ItemType>* preLoc
  bool moreToSearch
  
• location = listData
  preLoc = NULL
  moreToSearch = (location != NULL)
  
• while (moreToSearch)
  • if (location->info < item) // 못 찾았을 때
    preLoc = location
    
    location = location->next
    moreToSearch = (location != NULL)
    
  • newNode = new NodeType<ItemType>
    
  • newNode->info = item
    
  • if (preLoc == NULL) // item이 첫 순서라면
    newNode = listData
    
    listData = newNode
    
  • else // item이 중간 위치라면
    newNode->next = location
    
    preLoc->next = newNode
    
  • legnth++

SortedLinkde.h

#include <cstddef>
#include <new>
#include "ItemType.h"
#define MAX_ITEMS 100

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

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

template<class ItemType>
SortedType<ItemType>::SortedType() {
	length = 0;
	listData = NULL;
}

template<class ItemType>
SortedType<ItemType>::~SortedType() {
	MakeEmpty();
}

template<class ItemType>
void SortedType<ItemType>::MakeEmpty() {
	NodeType<ItemType>* tempPtr;
	while (listData != NULL) {
		tempPtr = listData;
		listData = listData->next;
		delete tempPtr;
	}
	length = 0;
}

template<class ItemType>
bool SortedType<ItemType>::IsFull() {
	NodeType<ItemType>* location;
	try {
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch (std::bad_alloc exception) {
		return true;
	}
}

template<class ItemType>
int SortedType<ItemType>::LengthIs() {
	return length;
}

template<class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item) {
	NodeType<ItemType>* location;
	NodeType<ItemType>* preLoc;
	NodeType<ItemType>* newNode;
	location = listData;
	preLoc = NULL;
	bool moreToSearch = (location != NULL);
	while (mroeToSearch) {
		if (location->info < item) {
			preLoc = location;
			location = location->next;
			moreToSearch = (location != NULL);
		}
		else
			moreToSearch = false;
	}
	newNode = new NodeType<ItemType>;
	newNode->info = item;
	if (preLoc == NULL) {
		newNode->next = location;
		listData = newNode;
	}
	else {
		newNode->next = location;
		preLoc->next = newNode;
	}
	length++;
}

template<class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item) {
	NodeType<ItemType>* location;
	NodeType<ItemType>* tempLocation;
	location = listData;
	if (location->info == item) { // 처음에 item 존재
		tempLocaton = location;
		listData = location->nextl
	}
	else {// 중간에 item 존재
		while ((location->next)->infp != item)
			locaiton = location->next;
		tempLocation = location->next;
		location->next = (location->next)->next;
	}
	delete tempLocation;
	length--;
}

template<class ItemType>
void SortedType<ItemType>::ResetList() {
	currentPos = NULL;
}

template<class ItemType>
void SortedType<ItemType>::GetNextItem(ItemType& item) {
	if (currentPos == NULL) {
		currentPos = listData;
	}
	else {
		currentPos = currentPos->next;
	}
	item = currentPos->info;
}

template<class ItemType>
void SortedType<ItemType>::RetrieveItem(ItemType& item, bool& found) {
	NodeType<ItemType>* location = listData;
	bool moreToSearch = (location != NULL);
	found = false;
	while (moreToSearch && !found) {
		if (location->info == item) {
			found = true;
			item = location->info;
		}
		else {
			location = location->next;
			moreToSearch = (location != NULL);
		}
	}
}

Big-O Comparison

Operation	Array Implementaion	Linked-list Implementation
Constructor	O(1)	O(1)
MakeEmpty	O(1)	O(N)
InsertItem	O(1)	O(1)
DeleteItem	O(N)	O(N)
IsFull	O(1)	O(1)
LengthIs	O(1)	O(1)
RetrieveItem	O(N)	O(N)
ResetList	O(1)	O(1)
GetNextItem	O(1)	O(1)
Destructor	O(1)	O(N)

Stack

Application Level

• Application Level에선 기존 stack과 변함없이 동일
• Operation을 가지지 않는 Node를 struct로 구현
• Top 노드 가리키는 private 변수 추가

Push Method

• NodeType<char>* location
  
• location = new NodeType<char>
  
• location->info = newItem
  
• location->next = topPtr
  
• topPtr = location
  

Pop Method

• NodeType<char>* tempPtr
  
• item = topPtr->info
  
• tempPtr = topPtr
  
• topPtr = topPtr->next
  
• delete tempPtr
  

StackType.h

#include <cstddef>
#include <new>

template <class ItemType>
struct NodeType;

class FullStack {
};

class EmptyStack {
};

template <class ItemType>
class StackType {
public:
	StackType();
	~StackType();
	bool IsFull() const;
	bool IsEmpty() const;
	void Push(ItemType item);
	void Pop();
	ItemType Top();
private:
	NodeType<ItemType>* topPtr;
};

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

template <class ItemType>
StackType<ItemType>::StackType() {
	topPtr = NULL;
}

template <class ItemType>
StackType<ItemType>::~StackType() {
	NodeType<ItemType>* tempPtr;
	while (topPtr != NULL) {
		tempPtr = topPtr;
		topPtr = topPtr->next;
		delete tempPtr;
	}
}

template <class ItemType>
bool StackType<ItemType>::IsFull() const {
	NodeType<ItemType>* location;
	try {
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch (std::bad_alloc exception) {
		return true;
	}
}

template <class ItemType>
bool StackType<ItemType>::IsEmpty() const {
	return (topPtr == NULL);
}

template <class ItemType>
ItemType StackType<ItemType>::Top() {
	if (topPtr == NULL)
		throw EmptyStack();
	else
		return topPtr->info;
}

template <class ItemType>
void StackType<ItemType>::Push(ItemType item) {
	if (IsFull())
		throw FullStack();
	else {
		NodeType<ItemType>* location;
		location = new NodeType<ItemType>;
		location->info = item;
		location->next = topPtr;
		topPtr = location;
	}
}

template <class ItemType>
void StackType<ItemType>::Pop() {
	if (IsEmpty())
		throw EmptyStack();
	else {
		NodeType<ItemType>* tempPtr;
		tempPtr = topPtr;
		topPtr = topPtr->next;
		delete tempPtr;
	}
}

Big-O Comparison

Operation	Array Implementaion	Linked-list Implementation
Constructor	O(1)	O(1)
MakeEmpty	O(1)	O(N)
Push	O(1)	O(1)
Pop	O(1)	O(1)
IsFull	O(1)	O(1)
IsEmpty	O(1)	O(1)
Top	O(1)	O(1)
Destructor	O(1)	O(N)

Queue

Application Level

• Application Level에선 기존 Queue와 변함없이 동일
• Operation을 가지지 않는 Node를 struct로 구현
• front와 rear 가리키는 Pointer 두 개 필요

Enqueue Method

• NodeType<ItemType>* ptr;
  
• ptr = new NodeType<ItemType>
  
• ptr->info = newItem
  
• ptr->next = NULL
  
• if (rear == NULL) // 처음 넣을 때
  • front = ptr
    
• else
  • rear->next = ptr
    
• rear = ptr
  

Dequeue Method

• NodeType<ItemType>* tempPtr
  
• tempPtr = front
  
• item = front->info
  
• front = front->next
  
• if (front == NULL) // 아이템이 하나 남았을 때
  • rear = NULL
    
• delete tempPtr
  

QueType.h

#include <cstddef>
#include <new>

#include <cstddef>
#include <new>

template <class ItemType>
struct NodeType;

class FullQueue {
};

class EmptyQueue {
};

template<class ItemType>
class QueueType {
public:
	QueueType();
	~QueueType();
	void MakeEmpty();
	bool IsFull() const;
	bool IsEmpty() const;
	void Enqueue(ItemType newItem);
	void Dequeue(ItemType& item);
private:
	NodeType<ItemType>* front;
	NodeType<ItemType>* rear;
};

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

template<class ItemType>
QueueType<ItemType>::QueueType() {
	front = NULL;
	rear = NULL;
}

template<class ItemType>
QueueType<ItemType>::~QueueType() {
	MakeEmpty();
}

template<class ItemType>
void QueueType<ItemType>::MakeEmpty() {
	NodeType<ItemType>* tempPtr;
	while (front != NULL) {
		tempPtr = front;
		front = front->next;
		delete tempPtr;
	}
	rear = NULL;
}

template<class ItemType>
bool QueueType<ItemType>::IsEmpty() const {
	return (front == NULL);
}

template<class ItemType>
bool QueueType<ItemType>::IsFull() const {
	NodeType<ItemType>* location;
	try {
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch (std::bad_alloc exception) {
		return true;
	}
}

template<class ItemType>
void QueueType<ItemType>::Enqueue(ItemType newItem) {
	if (IsFull())
		throw FullQueue();
	else {
		NodeType<ItemType>* location;
		location = new NodeType<ItemType>;
		location->info = newItem;
		if (rear == NULL)
			front = location;
		else
			rear->next = location;
		rear = location;
	}
}

template<class ItemType>
void QueueType<ItemType>::Dequeue(ItemType& item) {
	if (IsEmpty())
		throw EmptyQueue();
	else {
		NodeType<ItemType>* tempPtr;
		tempPtr = front;
		item = front->info;
		front = front->next;
		if (front == NULL)
			rear = NULL;
		delete tempPtr;
	}
}

Memory Comparison

• Array-based Implimentation
  • item 하나가 80bytes라고 가정하면 100개의 item으로 이루어진 배열은 8000bytes
  • Reserved cell 80 bytes
  • front와 rear Pointer은 각각 2bytes씩 차지해서 총 4bytes
  • 8084 bytes
• Linked-list Implimentation
  • Node의 info는 80bytes next Pointer는 4bytes
  • Node 하나 당 84bytes
• Array는 항상 일정한 수의 메모리 사용
• Linked-list는 item의 수가 많아질수록 많은 메모리 사용
• 하나의 item이 차지하는 메모리 크기가 클수록 Linked-list가 유리
  

Big-O Comparison

Operation	Array Implementaion	Linked-list Implementation
Constructor	O(1)	O(1)
MakeEmpty	O(1)	O(N)
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
IsFull	O(1)	O(1)
IsEmpty	O(1)	O(1)

|Destructor |O(1) |O(N) |