Chapter 6: Linked Structures (2)

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

Linked Structures

Review

▶ Big-O Comparison of Stack Operations

▶ Big-O Comparison of Queue Operations

Array vs. Linked Structure

Performance

Generally, array-based structures are faster than linked structures. (속도 -> 시간복잡도: 연산의 양)

• Most operations are equally fast for both array and linked structures (O(1)).
• For size(), clear(), and destructor(소멸자), the array is faster (O(1) vs. O(n)).

But, are those operations used often?

• data를 보 관하는 structure를 만들어서 data를 보관하고 있을 때, 이를 비운다던지 혹은 data structure를 삭제할 일은 많지 X
• size의 경우에는, 많이 쓰여야 되면 length라는 변수를 추가하면 O(1) 시간 복잡도 가질 수 있음 

-> 프로그래밍 시, 실질적으로 유의미한 차이는 없을 가능성이 크다.

• 속도: 비슷하지만 array가 조금 더 좋음

Memory Efficiency

It seems like the array-based structure is more efficient,

due to the pointer in ther node (linked structure). 

• The size of an 'int' type node is 12 bytes. (assuming int is 4 bytes, and the pointer is 8 (x64) bytes)
• For a single 'int' type data, it wastes 8 more bytes (less efficient).

What if the data stored in the node is much bigger? (e.g., 1KB).

• The wasted memory is relatively small (8 bytes for 1KB).

-> 노드에 보관하려는 데이터의 크기가 작은 경우에는 array가 더 효율적이지만, 커지게 될수록 차이가 없어지게 된다.

• 메모리 효율: 비슷하지만 array가 조금 더 좋음

Scalability

Still, array-based structures look better than linked structures.

What is better than an array of linked structures?

• Scalability (확장성, or flexibility)!

If the size of data structures fluctuates, we cannot decide the array's size.

• e.g., Kakao's message queues, network traffic queues, etc.

Linked structures allow the computer to adjust the size of data structures by newly allocating the node or deleting the unnecessary node. (Efficient memory management!)

 

So, what is better? Array? Or linked structures?

• It depends on the variability and the size of the data to be stored.

-> 메모리 자체의 효율성은 array가 좋지만, 메모리를 관리하는 memory management 측면에서는 linked structures가 좋다.

 

실제로 데이터를 보관하고 데이터를 찾는 방식은 array가 훨씬 더 유리하다. (linked: dereferencing 하며 위치 추정)

Unsorted List

Review: List Definitions

Linear relationship:

• Each element except the first has a unique predecessor, and each element except the last has a unique successor.

Length:

• The number of items in a list; the length can vary over time.

Unsorted list vs Sorted list

 

Review: Linked Structure Stack

▶ Linked Structure Stack

Unsorted List Definition using Node

▶ Inplementation Level

• insertItem, updateItem 제외
• stack의 구조를 그대로 가져오되, 이름만 topPtr -> listData 변경

 

Constructor 

▶ Inplementation Level

 

size()

▶ Inplementation Level

 

findItem()

▶ Inplementation Level

• unsorted -> linear search

 

item == tempPtr -> value

• 현재 코드에선 쓸모가 없지만, 현실에선 고유한 key 값으로 검색하여 내가 찾고자 하는 오브젝트를 찾아 오브젝트 전체를 return 해주어야 하는데, 이런 식으로 하게 된다.
• ex) 학번으로 검색하여 해당 학생의 정보 전체를 조회

 

appendItem()

▶ Inplementation Level

• 새로운 노드를 뒤에 넣는 array와 달리 linked structure는 앞에 넣음 (like push, 시간복잡도 고려 위함)
• 정렬되지 않은 리스트에서 새로운 노드를 맨 뒤에 넣으려면 넣어주려는 공간을 찾아야 하기에, 즉 traverse에 의해 O(N) 시간복잡도 가지지만, 앞에 넣으면 4번의 연산만 필요하여 O(1) 시간복잡도 가짐

removeItem()

▶ Logical Level

 

1. Find the node which has the value of 3. (traverse)

• tempPtr -> value != 3
• tempPtr = tempPtr -> next;

2. Remove the node pointed by tempPtr.

• Make the previous node (7) point to the next node (6).

이때, 6이라는 노드로는 tempPtr -> next를 이용해 갈 수 있지만, 7이라는 노드로는 3이라는 노드의 tempPtr을 통해 갈 수 없다.

 

그 이유는 single linked structure는 앞에 노드가 뒤에 노드를 가리키지만,

뒤에 노드는 앞에 노드를 가리키지 않는다는 근본적인 성질이 있기 때문이다.

 

 

 

Linked Structure Principle

▶ Can we make 'tempPtr' point to the right node?

• Yes, tempPtr = tempPtr -> next;

▶ Can we make 'tempPtr' point to the left node?

• No direct way, tempPtr = listData; tempPtr = tempPtr -> next; (traverse)

We can traverse nodes only following the directions of pointers in the nodes.

▶ Logical Level

 

