CH 05 Linked Structure

67635 단어 python자료구조CC

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

OperationArray ImplementaionLinked-list Implementation
ConstructorO(1)O(1)
MakeEmptyO(1)O(N)
InsertItemO(1)O(1)
DeleteItemO(N)O(N)
IsFullO(1)O(1)
LengthIsO(1)O(1)
RetrieveItemO(N)O(N)
ResetListO(1)O(1)
GetNextItemO(1)O(1)
DestructorO(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

OperationArray ImplementaionLinked-list Implementation
ConstructorO(1)O(1)
MakeEmptyO(1)O(N)
InsertItemO(1)O(1)
DeleteItemO(N)O(N)
IsFullO(1)O(1)
LengthIsO(1)O(1)
RetrieveItemO(N)O(N)
ResetListO(1)O(1)
GetNextItemO(1)O(1)
DestructorO(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

OperationArray ImplementaionLinked-list Implementation
ConstructorO(1)O(1)
MakeEmptyO(1)O(N)
PushO(1)O(1)
PopO(1)O(1)
IsFullO(1)O(1)
IsEmptyO(1)O(1)
TopO(1)O(1)
DestructorO(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

OperationArray ImplementaionLinked-list Implementation
ConstructorO(1)O(1)
MakeEmptyO(1)O(N)
EnqueueO(1)O(1)
DequeueO(1)O(1)
IsFullO(1)O(1)
IsEmptyO(1)O(1)

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

[Algorithm log] 그리디#17 백준 2012
MSSQL 스크립트 .zip

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage