Review 8 - Python Data Structure

https://eglife.tistory.com/75

Review 7 - Python Algorithm design & Testing & Debugging

의사소통을 할 때, 못 알아 들었으면 못 알아 들었다고 확실히 말하자.

 

이해 한 것, 이해 못 한 것을 정확히 구분해서 빨리 빨리 물어보고 해결해야 함

 

코딩을 시작하기 전에, 알고리즘 구조를 먼저 고민하고 Implementation에 들어가기.

 

코딩을 무작정 시작하기 보다, 사전에 의사결정을 먼저 내리고 논리를 갖고 시작해야한다.

 

즉, 내가 구현한 알고리즘을 사람의 언어로 먼저 설명하고 그 다음 코드를 짜보는(코드로 번역) 순서로 들어가야 한다.

 

 

1. Array

지금껏 배워 온 데이터 구조

 

Array는 지금껏 배운 구조의 '기저'에 있는 데이터구조이다. 가장 Foundation 영역!

 

지금껏 배운 데이터 구조의 다양한 Method들 ( ex: Append, pop, insert, remove, get, size etc. )을 구현하기 위해서 사용된 기초 블럭이다.

 

Array는 Data Block이 서로 Neighboring 되어 있다. 즉, Data Memory가 따닥따닥 붙어 있어서, 첫 번 째 element의 주소만 알아도, 나머지 녀석들의 주소를 알아내기가 쉽다. => Sequential access 가능!

 

그래서, list에서 i - th data를 조회하는 것이 편했던 것이다. 이것이 장점!

단점은, 귀찮지만 초기 initialize 할 때 미리 크기 length를 정해줘야 한다. => Fixed length

 

이렇게 Fixed Length인데, 우리가 아는 list는 자유롭게 data를 더하고 뺄 수가 있다.

 

list의 하부구조가 array이고 얘는 fixed length인데 어떻게 list는 이것에서 자유로울 수가 있는 거지?

--> #Array Resizing

 

Resizing은 사실 굉장히 Naive한 Technique 이다 ;; 

 

새로운 Memory box를 다시 만든 다음에 복붙을 하는 작업이다.

 

그래서 Resizing은 비싼 작업이라고 불린다. 그래서 too many resizing은 너무 비효율적이라, Resizing을 한 번 할 때마다 적절히 확~ 늘려서 Resizing을 한다.

 

For Resizing 효율 + Memory 낭비 막기

Python이 취한 방법. 요렇게 애매하게 Resizing을 진행한다.

즉, Array의 장점 : i-th element에 접근하기 편함  단점 : Append, pop 할 때마다 Resizing이라는 비싸고 귀찮은 작업이 동반

 

이 Array의 단점을 극복하기 위해 아예 하부구조를 Array 말고 좀 더 Dynamic 한 걸 써보자.. 라는 고민에서 나온 개념이 바로 밑 2번이다.

 

 

2. Linked Lists

 

Array는 5번 째 element 조회할 때, 1번 째 주소를 알고 있으면 거기서 그냥 +4 하면 거기에 data가 있어서 data retrieve가 편했다. 하지만 Linked List는 5번 째 element 가려면 0->1->...->5 이렇게 하나씩 이동하며 주소를 찾아다녀야 한다. 즉, element들이 Neighbor하지 않다.

 

즉, Array / Linked List는 사실 trade off 관계이다. Linked list가 element 조회가 어려운만큼 data를 추가/제거 할 때,  Resizing이 필요 없다는 장점이 있다.!

 

class LinkedNode():
    def __init__(self,x):
        self.val = x
        self.next = None
    
a = LinkedNode(5)
b = LinkedNode(7)
a.next = b

 

a와 b 사이의 관계를 부여하는 것 : a.next = b

print(b.val)
print("a:",a.val,"\nb:",a.next.val)
7
a: 5 
b: 7

 

이런 특성을 가지고 Single Linked List를 다뤄보자.

(Doubly Linked List도 공부를 해보자)

 

# add first / get first
class SLList():
    def __init__(self) -> None :
#         self.first = LinkedNode(None) # 첫 빠따 정의해놓기
        self.first = None
        
        self.size = 0
    def addFirst(self, x:int) -> None:
        p1 = LinkedNode(x) # 일단 생성
        p1.next = self.first
        self.first = p1
        
        self.size+=1
        
    def getFirst(self) -> int:
        if self.first:
            return self.first.val
        else : return None
        
    def getSize(self) -> int:
#         return self.size
        size = 0
        curr = self.first
        while curr!=None :
            size += 1
            curr = curr.next
        
        return size

 

여기서 getSize를 보면 size 하나 알아보는데 O(N) 시간이 걸리는 불상사가 발생한다.

 

그래서 getSize할 때 위와 같이 하지 말고, 주석된 self.size를(별도로 저장해놨던 value) 반환하면 Time complexity 낭비가 없다.

 

    def append(self,v :int) -> None:
        newNode = LinkedNode(v)
        curr = self.first
        
        if curr == None :
            newNode.next = self.first
            self.first = newNode
        else :
            while curr.next != None :
                curr = curr.next
            curr.next = newNode
        
        self.size += 1

 

이런식으로 append 함수를 쓸 수 있는데 sentinel을 이용해 구현해보자.

 

코드가 복잡해지는게 싫으니까..

 

 

3. Linked List with Sentinel

 

sentinel 부분은 변동이 없다.

# add first / get first
class SLList():
    def __init__(self) -> None :
#         self.first = LinkedNode(None) # 첫 빠따 정의해놓기
        