When we find the node (3), we cannot move back to the previous node (linked structure principle).

• Solution: Compare one item ahead!

▶ Logical Level

 

1. Find the node which has the value of 3. 

• (tempPtr -> next) -> value != 3
• tempPtr = tempPtr -> next;

2. Remove the node next to the node pointed by tempPtr.

• Make the node (7) point to the next node (6).
• Before changing the node (7)'s next, we need to make another pointer for the node (3).
• deallocPtr = tempPtr -> next
• tempPtr -> next = (tempPtr -> next) -> next
• delete deallocPtr;

▶ Implementation Level

 

Is it good enough? (Edge cases)

• When the item does not exist (or the list is empty)
• When the i tem exists in the first location
• When the item exists in the last location

Review

▶ Big-O Comparison of Unsorted List Operations

 

array에서도 Linked Implementation처럼 appendItem() 함수 구현시 아이템을 앞에다 붙이려면

한 칸씩 다 뒤로 옮겨줘야 하기에, O(N)이 나온다. (traverse)

 

Sorted List

Sorted List Definition using Node

▶ Implementation Level

 

Sorted List Implementation

▶ We can reuse most operations implemented for Unsorted List.

 

findItem()

▶ Logival Level

 

For an array-based sorted list, we had two choices to find an item in the list.

• linear search - O(N)
• binary search - O(logN)

Can we apply the binary search to linked structures?

• No, due to the linked structure principle.
• We should implement it via linear search. -> Time Complexity: O(N)

array는 index만 알고 있으면 그 값에 바로 접근이 가능하지만 linked structure는 binary search를 쓰려면 처음부터 중간값까지 traverse로 값을 찾고, 또 처음으로 넘겨 이 중간값의 중간값까지 list를 옮겨 값을 찾을 때까지 반복야 하기에 사용할 수 없다.

 

insertItem()

▶ Logical Level

 

1. Make a new node that contains the 'item'.

2. Find the proper location to put the new node into.

• compare on item ahead

3. Put the new node and modifiy the links (pointers).

• newNode -> next = tempPtr -> next;
• tempPtr -> next = newNode;

▶ Implementation Level

 

Does this code handle edge cases well?

• When the list is empty.
• when the list is full.
• when the new item is put into the first location.
• When the new item is put into the second location.
• When the new item is put into the last location.
• When the new item is put into the second last location.

Review

▶ Big-O Comparison of Sorted List Operations

Doubly Linked List

Doubly Linked Structure

▶ doubly linked list

 

A doubly linked list is a list in which each node is linked to both its successor and its predecessor (back and next).

 

linked structure에서 traverse는 반드시 포인터가 연결되어 있는 방향으로만 갈 수 있다.

 

Review: insertItem()

▶ Logical Level

 

3. Put the new node and modify the links (pointers).

• The prev node (5) should point to the new node (9).
• The new node (9) should point to the next node (11).
• We already lost the pointer to the previous node (5).

위 문제를 해결하기 위해 compare one item ahead 방식을 사용했었다.

 

doubly_insertItem()

▶ Logical Level

 

3. Put the new node and modify the links (pointers).

• Now we can go back to the previous node (5).
• prevNode = tempPtr -> back;
• newNode -> back = prevNode;
• newNode -> next = tempPtr;
• prevNode -> next = newNode;
• tempPtr -> back = newNode;

doubly linked 방식을 사용하면 compare one item ahead 방식을 사용하지 않아도 된다. (차이점)

Can we do the same thing without using 'prevNode'?

 

doubly_insertItem() - only tempPtr

▶ Logical Level

 

3. Put the new node and modify the links (pointers).

• newNode -> back = tempPtr -> back; - 1 
• newNode -> next = tempPtr;
• (tempPtr -> back) -> next = newNode;
• tempPtr -> back = newNode; - 4
• 1 must be done before 4

1번보다 4번이 먼저 실행되면 5로 갈 수 있는 방법이 없어지게 된다.

• (9)는 newNode로, (11)은 tempPtr로 직접 접근하지만, (5)는 tempPtr -> back로 우회적으로 접근하기 때문

이처럼 연결하는 링크가 사라지게 되면 해당 노드에 접근할 수 있는 방법이 없어지게 되니 주의하여야 한다.

 

What's better (prevPtr + tempPtr vs. only tempPtr)?

• The additional pointer wastes only 8 bytes.
• But it is way much more intuitive.

-> 8bytes는 큰 공간이 아니기에 코드의 가독성을 위해 prevPtr을 사용하는 게 더 좋다.

 

What's better (singly vs. doubly)?

• It is up to design.
• It wastes 8 more bytes per node (overhead) but gives more flexibility.

singly 사용 시, back 하려면 compare one item ahead 방식,

혹은 tempPtr을 따라 오는 pointer를 하나 더 만들어 tempPtr의 바로 직전의 node를 가리키도록 하는 방식을 사용해야 한다.

 

doubly_insertItem() - Edge Case

▶ Logical Level

