링크드 리스트(Linked List)

배열과 링크드 리스트
배열

• 배열은 크기가 정해진 데이터 공간. 크기가 정해지면 바꿀 수 없다.
• 배열은 각 index에 즉시 접근 가능
• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다. 최악의 경우 배열의 길이 N만큼을 옮겨야 되서 O(N)의 시간 복잡도를 가진다.
• 배열은 새로운 값을 추가하면 새로운 공간을 할당해야 해서 비효율적

리스트
ex) 화물열차
["기관실"] -> ["시멘트"] -> ["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]

• 리스트는 크기가 정해지지 않은 데이터 공간, 연결 고리로 이어주면 자유롭게 늘어난다.
• 리스트는 특정 원소에 접근하려면 연결고리를 따라 탐색해야 한다. 최악의 경우 모든 화물칸을 탐색해야 함. O(N)의 시간 복잡도를 가진다.
• 리스트는 원소를 중간에 삽입/삭제 하기 위해 앞 뒤의 포인터만 변경하면 된다. 원소 삽입/삭제 O(1)의 시간복잡도를 가진다.
  연결 고리를 포인터라 부르고, 각 화물 칸을 노드

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

파이썬의 list는 array로 구현되어 있다.
내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계되어 있다.
파이썬의 배열은 링크드 리스트로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조 이다.

링크드 리스트 추가, 출력, index값 가져오기, 리스트 사이에 추가, 리스트 값 제거 코드

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value) #새로운 노드
        if index == 0:
            new_node.next = self.head #[6] -> [5]
            self.head = new_node # head -> [6] -> [5] -> ...
            return

        node = self.get_node(index -1) #index - 1번째 노드 가져오기(앞에 추가 해야 되서 -1)
        next_node = node.next # next_node는 현재 노드의 다음꺼
        node.next = new_node # node.next의 다음꺼는 new_node
        new_node.next = next_node #new_node의 다음꺼 next_node
        return

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return

        node = self.get_node(index -1)
        node.next = node.next.next
        return
        



linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
linked_list.add_node(2, 6)
# linked_list.delete_node(0)
# linked_list.get_node(0) # -> 5를 들고 있는 노드를 반환해야 합니다!
# print(linked_list.get_node(2).data)
linked_list.print_all()