[자료구조] L05.Linked Structures

• toc {:toc}

Review

• 같은 타입의 아이템이 순서를 지닌닌 그룹. 하나의 입구로 들어가고 나오는 구조

• LIFO(Last in First out) 구조

• Queue

• 같은 타입의 아이템의 순서가 있는 그룹. 뒤에서 들어가고 앞으로 나오는 구조

• FIFO(First in First out) 구조

• List vs Array

• 매우 유사하나, 같은 개념은 아니다.

• Array : 구체적인 데이터 타입

  • 다른 ADT들을 구현하는데 사용될 수 있다.

• List : 추상적인 데이터 타입(Abstract Data Type, ADT)

  • 개념적인 데이터 타입
  • array를 사용하지 않고 구현할 수 있다.

Stack Implementation(Linked List)

• ADT 장점 : 구현의 방식이 변경될 수 있다. ADT 개념을 잘 구현하기만 하면 되기 때문이다.

• 스택의 동적 배열 구현의 단점 - 스택의 최대 크기를 파라미터로 전달받아 생성돼야 한다.

  • 스택의 크기를 중간에 동적으로 변환할 수 없다.

• 스택의 크기를 파라미터로 받지 않고 push 할 때 스택 요소의 공간을 동적으로 할당할 수 있다.

  • 어떻게?
  • Linked Structure!

• Operation ‘new’

  • free store, heap을 이용 가능하다면 new는 요청된 객체를 할당하고 할당된 주소를 반환한다.

class StackType{
public:
	StackType();
	~StackType();
	bool IsEmpty();
	bool IsFull();
	void Push(ItemType item);
	void Pop();
	ItemType Top();
private:
	NodeType* topPtr;
}
 
struct NodeType{
	ItemType info;
	NodeType* next;
}
 
newItem = 'B';
// Push
if (IsFull())
	throw FullStack();
NodeType* location;
location = new NodeType<char>  // 새로 들어올 위치 동적 할당
location->info = newItem;      // info, next에 정보, 위치 지정
location->next = topPtr;
topPtr = location;             // top location 수정
 
// Pop
if(IsEmpty())
	throw EmptyStack();
else{
	NodeType* tempPtr;
	tempPtr = topPtr;
	topPtr = topPtr->next;
	delete tempPtr;
}
 
// Top
if (IsEmpty())
	throw EmptyStack();
else
	return topPtr->info;

• Linked List

• NodeType : 값을 지닐 ItemType과 다음 NodeType을 나타내는 포인터를 가진다. ⇒ info(data) + next(pointer)

• Comparing stack implementations

Operation	Array Implementation	Linked Implementation
Class constructor	O(1) top을 -1로 설정	O(1) Null NodeType 포인터 생성
Make Empty	O(1) Index를 0으로 설정	O(N) 순회하며 할당 해제
IsFull	O(1) top == Max인지 확인	O(1) heap 메모리 오류 확인
IsEmpty	O(1) top == 0인지 확인	O(1) 첫 시작 location이 Null인지 확인
Push	O(1) 맨 위에 붙여주기	O(1) 새로운 노드 생성, top 노드로 연결
Pop	O(1) 맨 위 값 빼기	O(1) 맨 처음 top 값 빼기
Destructor	O(1) 배열 할당 해제	O(N) 순회하며 할당 해제

• Why is a destructor needed? 동적 할당(new)를 통해 할당된 heap의 메모리는 main 함수가 끝나더라도 자동으로 할당 해제되지 않는다. 명시적으로 할당을 해제해야 한다. 만약 명시적으로 할당 해제하지 않고 함수가 끝나게 되는 경우 포인터가 가리키는 노드는 할당이 된 채로 낭비된다.

Queue Implementation(Linked List)

class QueType{
public:
	QueType();
	~QueType();
	bool IsEmpty();
	bool IsFull();
	void Enqueue(ItemType newItem);
	void Dequeue(ItemType& item);
	void MakeEmpty();
private:
	NodeType<ItemType>* qFront = NULL;
	NodeType<ItemType>* qRear = NULL;
}
 
// Enqueue
NodeType<ItemType>* ptr;
ptr = new NodeType<ItemType>;
ptr->info = newItem;
ptr->next = NULL;
if(qRear == NULL)      // 큐가 비어있을 때 
	qFront = ptr;      // Front 설정