• We put the newNode in front of the node pointed by 'tempPtr'.
• Our search algorithm identifies (tempPtr -> value) > item.

What if the new item is supposed to be in the last location?

• When searching ends, tempPtr will point to the last node.
• We should distinguish between "putting into the last location" and "putting into the second last location".
• Edge-case handling

Doubly Linked Structures - Implementation Level

We should consider the following cases:

1. insertItem

• Insert into the empty list
• Insert into the first position
• Isert into the second position
• Insert into the last position
• Insert into the second last position
• etc.

마지막 노드의 next와 첫 번째 노드의 back은 nullPtr이어야 한다.

 

2. removeItem

• Remove from the empty list
• Remove from the first position
• Remove from the second position
• Remove from the last position
• Remove from the second last position
• etc.

Minimizing Edge Cases

▶ Using Head and Tail Nodes

 

edge case 보통 첫 번째 노드와 마지막 노드에서 발생하는데,

이를 신경쓰고 싶지 않다면 sorted 기준으로 상상할 수 있는 값 중 가장 큰 값의 노드와, 작은 값의 노드를 하나 만들어 그냥 list 안에 넣어주어, 이 두 개의 노드를 항상 기본적으로 가지고 있는 상태를 유지하도록 하게 하면 된다. (첫 번째, 마지막 노드 고정)

• Head: 가능한 가장 작은 값을 넣은 노드
• Tail: 가능한 가장 큰 값을 넣은 노드

-> insert, remove 모두 항상 list의 중간에서 일어나게 된다.

 

Putting head (possibly smallest) and tail (possibly largest) nodes into the sorted list can minimize edge cases.

 

Linked Structure using Array

▶ Linked Structure using Array

 

Heap이라는 공간에 new로 동적 할당하는 방식이 아닌, 2차원 array를 통해서도 linked structure를 만들 수 있다.

• 첫 번째 노드는 항상 제일 위 칸

효율성이나 속도 면에서 기본적으로 array가 좋은데도 linked structure를 사용하는 이유는 scalability라는 확장성 때문이다.

즉, memory management의 효율성 때문에 linked structure를 사용하는 건데,

위처럼 linked structure를 array로 구현하면 비효율적이다.

Copy Constructor

C/C++ Basics: it is almost about "copy"

Shallow Copy

▶ Shallow Copy

 

tempStack이 가지고 있는 변수는 topPtr 하나이다.

즉, HEAP의 노드들은 tempStack 자료구조의 일부가 아니다.

-> copy 시, topPtr만 복사된다. (shallow copy, 얕은 복사)

 

Problem

▶ Shallow Copy: Problem

 

At default, the pass-by-value generates a shallow copy.

This default method used for pass-by-value is not the best way when a data member pointer points to dynamic data.

 

Since both tempStack and copiedStack point to the same memory spaces in the HEAP,

changes made inside the function could lead to the dangling(매달려 있는) pointer.

• dangling pointer: 내부에서 데이터를 수정하여 외부에 있는 포인터가 갈 곳을 잃어버리는 문제

Deep Copy

▶ Deep Copy

• tempStack과 deepCopiedStack은 완전히 별개의 데이터

Shallow Copy vs. Deep Copy

A shallow copy copies only the class data members and does NOT copy any pointed-to data.

A deep copy copies not only the class data members but also makes separately stored copies of any pointed-to data.

-> Deep Copy를 사용하면 Dangling Pointer 혹은 메모리 누수라는 문제 예방 가능

 

Copy Constructor

함수 호출 시, default는 shallow copy로 설정이 되어있고,

이때 이를 deep copy로 바꾸고 싶으면 copy constructor를 설정해야 한다.

 

A deep copy can prevent the dangling pointer caused by a shallow copy.

To use a deep copy as a default method for copy, we should write what is called a copy constructor.

When there is a copy constructor provided for a class, the copy constructor is used to make copies for pass-by-value.

Copy constructor is a special member function of a class that is implicitly called under these three circumstances:

• passing object parameters by value.
• returning an object as the return value of a function.
• initializing an object variable in a declaration. 
  • StackType<int> newStack = tempStack; -> copy constructor 자동 적용 O

▶ Copy Constructor

• What about the below case?
  • StackType<int> newStack;
  • newStack = tempStack; -> copy constructor 자동 적용 X
  • It still generates a Shallow Copy.

위 경우에도 copy constructor을 쓰도록 만들고 싶으면 '=' 역할을 바꿔주어야 한다.

 

Assignment Operator ('=')

The default method used for the assignment of class ('=' operator) objects makes a shallow copy.

If your class has a data member pointer to dynamic data,

you should write a member function to overload the assignment operator to make a deep copy of the dynamic data.

▶ Assignment Operator ('=')

 

deep copy가 무조건 좋은 건 아니고, 프로그래밍의 효율성을 생각하면 shallow copy가 훨씬 좋다.

때문에 일반적인 observer 상황에선 shallow copy를, 자료 구조체의 수정이 필요한 경우에만 deep copy를 써야 한다.