Chapter 5: Linked Structures

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

Linked Structure 

Array-based Stack Implementation

▶ In the previous implementation, we consider an entire stack (a set of items) as a single object (array).

 

New stack Implementation

▶ Here, we consider each item in the stack a single object (Node).

• How could we define relationships between items? (Who's on top of whom?)

Node Implementation

▶ A pointer can be used for it!

• The pointer named 'next' will point to the next 'NodeType'.

We call it "linked structures".

Each node has a value and a pointer pointing to the next node.

▶ We need another pointer to indicate the top of the stack.

 

Why We Need topPtr?

 

All variables have their own name and memory space.

Computers use these variable names to access each memory space.

Dynamically allocated memory spaces do not have bound(결속된) names.

• 변수 이름 없이 포인터를 통해 접근, 이때 동적할당된 공간에 포인터가 없는 경우 메모리 누수가 발생한 것임.

A dynamically allocated variable needs a pointer to be accessed.

All but the first (top) node is pointed to by other pointers. (포인터 없으면 변수에 접근 불가)

topPtr points to the top node.

• 포인터 없으면 변수에 접근 불가, 때문에 top node를 가리키는 topPtr 필요

Stack Definition using Node

▶ Implementation Level

 

Tracing Client Code

▶ Tracing Client Code

 

push()

▶ Logical Level

• tempStack.push(5);

0. (Exception Handling)

1. Make a new 'NodeType'

2. Set the new NodeType's 'value' as '5'

3. Make the new NodeType's 'next' point to the old top

4. Make 'topPtr' point to the new Node Type

 

이때, 3번과 4번의 순서가 바귀면 7이라는 Node를 가리키는 포인터가 존재하지 않게 된다. (메모리 누수 -> 런타임 에러)

▶ Implementation Level

 

※ 포인터 1 = 포인터 2: 포인터2가 가리키고 있는 걸 포인터 1도 가리키도록 만들라는 의미이다.

 

Validating Edge Cases

• An "edge case" is a term commonly used in software development to refer to(~을 의미하는) a unique of extreme scenario that deviates from the norm(일반적이지 않은).
• While a program may function well under typcal conditions or inputs, it can encounter unexpected behavior or problems when faced with unusual inputs.

isFull()

Pushing an item generates a new dynamically allocated node.

HEAP is NOT an infinite space.

Operating systems have the default HEAP size for each program, but you can adjust when compiling the code.

When the HEAP is saturated(포화된), 'new' instruction fails and throws an exception.

▶ Implementation Level

 

pop()

▶ Logical Level

 

1. Make the topPtr point to the second top node

2. We need to delete the top node (5) .... But we lost pointers pointing to it (topPtr)

3. We need a temporary pointer for it

▶ Logical Level (ver. 2)

 

0. (Exception Handling)

1. Make tempPtr which points to the top node

2. Make the topPtr point to the second top node

3. Delete the node pointed by tempPtr (tempPtr (local variable) will automatically disappear)

▶ Implementation Level

 

isEmpty()

▶ Implementation Level

 

Destructor

▶ Implementation Level

 

When a local stack variable goes out of scope, the memory space for data member topPtr is deallocated.

But the nodes are NOT automatically deallocated.

 

clear()

▶ Implementation Level

 

size()

▶ Implementation Level

 

Big-O Comparison of Stack Operations

▶ Big-O

Linked Structure (2)

Queue Definition using Nodes

▶ Logical Level

▶ Implementation Level

 

enqueue()

▶ Logical Level

 

0. (Exception Handling)

1. Make a new 'NodeType' (new node)

2. Set the new node's 'value' as '6' 'next' as nullptr

3. Make the last node's 'next' point to the new node

4. Make pRear point to the new node

▶ Implementation Level

 

Exception Handling이 필요한 상황

• queue가 full -> enqueue 불가
• queue가 empty -> dequeue 불가

isFull()

▶ Implementation Level

 

enqueue() 

▶ Implementation Level: isFull -> Exception Handling

 

Is it good enough? Let's think about when the queue is empty.

 

▶ 런타임 에러 발생

• pRear가 가리키는 주소의 next 값을 newNode로 바꿔주려 하는데, pRear는 아무것도 가리키고 있지 않음

▶ 런타임 에러 해결

▶ Implementation Level: isFull -> Exception Handling (런타임 에러 해결)

 

isEmpty()

▶ Implementation Level

 

dequeue()

▶ Logical Level

 

1. Make tempPtr which points to the front node (메모리 누수 방지)

2. Make the pFront point to the second front node

3. Delete the node pointed by tempPtr (tempPtr (local variable) will automatically disappear)

▶ Implementation Level

▶ Logical Level (Edge Case)

▶ Implementation Level (Edge Case)

Destructor and clear()

▶ Implementation Level

 

※ clear는 주로 flush로 많이 사용한다.

 

size()

▶ Implementation Level

 

Big-O Comparison of Queue Operations 

▶ Big-O

 

물론, length 변수를 미리 만들고 enqueue시 length++, dequeu시 length--를 미리 해주면 size()의 시간 복잡도는 O(1)이다.