배열 VS 연결 리스트

	배열	연결 리스트
장점	인덱스 값을 알고 있다면 빠르게 접근 가능	데이터 삽입, 삭제가 빠름
단점	크기가 고정, 중간 데이터 변경 시 느림	데이터 및 다음 노드를 저장해 저장 공간 효율이 낮음, 검색 속도가 느림

단방향 연결 리스트

Node

class Node<T> {
    var data: T?
    var next: Node?
    
    init(data: T?, next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

LinkedList

class LinkedList<T: Equatable> {
    var head: Node<T>?
    var numOfData: Int
    
    init() {
        self.head = nil
        self.numOfData = 0
    }
}

데이터가 제네릭이므로 Equatable 프로토콜을 채택하여 데이터 비교가 가능하게 함

append

func append(data: T) {
        let newNode = Node(data: data)
        
        if head == nil {
            head = newNode
        } else {
            var p = head
            while p?.next != nil {
                p = p?.next
            }
            p?.next = newNode
        }
        numOfData += 1
    }

insert

func insert(data: T, at index: Int) {
        let newNode = Node(data: data)
        
        if index > numOfData {
            print("Out of index")
            return
        }
        
        var p = head
        for _ in 0..<index - 1 {
            p = p?.next
        }
        newNode.next = p?.next
        p?.next = newNode
        numOfData += 1
    }

removeLast

func removeLast() {
        
        if numOfData == 0 {
            print("There's no data")
            return
        } else if numOfData == 1 {
            head = nil
            numOfData -= 1
        } else {
            var p = head
            
            while p?.next?.next != nil {
                p = p?.next
            }
            p?.next = nil
            numOfData -= 1
        }
    }

remove

func remove(at index: Int) {
        if numOfData == 0 {
            print("There's no data")
            return
        } else {
            if index > numOfData - 1 {
                print("Out of index")
                return
            } else {
                if index == 0 {
                    head = head?.next
                } else {
                    var p = head
                    for _ in 0..<index - 1 {
                        p = p?.next
                    }
                    p?.next = p?.next?.next
                }
                numOfData -= 1
            }
        }
    }

search

 func searchNode(data: T) -> Node<T>? {
        
        var p = head
        while p != nil {
            if p?.data == data {
                return p
            }
            p = p?.next
        }
        return nil
    }

Node를 Class로 구현하였기에 해당 클래스의 Reference Count가 0이 되면 ARC에 의해 자동으로 메모리에서 해제되므로 노드 삭제 시 메모리 해제 코드를 작성하지 않아도 된다.