else
	qRear->next = ptr; // 안 비어 있으면 이전값을 들어온 값과 연결
qRear = ptr;           // qRear 수정
 
// Dequeue
NodeType<ItemType>* tempPtr;
tempPtr = qFront;
item = qFront->info;
qFront = qFront->next;
if(qFront == NULL)
	qRear = NULL;
delete tempPtr;
 

• Comparing queue implementations

Operation	Array Implementation	Linked Implementation
Class constructor	O(1) front, rear, items 설정	O(1) front, rear Null 지정
Make Empty	O(1) front, rear 초기화	O(N) front == Null이 될 때까지 순회하며 해제
IsFull	O(1) ((rear+1)%max == front) 확인	O(1) heap 메모리 오류 확인
IsEmpty	O(1) rear == front 확인	O(1) front가 Null인지 확인
Enqueue	O(1) rear index 설정, 입력	O(1) 새로운 노드 생성, rear 노드로 연결
Dequeue	O(1) front index 설정, 반환	O(1) front 값 빼기
Destructor	O(1) 배열 할당 해제	O(N) 순회하며 할당 해제

Static vs Dynamic

• 두 가지 다른 맥락에서 dynamic, static 용어를 사용한다.

• 이 두 용어를 구분할 필요가 있다.

• Memory allocation 관점

  • Static memory allocation : new/malloc을 사용하지 않은 지역 변수가 생성한 메모리는 stack segment에 위치하고 정적 메모리 할당을 한다.
  • Dynamic memory allocation : new/malloc을 사용하여 초기화된 변수가 생성한 메모리는 heap segment에 위치하고 동적 메모리 할당을 한다.

• Data structure 관점

  • Static data structure : 자료 구조의 크기가 고정되어 있는 경우
    • ex) Array-based stack/queue
  • Dynamic data structure : 자료 구조의 크기가 고정되어 있지 않은 경우 변하는 경우
    • ex) Linked structure-based stack/queue

Unsorted List Implementation(Linked List)

• Unsorted
• InsertItem : 정렬없이 맨 처음에 붙인다.
• RetrieveItem : 순회하면서 값을 찾는다.
• DeleteItem : 순회하며 값을 찾고 할당 해제를 하고, 이전 노드의 next값을 해제하는 노드 다음으로 연결시켜줘야 한다.
  • 하지만 단방향 linked list이기 때문에 원하는 값에 도달하는 경우 이전 값을 알 수 없다.
  • 때문에 2단계 앞의 정보를 확인하는 방식을 사용한다.

class UnsortedType{
public :
	UnsortedType();
	~UnsortedType();
	void MakeEmpty();
	bool IsFull() const;
	int LengthIs() const;
	void RetrieveItem(ItemType& item, bool& found);
	void InsertItem(ItemType item);
	void DeleteItem(ItemType item);
	void ResetList();
	void GetNextItem(ItemType& item);
private :
	NodeType<ItemType>* listData;
	int length;
	NodeType<ItemType>* currentPos;
} ;
 
// InsertItem
NodeType<ItemType>* location;
location = new NodeType<ItemType>;
location->info = item;
location->next = listData;
listData = location;
length++;
 
// RetrieveItem
bool moreToSearch;
NodeType<ItemType>* location;
location = listData;
found = false;
moreToSearch = (location != NULL);
while(moreToSearch && !found){
	if(item == location->info){
		found = true;
	}
	else{
		location = location->next;
		moreToSearch = location != NULL);
	}
}
 
// DeleteItem
NodeType<ItemType>* location = listData;
NodeType<ItemType>* tempLocation;
 
if(item == listData->info){
	tempLocation = location;
	listData = listData->next;
}
else{
	while(!(item == location->next->info))
		location = location->next;
	tempLocation = location;
	location->next = location->next->next;
}
delete tempLocation;
length--;

• Comparison unsorted list implementations

