[Swift] LinkedList

What is LinkedList? 

• LinkedList 는 Element 간의 연결(Link) 를 통해서 리스트를 구현한 자료구조 이다. 

 

Why LinkedList? 

• 연결리스트의 효율성은 배열과 비교가 가장 많이 되는데 이유는 둘다 리스트 형태 를 구현할수 있다는것이다.
• 두가지의 자료구조의 특징을 이해하고 상황에 따라 적절히 사용하기 위해서 각각의 시간 복잡도를 데이터 탐색, 추가, 삭제 3가지로 나누어서 살펴봤다. 

 

데이터 탐색

연결리스트:

특정 데이터를 찾기 위해서 연결되어 있는 요소들을 처음부터 순차적으로 탐색해야하기 때문에 O(n) 의 시간 복잡도를 갖는다. 

 

배열:

배열의 요소는 특정 인덱스를 가지고 있기 이를 통해서  빠르게 특정 데이터를 찾을수 있다. O(1) 의 시간복잡도를 갖는다. 

 

​

데이터 추가 & 삭제

연결리스트:

데이터를 추가 및 삭제 하는 행위 자체의 시간 복잡도는 O(1) 이지만 특정 위치를 탐색하는데 O(n) 의 시간 복잡도를 갖는다. 

이때 추가하려는 위치가 리스트의 맨처음 혹은 맨끝일경우 O(1) 의 시간 복잡도를 갖는다. 

 

배열:

배열의 경우 추가 및 삭제 하려는 데이터의 위치가 맨끝이 아닐경우 요소들의 위치가 한칸씩 밀림으로 O(n) 의 시간복잡도를 가진다. 

하지만  맨 뒤일경우 O(1) 의 시간복잡도를 갖는다. 

​

정리

배열: 데이터의 접근과 탐색의 비중이 높게 사용되는 상황에 사용하는게 좋다. 
연결리스트: 데이터의 추가, 삭제의 비중이 높게 사용되는 상황에 사용하는게 좋다. 

 

Swift 를 사용한 LinkedList 구현 

Node

class Node {
  var next: Node?
  let data: Int
  
  init (next: Node?, data: Int){
    self.next = next
    self.data = data
  }
}

• LikedList 에 사용될 요소, Node 를 구현한다. 
• 각 Node 는 다음 Node 를 가르키는 next 변수와 데이터를 담는 data 상수를 갖는다. 

LinkedList

class LinkedList {
  //1
  var head: Node?

  //2
  var tail: Node? {
    var cursor = head
    while cursor?.next != nil {
      cursor = cursor?.next
    }
    return cursor
  }
  
  //3
  var count: Int {
    guard var cursor = head else {return 0}
    var count = 1
    while cursor.next != nil {
      cursor = cursor.next!
      count += 1
    }
    return count
  }
}

1. 현재 List 가 가르키고 있는 첫 Node 를 나타내는 head 이다. 
2. 현재 List 의 끝에있는 Node 를 가르킨다. 
3. 현재 List 의 Node 의 총 개수를 가진다. 

 

Append

 func appendNode(data: Int) {
    
    if head == nil {
      self.head = Node(next: nil, data: data)
      return
    }else {
      tail?.next = Node(next: nil, data: data)
      return
    }
  }

 

InsertAt

  func insertAt(index: Int, data: Int){
    var curr = head
    var prev: Node?
    // head 가 없을시
    if curr == nil {
      head = Node(next: nil, data: data)
      return
    }
    
    //index 가 리스트의 범위를 넘어 갈때
    if count <= index {
      tail?.next = Node(next: nil, data: data)
      return
    }
    
    //다음 노드로 이동
    for _ in 0..<index {
      prev = curr
      curr = curr?.next
    }
    
    //0 번째 요소에 추가하려고 할떄
    if prev == nil {
      head = Node(next: curr, data: data)
      //그외
    }else {
      prev?.next = Node(next: curr, data: data)
    }
    
  }

 

 

RemoveLast

  //To delete the last node of a linked list, find the second last node and make the next pointer of that node null.
  func deleteLast() {
    
    if head == nil {return}
    
    if head?.next == nil {
      head = nil
      return
    }
    
    var cursor = head
    //Cusor 의 다음 node 가 아무것도 없다면, 즉 현재 head 의 next 에 더이상 새로운 node 가 없다면 return
    while cursor?.next?.next != nil {
      //head 뒤에 node 가 더 있다면 cursor 를 다음 node 로 만든다.
      cursor = cursor?.next
    }
    cursor?.next = nil
  }

 

RemoveAt

func deleteAt(index: Int) {
    var curr = head
    var prev: Node?
    
    if head == nil {return}
    

    for _ in 0..<index {
      if curr?.next == nil {break}
      prev = curr
      curr = curr?.next
    }
    
    //주어진 Index 가 0 일떄
    if prev == nil {
      head = head?.next
      return
    }
    
    //다음 노드가 없을때, 즉 마지막 요소일때
    if curr?.next == nil {
      prev?.next = nil
      return
    }
    
    //그 이외의 케이스
    prev?.next = curr?.next
    curr?.next = nil

  }