Chapter 3: 동적 자료 구조

내용 정리

배열의 한계

• 생성 시 크기와 메모리 레이아웃이 고정된다

  • 확장하고자 하면, 새로 큰 배열을 만들고 기존 배열에서 데이터를 복사해야 한다

• 현대적 프로그래밍 언어들은 동적 “배열” 을 제공하지만, 실체는 정적 배열이라 다른 자료 구조를 감싼 wrapper로, 배열의 끝을 지나 원소를 추구할 때 메모리를 늘려야하는 것은 여전하다

• array doubling 같은 전략으로, 배열 크기가 확장될 때마다 그 크기를 두 배로 키우는 방식을 채택할 수 있지만, 잠재적 메모리 낭비는 여전하다

• 그러므로 배열의 한계를 극복하기 위해 새로운 데이터를 추가할 때 더 커질 수 있는 동적 자료 구조를 사용해야 한다!

포인터와 참조

• pointer는 동적 자료구조의 필수 재료로, 주소를 공유함으로써 복사본을 만들 필요가 없게 한다

• C나 C++ 같은 저수준 언어는 원시 pointer를 제공하고, 이 포인터에 저장된 메모리 위치에 직접 접근할 수 있다

• Python 과 같은 언어는 reference 를 사용해 다른 변수를 참조할 수 있다

연결 리스트

• 동적 자료 구조의 간단한 예로, pointer로 연결된 node의 사슬로 구성된다

• linked list의 node는 두 부분으로 이루어진 복합 자료 구조로, 아래와 같다

  LinkedListNode {
   Type: value
   LinkedListNode: next
  }

  • 첫 번째 부분: 어떤 타입의 값이든 포함할 수 있는 값

  • 두 번째 부분: list의 다음 node를 가리키는 Pointer

• 메모리 사용

  • 각 원소를 저장하기 위해 value와 pointer를 저장해야 하므로, 같은 항목을 저장할 때 배열보다 더 많은 메모리를 사용한다

  • but, pointer가 제공하는 유연성을 위해 메모리 사용량 증가를 감수할 가치가 있는 경우가 자주 있다

• 장점

  • pointer로만 연결되어 있기 때문에, list 전체를 하나의 연속적인 메모리 블록에 유지해야만 하는 제약이 없다

• 단점

  • 배열보다 계산 부가 비용이 높다

    • 배열의 원소에 접근할 때 offset을 계산하여 바로 메모리에서 주소를 찾을 수 있는 방면, linked list는 원하는 원소에 도달할 때까지 앞에서부터 반복하여 조회해야 한다

    • 긴 목록의 경우 접근에 대한 비용이 커지게 된다

연결 리스트에 대한 연산

• 삽입

  • 새 node의 위치를 알고 있으면, 이전 node의 next pointer가 새 node를 가리키도록 갱신하고, 새 node의 next pointer를 올바른 node로 지정하면 된다

  • linked list의 시작, 중간, 끝에 모두 새로운 node 를 추가할 수 있다

• 제거

  • 배열에서는 나머지 원소들을 모두 앞으로 한 칸씩 이동해야하기 때문에 비용이 많이 드는 반면, linked list는 pointer 만 바꿔주면 된다

• e.g.

  class Node:
      def __init__(self, value):
          self.value = value
          self.next = None
  
  class LinkedList:
      def __init__(self):
          self.head = None
  
      def insert(self, value):
          new_node = Node(value)
          if not self.head:
              self.head = new_node
              return
          current = self.head
          while current.next:
              current = current.next
          current.next = new_node
  
      def delete(self, value):
          if not self.head:
              return
          if self.head.value == value:
              self.head = self.head.next
              return
          current = self.head
          while current.next and current.next.value != value:
              current = current.next
          if current.next:
              current.next = current.next.next
  
      def display(self):
          current = self.head
          result = []
          while current:
              result.append(current.value)
              current = current.next
          return result

이중 연결 리스트

• 구조는 아래와 같다

  DoublyLinkedListNode {
   Type: value
   DoublyLinkedListNode: next
   DoublyLinkedListNode: previous
  }
• Linked List vs Doubly Linked List

  • 임의의 node 를 가리키는 pointer가 주어졌을 때, 그 node 의 이전 node에 접근하고 싶다면 linked list에서는 처음부터 목록을 순회해야 하지만, doubly linked list에서는 임의의 node로부터 직접 이전 node에 접근할 수 있다

생각

개발을 처음 배울때 인상깊게 생각했던 linked list에 대해 정리해볼 수 있는 챕터였다