[공부] 내일배움캠프 알고리즘 2주차 Linked List

내일배움캠프 알고리즘 2주차

Array

• 배열은 크기가 정해진 데이터 공간
• 원소에 즉시 접근할 수 있다 (상수 시간 내에)
• 원소를 중간에 삽입 / 삭제를 하려면 모든 원소를 옮겨야한다.
• 최악의 경우 배열의 길이 N 만큼 옮겨야 하므로 O(N) 의 시간복잡도를 가질 수 있다.
• 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조이다.

Linked List

• 크기가 정해지지 않은 데이터의 공간
• 연결고리를 따라 탐색
• 연결고리 -> 포인터, 화물칸 -> 노드
• 원소를 중간에 삽입 / 삭제를 하기 위해 앞 뒤의 포인터만 변경하면 된다.
• 모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.

데이터에 접근하는 경우가 빈번하다면 Array !
삽입, 삭제가 빈번하다면 Linked List !

---

Linked List

1. Node 클래스 생성

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

2. Linked List 클래스 생성

class LinkedList:
    # head만 가지고 있으면 된다
    def __init__(self, data) :
        self.head = Node(data)

3. append
   head를 맨 끝 노드로 이동 후 새 노드를 생성해서 연결.
   맨 끝 노드는 while문으로 node의 next가 None일 때 까지.

class LinkedList:
    # head만 가지고 있으면 된다.
    def __init__(self, data) :
        self.head = Node(data)

    def append(self, data) :
        
        # head가 None일 때
        if self.head is None:
            # 노드를 생성해서 바로 붙여준다.
            self.head = Node(data)
            return

        # head가 None이 아닐때
        cur = self.head                     # cur 은 head를 가리킨다
        while cur.next is not None:         # 조건 : 다음노드가 없을때까지 반복
            cur = cur.next                  # cur 을 다음노드를 가리키게 한다.
            print("cur is ", cur.data)      
        cur.next = Node(data)               # 다음노드가없다면(맨끝노드) 
                                            # node를 생성해서 붙인다.

4. 노드 순회 출력

def print_all(self) :

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

5. 특정 index의 노드 가져오기

def get_node(self, index):

        node = self.head

        count = 0
        while count < index:
            node = node.next
            count += 1

        return node

6. 특정 index번째에 새로운 노드 추가

# index 번째에 새로운 노드추가
    def add_node(self, index, value):
        # 새로운 노드
        new_node = Node(value)

        # head 앞에다가 (맨 앞에) 노드를 추가하고싶을때
        if index == 0 :
            new_node.next = self.head   # 새로운 노드의 next에 head를 걸어놓고
            self.head = new_node        # head가 새로운 노드(맨앞) 을 가리키게
            return

        # index번째 노드
        node = self.get_node(index-1)        
        # index번째 노드의 다음거를 미리 저장
        next_node = node.next

        # node - new_node - next_node 형태로 새롭게 연결
        node.next = new_node
        new_node.next = next_node