옆집 스위프트: 1-4) 데이터 구조 - 연결 리스트(Linked List)

오늘은 스위프트로 연결리스트를 만들어봤다.

 

 

4. 연결 리스트(Linked List)

• 연결 리스트에 대하여
  • 노드: 연결리스트는 노드로 구성되며 각 노드는 아래에 2가지 구성 요소를 포함한다. 리스트에서 첫번째 노드는 헤드(head)라고 하고, 마지막 노드는 테일(tail)이라고 한다. 테일노드는 nil을 가리켜 리스트의 끝을 나타낸다.
    
    노드의 구성 요소:
    • 데이터: 노드가 보유하는 값 또는 데이터
    • 다음(Next): 리스트에서 다음 노드에 대한 참조 또는 포인터
  • 연결 리스트 유형
    • 단일 연결 리스트: 각 노드가 리스트의 다음 노드에만 참조 eg. 노드1 → 노드2 → 노드3 → nil
    • 이중 연결 리스트: 각 노드는 다음 노드와 이전 노드 모두에 대한 참조 eg. 노드1 ↔ 노드2 ↔ 노드3 → nil
    • 원형 연결 리스트: 테일 노드가 헤드를 다시 가리켜 원형구조를 이룸 eg. 노드1 → 노드2 → 노드3 → 노드1
  • 연결 리스트의 장단점
    • 장점:
      • 동적 크기: 연결리스트는 동적으로 늘어나거나 줄어들수있어서 배열보다 유연
      • 효율적인 삽입/삭제: 노드를 삽입하거나 삭제하는 것을 상수 시간에 수행할 수 있음(배열에서는 요소를 이동해야 할 수 있음)
      • 메모리 효율성: 연결 리스트는 포함된 노드에 대해서만 메모리 할당(배열은 연속된 메모리 블록이 필요)
    • 단점:
      • 무작위 접근: 요소에 접근하는데 선형시간이 걸리면 시작부터 순회해야함
      • 추가 메모리: 다음 노드에 대한 참조를 저장하기위해 추가메모리 필요
      • 캐시 지역성 부족: 노드가 메모리 전반에 흩어져 있을 수 있으므로 연결 리스트는 CPU 캐시를 효율적으로 활용 못할 수가 있음

// 스위프트에서 구현하는 연결 리스트~
class Node<T: Equatable> {
  var value: T
  var next: Node<T>?
    
  init(value: T) {
    self.value = value
  }
}

class LinkedList<T: Equatable> {
  var head: Node<T>?
    
  // 리스트 끝에 노드 추가
  func append(value: T) {
    let newNode = Node(value: value)
        
	  if head == nil {
      head = newNode
      return
    }
        
	  var currentNode = head
    while currentNode?.next != nil {
      currentNode = currentNode?.next
    }
        
    currentNode?.next = newNode
  }
    
  // 특정 위치에 노드 삽입
  func insert(value: T, at index: Int) {
    let newNode = Node(value: value)
        
    // 리스트가 비어있거나 인덱스가 0인 경우
    if head == nil || index == 0 {
      newNode.next = head
      head = newNode
      return
    }
        
    var currentNode = head
    var currentIndex = 0
        
	  // 삽입 위치 이전 노드 찾기
    while currentNode != nil && currentIndex < index - 1 {
        currentNode = currentNode?.next
        currentIndex += 1
    }
        
    // 인덱스가 리스트 범위 내에 있는지 확인
    if currentNode == nil {
      print("인덱스가 리스트 범위를 벗어났습니다.")
      return
    }
        
    // 새 노드를 현재 노드와 다음 노드 사이에 연결
    newNode.next = currentNode?.next
    currentNode?.next = newNode
  }
    
  // 특정 값을 가진 첫 번째 노드 삭제
  func delete(value: T) -> Bool {
    // 리스트가 비어있는 경우
    if head == nil {
      return false
    }
        
    // 삭제할 노드가 첫 번째 노드인 경우
    if head?.value == value {
      head = head?.next
      return true
    }
        
    // 삭제할 노드의 이전 노드 찾기
    var currentNode = head
    while currentNode?.next != nil && currentNode?.next?.value != value {
      currentNode = currentNode?.next
    }
        
    // 값을 찾지 못한 경우
    if currentNode?.next == nil {
      return false
	  }
        
    // 노드 삭제 (다음 노드를 건너뛰기)
    currentNode?.next = currentNode?.next?.next
    return true
  }
    
