Dynamic Array vs LinkedList In Dart

Uno·2023년 11월 13일

dart

목록 보기

5/7

개요

작성 동기

매일 사용하는 Dart 언어로, Dynamic Array 와 LinkList 를 직접 구현해보고 싶었다.
예상 독자

Dart 언어를 사용한 초보자.
기대 효과
- Dynamic Array 가 Default 설정일 뿐, 변경 가능하다는 사실을 알게된다.
- LinkedList 를 Dart 언어로 직접 구현할 수 있게 된다.
요약

Dynamic Array 는 조회에 강하고 추가에 약하다. LinkedList 는 추가에 강하고 조회에 약하다. 이유는 메모리 저장 방식이 다르기 때문이다.

Dynamic Array(동적 배열)

연속된 메모리 공간을 차지한다. 그러므로, 인덱스를 통한 데이터 접근이 가능하다. 이를 Random Access 라고 부른다.
메모리 공간을 차지하는데, 고정된 크기만큼 차지한다. 그래서, 고정된 크기를 벗어나는 크기를 확보하려고 하면, 기존 메모리 공간을 버리고 더 큰 메모리 공간을 차지해야한다. 이 때, 2 배 크기를 확보하는 Doubling 이라는 기법을 활용한다.

정리하면, 잦은 데이터 조회에는 O(1) 이므로 강점을 가진다. 데이터 추가가 고정된 크기를 넘어서는 순간 O(n) 이 발생한다는 약점이 있다.

예시코드

아래 코드는 일부러 Uncaught Error 를 발생시켰다. 고정된 크기의 배열인 경우, 추가적인 크기에 대한 대응 코드가 필요하다. 만약 정상적으로 동작시키고 싶다면 첫 번째 줄에 있는 growable 파라미터를 true 로 수정하면 된다.

void main() {
  // 고정된 크기의 리스트 생성
  List<int> fixedSizeArray = List.filled(
    3, 0,
    growable: false, // <--- 이것을 true 로 수정하면 된다.
  );
  // 초기 상태 출력
  print("초기 리스트: $fixedSizeArray");

  // 데이터 추가
  fixedSizeArray[0] = 1;
  fixedSizeArray[1] = 2;
  fixedSizeArray[2] = 3;

  // 데이터 변경 후 상태 출력
  print("변경된 리스트: $fixedSizeArray");

  // 리스트의 현재 참조 저장
  var oldReference = fixedSizeArray;

  // 리스트 크기를 초과하여 데이터 추가
  // 여기서 Uncaught Error: Unsupported. operation: add" 에러 발생
  // 에러 발생을 시키기 싫다면 "growable" 을 `true` 로 변경할 것
  fixedSizeArray.add(4); 

  // 데이터 추가 후 상태 출력
  print("확장된 리스트: $fixedSizeArray");
}

에러없이, 끝까지 출력했다면, 다음과 같은 결과가 출력된다.

초기 리스트: [0, 0, 0]
변경된 리스트: [1, 2, 3]
확장된 리스트: [1, 2, 3, 4]

LinkedList(연결리스트)

연결 리스트는 각 데이터가 메모리구조상 연속적으로 저장되지 않는다.
그 대신, 새로운 자료구조인 Node 를 구성하여 데이터를 저장한다. Node 는 데이터와 다음 Node의 주소를 가지고 있는 자료구조이다.
그래서, 데이터를 조회하면, 첫 번째 Node 에 접근하여 데이터를 확인하고 만약 원하는 데이터가 아니면 다음 노드 메모리주소를 통해 이동하여 다시 조회한다. 이 반복을 원하는 데이터를 찾을 때까지 반복하다. 그러므로 시간복잡도는 O(n) 이다.
데이터를 추가할 시, 아무리 데이터를 추가하더라도, 마지막 노드에 메모리 주소만 할당하면 된다. 그러므로 시간복잡도는 O(1) 이다.

정리하면, 데이터 추가에는 제약이 없으므로 O(1) 인 강점을 가진다. 데이터 조회에는 모든 데이터를 찾아야하므로 O(n) 이라는 약점이 있다.

예시코드

LinkedList 는 설명에서도 있든 Node 라는 자료구조를 먼저 만들어야한다.

class Node<T> {
  T data;
  Node<T>? next;
  Node(this.data);
}

<T> 는 제네릭 문법이다. “타입을 동적으로 전달받겠다.” 라는 뜻이다.

LinkedList 를 정의한다.

// LinkedList 정의
class LinkedList<T> {
  // 가장 첫 번째 노드를 선언한다.
  Node<T>? head;
  
  /// 데이터 추가
  bool add(T data) {
    // 최초로 값을 정의하는 순간이라면, head 에 저장한다.
    if (head == null) {
      head = Node(data);
      return (head != null);
    }
    
    
    Node<T> current = head!;
    // 마지막 노드까지 이동한다.
    while (current.next != null) {
      current = current.next!;
    }
    // 마지막 노드에 이동했다면, next 에 Node 를 저장한다.
    current.next = Node(data);
    return (current.next != null);
  }
  
  /// 데이터 출력
  void printList() {
    Node<T>? current = head;
    while (current != null) {
      print(current.data);
      current = current.next;
    }
  }
}

그리고 LinkedList 의 실행코드이다.

void main() {
  // 연결 리스트 생성 및 데이터 추가
  LinkedList<int> linkedList = LinkedList<int>();
  linkedList.add(1);
  linkedList.add(2);
  linkedList.add(3);

  // 연결 리스트 출력
  linkedList.printList(); // 1 2 3
}