#         self.first = None
        self.sentinel = LinkedNode(-1)
        self.size = 0
        
    def addFirst(self, x:int) -> None:
        p1 = LinkedNode(x) # 일단 생성
        p1.next = self.sentinel.next
        self.sentinel.next = p1
        
        self.size+=1
        
    def append(self,v :int) -> None:
        self.size += 1
        curr = self.sentinel
        while curr.next != None :
            curr = curr.next
        curr.next = LinkedNode(v)
        
    def getFirst(self) -> int:
        if self.sentinel.next:
            return self.sentinel.next.val
        else : return None
        
    def getSize(self) -> int:
#         return self.size
        size = 0
        curr = self.sentinel.next
        while curr!=None :
            size += 1
            curr = curr.next
        return size    
 ----
 Test Code Below
 
L = SLList()
# print(L.first.next)
# print(L.getFirst())
L.append(100)
L.append(102)
​
L.addFirst(4)
L.addFirst(11)
L.addFirst(7)
L.append(101)
​
print("size:",L.getSize())
curr = L.sentinel.next
while curr:
    print(curr.val)
    curr = curr.next
    
print("size:",L.getSize())
# # L.getFirst()
# # print(L.getFirst(),L.next.getFirst(),L.next.next.getFirst())
# print(L.first.val,L.first.next.val,L.first.next.next.val)
# print("size:", L.getSize())
# print("size:", L.getSize())
# print("size:", L.getFirst())
size: 6
7
11
4
100
102
101
size: 6

 

addFirst( ) 에 비해 느린 append( ) 를 구조적으로 빠르게 하는 방법? Doubly Linked List ( DLList 이다 )

Append 보다 addLast 개념으로 접근이 된다. by using sentinels of both sides

Append나 Remove를 자주하는 경우엔, deque() [DLList로 구현된 파이썬 모듈] 을 써는 것이 효율적이다.

 

 

4. Doubly Linked List

 

간단히 말하면, Node를 추가할 때 SLList에선 Node의 Next만 고려했는데, 이제 Previous도 고려한다는 것이다.

 

이를 간편하게 구현하기 위해 Sentinel을 Head, tail 이렇게 2개를 만들었으며

 

Head 에선 Next를 난발하고, Tail에선 Prev을 난발한다.

 

Addfirst는 Head로 편하게 구현하고, append = addLast 개념이라 Tail로 편하게 구현이 가능하다.

 

한 가지 주의할 것은 Add first 든 Append 든 Node를 추가할 때 Node를 중심으로 총 4번의 관계를 형성해야하는데, 이 때 순서가 중요하다.

 

1. "New Node"를 기준으로 Next / Prev 관계를 형성해준다. addFirst의 경우 맨 앞에 추가하는거라 Head를 기준으로 관계 형성 -> 그러면 총 2회의 관계형성이 된다.

 

2. 그 다음 "Head"를 기준으로 관계를 2회 형성한다. 기존 Head의 next에 해당하는 first element를 끊기 위해서 Head.next의 Prev을 "New Node"로 만들고, Head의 next를 "New Node"에 할당한다. 이게 총 2회의 관계형성이다.

 

이렇게 총 4회의 관계를 형성하고 나면 비로소 New Node가 제일 Linked List 제일 앞단에 자리잡게 된다.

 

Append(Add Last)의 경우도 같은 맥락이며, Head 대신 Tail과 상호작용한다는 차이점이 있다.

 

말로는 주절주절 좀 복잡하게 설명되었는데 아래 코드를 보면 이해가 쉬울 것이다.

 

DLList의 경우 한 번 자료구조를 만드는 것은 귀찮았는데, 만들고 나니까 이래저래 이용해먹기 편한 녀석이라는 생각이 든다 ㅎㅎ

 

class LinkedNode:
    def __init__(self,val:int) -> None :
        self.val = val
        self.next = None
        self.prev = None

class DLList:
    def __init__(self) -> None :
        self.senti_head = LinkedNode(-1)
        self.senti_tail = LinkedNode(-100)
        self.senti_head.next = self.senti_tail
        self.senti_tail.prev = self.senti_head
        self.size = 0
    
    def addFirst(self,v :int) -> None :
        new_node = LinkedNode(v)
        
        new_node.next = self.senti_head.next
        new_node.prev = self.senti_head        
        
        self.senti_head.next.prev = new_node
        self.senti_head.next = new_node

        self.size += 1
    
    def append(self,v :int) -> None :
        new_node = LinkedNode(v)
    
        new_node.prev = self.senti_tail.prev
        new_node.next = self.senti_tail
        
        self.senti_tail.prev.next = new_node
        self.senti_tail.prev = new_node
        
        self.size +=1
        
    def getFirst(self) -> int :
        if self.senti_head.next != self.senti_tail :
            return self.senti_head.next.val
        else : return None

    def getLast(self) -> int :
        if self.senti_tail.prev != self.senti_head :
            return self.senti_tail.prev.val
        else : return None
    
    def getSize(self) -> int:
        return self.size
    
 ## TEST CODE
DL = DLList()
print("get first:",DL.getFirst())
DL.append(100)
print("get first:",DL.getFirst())
DL.addFirst(1)
DL.addFirst(3)
DL.addFirst(0)
DL.append(102)
DL.addFirst(2)
DL.append(101)
​
​
curr = DL.senti_head.next
while curr.next :
    print(curr.val)
    curr = curr.next
print("get first:",DL.getFirst())
print("get last:",DL.getLast())
print("get size:",DL.getSize())
get first: None
get first: 100
2
0
3
1
100
102
101
get first: 2
get last: 101
get size: 7

 

 

- E. O. D -