[Swift/자료구조] 3. 연결리스트(LinkedList)

안녕하세요

이번시간에는 연결리스트에 대해 알아보고

스위프트로 구현해보도록 하겠습니다

---

 

연결리스트란? 

연결리스트는 자료구조 중 하나 입니다.

• 데이터를 노드라 불리는 단위로 나눔
• 각 노드는 데이터, 다음노드를 가리키는 포인터로 이루어진 선형 데이터 구조

단방향 연결 리스트

 

연결리스트와 배열의 차이점

• 저장방식: 배열은 순차적으로 메모리공간에 할당되고, 연결리스트는 불연속적으로 할당됨
• 삽입 및 삭제 연산: 배열은 특정 인덱스에 삽입, 삭제할 경우 해당 위치 이후의 모든 원소를 이동시켜야 함
  반면, 연결리스트는 앞뒤 노드의 포인터를 조정하면 되므로 이동 필요 X
• 접근: 배열은 인덱스를 통한 접근이 빠르다. 하지만 연결리스트는 순차적으로 탐색해야 하기 때문에 속도가 느릴 수 있음 

즉, 배열은 데이터 접근이 빠름

연결리스트는 데이터 삽입 및 삭제 속도가 빠르다

 

단방향 연결 리스트 구현 

일단 노드라고 불리는 단위로 나눠야한다. 노드를 짜주자

 

노드

class Node<T: Equatable> {
    var value: T
    var next: Node<T>?

    init(_ value: T, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

 

그 다음 연결리스트를 구현해보자

• head: 연결리스트의 시작 노드 (탐색을 위해 무엇이 시작인지 알고 있어야 함)
• tail: 연결리스트의 마지막 노드
  (연결리스트의 마지막 요소를 추가하는 작업을 쉽게하도록 tail을 선언 안 한다면, node.next가 안나올 때 까지 반복해서 구현할 수 도 있다, tail이 있다면 tail뒤의 next에만 넣어주면 된다.)
• add: 마지막에 요소 추가
• search: 데이터로 노드 탐색
• insert: 중간에 삽입 (인덱스처럼) 

class LinkedList<T: Equatable> {
    
    var head: Node<T>?
    var tail: Node<T>?
    
    func add(node: Node<T>) {
       if head == nil {
           head = node
           tail = node
           return
       }
       
       tail?.next = node
       tail = node
   }
    
    func search(_ value: T) -> Node<T>? {
        var now = head
        while now?.value != value && now != nil {
            now = now?.next
        }
        return now
    }
    
    func insert(node: Node<T>, at index: Int) {
        
        if head == nil {
            head = node
            tail = node
            return
        }
        var prevNode = head
        for _ in 0..<(index - 1) {
            if prevNode?.next == nil { break }
            prevNode = prevNode?.next
        }
        
        let nextNode = prevNode?.next
        prevNode?.next = node
        prevNode?.next?.next = nextNode
    }
}

 

대부분 문제에 맞게 메서드를 짜야하거나 코드를 짜야하기 때문에, 코드 자체를 외우기보다는 동작방식을 외우는 것이 좋을 듯 하다.