  // 인덱스로 노드 삭제
  func deleteAt(index: Int) -> Bool {
    // 리스트가 비어있는 경우
    if head == nil {
      return false
    }
        
    // 첫 번째 노드를 삭제하는 경우
    if index == 0 {
      head = head?.next
      return true
    }
        
    var currentNode = head
    var currentIndex = 0
        
    // 삭제할 노드의 이전 노드 찾기
    while currentNode != nil && currentIndex < index - 1 {
      currentNode = currentNode?.next
      currentIndex += 1
    }
        
    // 인덱스가 리스트 범위를 벗어난 경우
    if currentNode == nil || currentNode?.next == nil {
      return false
    }
        
    // 노드 삭제
    currentNode?.next = currentNode?.next?.next
    return true
  }
    
  // 값 검색 (있으면 true, 없으면 false 반환)
  func search(value: T) -> Bool {
    var currentNode = head
        
    while currentNode != nil {
      if currentNode!.value == value {
        return true
      }
      currentNode = currentNode?.next
    }
        
    return false
  }
    
  // 값의 인덱스 찾기 (없으면 -1 반환)
  func indexOf(value: T) -> Int {
    var currentNode = head
    var index = 0
        
    while currentNode != nil {
      if currentNode!.value == value {
        return index
      }
      currentNode = currentNode?.next
      index += 1
    }
        
    return -1
  }
    
  // 모든 노드의 값 출력
  func printList() {
    var currentNode = head
    var values: [T] = []
        
    while currentNode != nil {
      values.append(currentNode!.value)
      currentNode = currentNode?.next
    }
        
    print(values)
  }
}

// 사용 예시

// 정수형 연결 리스트 생성
let intList = LinkedList<Int>()

// 1. 노드 추가(append)
intList.append(value: 10)
intList.append(value: 20)
intList.append(value: 30)
print("리스트 초기 상태:")
intList.printList() // 출력: [10, 20, 30]

// 2. 특정 위치에 삽입(insert)
intList.insert(value: 15, at: 1) // 인덱스 1(두 번째 위치)에 15 삽입
print("인덱스 1에 15 삽입 후:")
intList.printList() // 출력: [10, 15, 20, 30]

intList.insert(value: 5, at: 0) // 맨 앞에 삽입
print("맨 앞에 5 삽입 후:")
intList.printList() // 출력: [5, 10, 15, 20, 30]

intList.insert(value: 35, at: 5) // 맨 뒤에 삽입
print("맨 뒤에 35 삽입 후:")
intList.printList() // 출력: [5, 10, 15, 20, 30, 35]

// 범위를 벗어난 인덱스 테스트
intList.insert(value: 40, at: 10) // 출력: "인덱스가 리스트 범위를 벗어났습니다."

// 3. 검색(search)
let found20 = intList.search(value: 20)
print("20이 리스트에 있나요? \\(found20)") // 출력: true

let found25 = intList.search(value: 25)
print("25가 리스트에 있나요? \\(found25)") // 출력: false

// 4. 인덱스 찾기(indexOf)
let indexOf15 = intList.indexOf(value: 15)
print("15의 인덱스: \\(indexOf15)") // 출력: 2

let indexOf40 = intList.indexOf(value: 40)
print("40의 인덱스: \\(indexOf40)") // 출력: -1 (존재하지 않음)

// 5. 값으로 삭제(delete)
let deleted20 = intList.delete(value: 20)
print("20 삭제 성공? \\(deleted20)")
print("20 삭제 후:")
intList.printList() // 출력: [5, 10, 15, 30, 35]

let deleted40 = intList.delete(value: 40)
print("40 삭제 성공? \\(deleted40)") // 출력: false (존재하지 않음)

// 6. 인덱스로 삭제(deleteAt)
let deletedAtZero = intList.deleteAt(index: 0)
print("인덱스 0 삭제 성공? \\(deletedAtZero)")
print("인덱스 0 삭제 후:")
intList.printList() // 출력: [10, 15, 30, 35]

let deletedAt5 = intList.deleteAt(index: 5)
print("인덱스 5 삭제 성공? \\(deletedAt5)") // 출력: false (범위 초과)

// 7. 문자열 연결 리스트 테스트
let stringList = LinkedList<String>()
stringList.append(value: "안녕")
stringList.append(value: "하세요")
stringList.append(value: "스위프트")
print("\\n문자열 리스트:")
stringList.printList() // 출력: ["안녕", "하세요", "스위프트"]

// 문자열 검색
let foundSwift = stringList.search(value: "스위프트")
print("'스위프트'가 리스트에 있나요? \\(foundSwift)") // 출력: true

// 중간 삽입
stringList.insert(value: "반갑습니다", at: 1)
print("'반갑습니다' 삽입 후:")
stringList.printList() // 출력: ["안녕", "반갑습니다", "하세요", "스위프트"]

// 삭제
stringList.delete(value: "하세요")
print("'하세요' 삭제 후:")
stringList.printList() // 출력: ["안녕", "반갑습니다", "스위프트"]