[swift] 배열과 연결리스트

개린이가 쓴 글이므로 오류가 있을 수 있음을 미리 알려드립니다 🐹 (꾸벅)

배열과 연결리스트 ! 둘 다 데이터를 나열한다.
그럼 그 차이점은 무엇일까?

✔️ 배열

-> 우리가 가장 흔히 잘 알고있는 선형 자료구조이다.

1. 배열은 논리적 순서에 따라 순차적으로 데이터를 입력하며, 입력 순서에 따라 물리적 주소 또한 순차적으로 이루어져있다.
2. 인덱스 값으로 원하는 데이터에 접근 할 수 있기 때문에 접근속도가 매우 빠르다.
3. 삽입 / 삭제는 좋지 않다. 중간 값을 삭제한다면 뒤에 있는 값들의 물리적 주소 모두를 앞으로 당겨와야한다.

✔️ 연결리스트

-> 값을 가지고 있으며, 다음으로 올 값의 참조정보를 가지고 있습니다.
-> c의 포인터를 생각하면 쉬움

1. 배열과 달리 물리적인 순서가 순차적이지 않음.
2. 한번에 원하는 데이터에 접근을 할 수가 없음. 이전의 데이터 값이 가리키는 곳을 따라가야함.
3. 이전 혹은 다음 값의 위치를 가지고 있다.
4. 데이터를 넣거나 뺄 때 물리적인 공간의 이동 없이 참조 값만 변경해주면 되기 때문에 배열에 비해 훨씬 좋다.

🐹 연결리스트 swift로 구현해보기

-> 단순 연결 리스트를 구현해둔 코드입니다.
-> 이것저것 참고하여 작성했는데 틀린 부분이 있을 수 있습니다.
-> 혹시 잘못된 부분이 있다면 댓글 남겨주세요 😭

연결 리스트를 위한 노드 구현

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

기본 구조

class LinkedList<T> {
    var head: Node<T>?
    var tail: Node<T>?
    
    init (head: Node<T>?) {
        self.head = head
        self.tail = head
    }
}

속성 부분

1. isEmpty : head가 있는지 없는지
2. first : head return
3. last : tail return
4. count : node의 개수

var isEmpty: Bool {
        return head == nil
}
    
var first: Node<T>? {
        return head
}
    
var last: Node<T>? {
    guard var node = head else {
        return nil
    }
        
    while let next = node.next {
        node = next
    }
    return node
}
    
var count: Int {
    guard var node = head else {
        return 0
    }
        
    var count = 1
    while let next = node.next {
        node = next
        count += 1
    }
    return count
}

메소드 구현

1. node(at index: Int) -> Node?
   몇 번 째에 어떤 Node가 있는지
2. append(_ newNode: Node)
   가장 뒤에 node 추가
3. insert(_ newNode: Node, at index: Int)
   리스트 중간에 node 추가
4. removeAll()
   전체 리스트 삭제
5. remove(at index: Int) -> T?
   해당하는 인덱스의 node 삭제 -> 그 node의 value 값 return
6. removeLast() -> T?
   마지막 node 삭제

    func node(at index: Int) -> Node<T>? {
        if index == 0 {
            return head
        } else {
            var node = head!.next
            for _ in 1..<index {
                node = node?.next
                if node == nil {
                    break
                }
            }
            
            return node
        }
    }
    
    
    func append(_ newNode: Node<T>) {
        if let tail = self.tail {
            tail.next = newNode
            self.tail = tail.next
        } else {
            self.head = newNode
            self.tail = newNode
        }
    }
    
    func insert(_ newNode: Node<T>, at index: Int) {
        if self.head == nil {
            self.head = newNode
            self.tail = newNode
            return
        }
        guard let frontNode = node(at: index-1) else {
            self.tail?.next = newNode
            self.tail = newNode
            return
        }
        guard let nextNode = frontNode.next else {
            frontNode.next = newNode
            self.tail = newNode
            return
        }
        newNode.next = nextNode
        frontNode.next = newNode
    }
    
    func removeAll() {
        head = nil
    }
    
    func remove(at index: Int) -> T? {
        guard let frontNode = node(at: index-1) else { // 인덱스 앞 노드를 찾을 수 없다면 -> nil 반환
            return nil
        }
        
        guard let removeNode = frontNode.next else { // 인덱스 앞 노드가 마지막 노드라면 -> nil 반환
            return nil
        }
        
        guard let nextNode = removeNode.next else { // index가 마지막 위치라면? -> tail에 index 이전 노드 저장
            frontNode.next = nil
            self.tail = frontNode
            return removeNode.value
        }
        
        frontNode.next = nextNode // index - 1 가 마지막 아닐 때 (일반적인 경우)
        
        return removeNode.value
    }
    
    public func removeLast() -> T? {
        return remove(at: self.count - 1)
    }

✔️ 실습 해보기

var myLinkedList = LinkedList<Int>(head: Node(value: 3, next: nil))
myLinkedList.append(Node(value: 4, next: nil))
myLinkedList.append(Node(value: 8, next: nil))


print(myLinkedList.count)
print(myLinkedList.remove(at: 2)!)
print(myLinkedList.count)
myLinkedList.append(Node(value: 2, next: nil))
print(myLinkedList.isEmpty)
print(myLinkedList.node(at: 1)!.value)
myLinkedList.insert(Node(value: 9, next: nil), at: 1)
print(myLinkedList.last!.value)

for i in 0..<myLinkedList.count {
    print(myLinkedList.node(at: i)!.value, terminator : " ")
    
}
print("")
print(myLinkedList.removeLast()!)

출력 결과 !