[swift] Linked List 정리 (1)

시간 복잡도에 대한 내용은 자세히 다루지는 않을 예정이다. 

본 글은 오로지 Linked List에 대한 내용만 기술할 것이다. 혼자 노트정리 한다고 생각하고 정리해 나갈 것이다. 

시각 자료등은 유데미의 스위프트로 공부하는 데아터 구조를 참조하자. 직접 그려 넣고 싶지만 시간이 많이 걸려 하진 않을 것임. 

 

먼저 링크드 리스트가 뭔지부터 알기 전에 배열의 특성을 살펴보자. 

 

배열을 하나 만들었다고 가정하고 맨 앞에 요소를 하나 추가한다고 해보자. 그러면 시간은 얼마나 걸릴까? 답은 O(n)이다. 

맨 앞에 요소를 추가하려면 먼저 있는 요소들을 한칸씩 밀어야 하기 때문이다. 만약 요소 1개당 1ms가 걸린다고 가정하고 요소가 백만개가 있다고 쳐보면 1000000ms -> 약 16.7분 정도가 걸린다. 너무 느려터지지 않은가? 이를 해결하기 위해서 링크드 리스트라는 개념을 사용한다. 

 

결론 부터 말하면 링크드 리스트를 이용해서 위와 똑같은 기능을 구현했을때 시간 복잡도는 O(1)이다. 어떻게 이렇게 될 수 있는지 알아보자. 

 

먼저 리스트의 코드 부분을 구현해보면 아래와 같다. 

 

class Node {
  var value: Int
  var next: Node?

  init(_ value: Int) {
    self.value = value
  }
}

class LinkedList {
  var head: Node?

  func insertAtFront(_ value: Int) {
    let newNode = Node(value)
    newNode.next = head
    head = newNode
  }
}

 

Node라는 것은 통상적으로 데이터 부분와 포인터(가르킬 부분 혹은 가르킴 당하는 부분)을 가지고 있다. 

 

노드 구성 요소 설명.

 

data: 이 필드에는 노드에 저장된 데이터 또는 값이 저장된다.
link(next): 이 필드는 목록의 다음 노드에 대한 참조 또는 포인터이다. 쉽게 말해 각 노드들의 연결부분이라 생각하면 된다. 

 

맨 처음 나오는 Node를 head(머리)라 하고 끝 부분을 tail(꼬리)이라 한다. 그리고 tail부분은 link(next)부분을 항상 nil 처리 한다. 왜냐면 tail이 마지막이니 더 이상 가르킬 노드가 없기 때문이다. 그래서 Node 클래스를 정의할때 Node부분을 옵셔널 처리해서 (?붙이기) 선택사항을 만들어 주는 것이다. 

 

맨 앞의 배열에 요소를 넣는 것 처럼 구현하면 위에 코드와 같아진다. 그림으로 보면 

 

새로 추가하지는 않은 평범한 리스트

 

저 해드와 3이라는 데이터를 가진 노드 사이에 새로운 노드를 추가하면 된다. 이때 시간 복잡도는 위에서 말한 것 처럼 O(1)이 되는데 그 이유는 하나의 노드만 생성한 후 head부분의 연결 고리만 바꿔주면 되는 일이기 때문이다. 그러면 배열 처럼 모든 부분의 요소를 건드릴 필요가 없어지기 때문에 아무리 많은 요소가 있어도 아주 빠르게 끝낼 수 있다. 

 

다음엔 뒤에  요소를 집어 넣는 것을 정리해보겠다.