[Tip] Swift - 딕셔너리로 링크드 리스트 구현하기

카카오 2021 채용연계형 인턴십 [표 편집] 문제를 풀다가 링크드 리스트를 구현 해야하는 일이 있었는데, 구조체를 정의하고 인스턴스를 만들지 않아도 딕셔너리로 아주 비슷하고 간단하게 링크드 리스트를 구현하는 방법이다.

🍎 양방향 링크드 리스트를 만들기

• 먼저 어떤 모양인지 알아보자!

  // 딕셔너리 컬렉션으로 링크드리스트 구현
    var linkedList: [Int: (Int, Int)] = [:] // 인덱스 : (prev, next) 형태.

• Doubly Linked List을 만들기 위한 작업

  // 순차적으로 연결해주는 작업
  for i in 1..<n {
    linkedList[i] = (i - 1, i + 1)
  }
  // DLL의 특징인 마지막 노드가 첫번째 노드와 연결 되어있다는것을 구현을 위한 처음과 끝 노드 연결
  linkedList[0] = (n-1, 1) 
  linkedList[n-1] = (n-2, 0)

• 특정 노드를 삭제하는 경우

  let preNode = linkedList[currentNode]!.0
  let nxtNode = linkedList[currentNode]!.1
  linkedList[preNode]!.1 = nxtNode
  linkedList[nxtNode]!.0 = preNode
  linkedList[currentNode] = nil

• X만큼 노드 이동하기

  // 앞으로 이동
  for _ in 0..<X {
     currentRow = linkedList[currentRow]!.0
  }
  // 뒤로 이동
  for _ in 0..<X {
     currentRow = linkedList[currentRow]!.1
  }