Operation	Array Implementation	Linked Implementation
Class constructor	O(1) length 지정	O(1) listData = NULL 지정
Destructor	O(1) 동적할당X	O(N) NULL 까지 순회하며 해제
MakeEmpty	O(1) length = 0	O(N) 순회하며 해제
IsFull	O(1) length == MAX 확인	O(1) heap 메모리 오류 메시지 확인
LengthIs	O(1) length 반환	O(1) length 반환
ResetList	O(1) currentPos = -1	O(1) currentPos = listData
GetNextItem	O(1) currentPos++ 추출	O(1) currentPos→next→info
RetrieveNextItem	O(N) or O(logN) 탐색 필요하기 때문	O(N) 순회하여 탐색
InsertItem	O(1) 맨 뒤에 삽입	O(1) 맨 앞에 삽입
DeleteItem	O(N) 탐색해 지우고 빈자리 이동시켜야 함	O(N) 탐색해 지우기

Sorted List Implementation(Linked List)

1 → 3 → 7 → 9

• Sorted
• InsertItem : 위치를 탐색하고 해당 위치에 삽입해야 한다. 4를 삽입하는 경우 3과 7 사이에 삽입해야 하기 때문에 info == 3인 노드의 next를 4로 지정해줘야 한다. Unsorted와 같이 2단계 뒤를 생각하는 방식이 있으나, 10을 삽입하는 경우 즉, 맨 마지막에 삽입하는 경우 2단계 뒤의 info를 확인하는 방식은 NULL값을 받기 때문에 사용할 수 없다. 때문에 포인터를 2개를 사용하여 해결한다.
• RetrieveItem : 이미 정렬되어 있기 때문에 item보다 큰지, 작은지, 같은지를 판단하면 된다. 이진 탐색을 사용할 수는 있으나, 이진 탐색을 사용하더라도 복잡도가 O(logN)이 되지는 않는다.(단방향이므로)

class SortedType{
public :
	SortedType();
	~SortedType();
	void MakeEmpty();
	bool IsFull() const;
	int LengthIs() const;
	void RetrieveItem(ItemType& item, bool& found);
	void InsertItem(ItemType item);
	void DeleteItem(ItemType item);
	void ResetList();
	void GetNextItem(ItemType& item);
private :
	NodeType<ItemType>* listData;
	int length;
	NodeType<ItemType>* currentPos;
} ;
 
// RetrieveItem
NodeType<ItemType>* location;
location = listData;
found = false;
while((location!=NULL) && !found){
	if (location->info < item)
		location = location->next;
	else if (location->info == item)
		found = true;
	else
		location = NULL;
}
 
// InsertItem
bool isFindLoc;
NodeType<ItemType>* predLoc = NULL;
NodeType<ItemType>* location = listData;
NodeType<ItemType>* newNode;
 
newNode = new NodeType<ItemType>;
newNode->info = item;
 
if(listData == NULL){
	newNode->next = NULL;
	listData = newNode;
	length++;
}
else{
    while (true){                   // for searching.
        if(predLoc == NULL)         // Add item at the first index.
            isFindLoc = (item <= location->info);
        else if(location == NULL)   // Add item at the last index.
            isFindLoc = (item >= predLoc->info);
        else 
            isFindLoc = (predLoc->info <= item && item <= location->info);
 
        if(isFindLoc){
            newNode->next = location;
            length++;
            if(predLoc == NULL){
                listData = newNode;
                break;
            }
            predLoc->next = newNode;
            break;
        }
        else{
            predLoc = location;
            location = location->next;
        }
    }
}

• Comparing sorted list implementations

Operation	Array Implementation	Linked Implementation
Class constructor	O(1) length 지정	O(1) listData = NULL 지정
Destructor	O(1) 동적할당X	O(N) NULL 까지 순회하며 해제
MakeEmpty	O(1) length = 0	O(N) 순회하며 해제
IsFull	O(1) length == MAX 확인	O(1) heap 메모리 오류 메시지 확인
LengthIs	O(1) length 반환	O(1) length 반환
ResetList	O(1) currentPos = -1	O(1) currentPos = listData
GetNextItem	O(1) currentPos++ 추출	O(1) currentPos→next→info
RetrieveNextItem	O(N) or O(logN) 탐색 필요하기 때문	O(N) 순회하여 탐색
InsertItem	O(N) 순회하여 위치 탐색, 자리 이동, 삽입	O(N) 순회하여 삽입
DeleteItem	O(N) 탐색해 지우고 빈자리 이동시켜야 함	O(N) 탐색해 지우기