[파이썬 알고리즘] 연결리스트(Linked List) 기초.

 - 배열 vs 연결리스트

배열 : 파이썬의 리스트, 접근은 쉬우나 삽입이 어렵다.

연결리스트 : 직접 구현해야 하고,  삽입이 쉽고, 접근은 어렵다.

경우	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다.	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 좋다

강의에서도 말했듯이 이 연결리스트는 자신이 직접 구현해 봐야한다. 하얀 도화지 위에서 이걸 다 적어낼수 있어야한다.

class ListNode:
    def __init__(self, val=0, next=None):
        # 값이랑 화살표를 정의
        self.val = val
        self.next = next
        # 나의 val는 입력 받은 val고,
        # 나의 next는 입력 받은 next야


class LinkedList:
    # 삽입, 삭제 기능이 있어야 한다.
    def __init__(self):
        self.head = None

        def append(self, val):
            # 값을 받았다면
            if not self.head:
                # 아직 입력 받은 게 없다면
                self.head = ListNode(val, None)
                # 화살표는 없고 입력 받은 값을 넣어주는 ListNode를 만들어주고 head에 넣자
                return

            node = self.head
            # 보이는 node를 head로 지정
            while node.next:
                node = node.next

            node.next = ListNode(val, None)
            # while 문으로 node 끝으로 가고 List node로 붙혀줘라