[Swift] The Swift Arcade Data Structures and AlgorithmsBootcamp - Linked List

배열 맨 앞에 요소를 넣으려고 하면 배열 전체를 복사해야하기 때문에 O(n) 임

배열은 공간을 차지한다

그리고 배열을 생성할 때마다 크기를 지정해야 하기도 한다

그래서 공간을 모두 차지하지 않는다면 공간 낭비이다

 

연결리스트는 요소를 추가하는데에 매우 빠르며 미리 크기를 지정할 필요 없이 축소 확장이 용이하다

 

---

기본적인 노드 구현

// Node는 data와 자신의 다음에 연결될 노드의 정보를 가지고 있다
// 마지막 노드는 다음 노드가 없으므로 nil이 와야함
class Node {
    var data: Int
    var next: Node?
    
    init(_ data: Int, _ next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

let node3 = Node(3)
let node2 = Node(2, node3)
let node1 = Node(1, node2)

func printLinkedList() {
    if head == nil { return }

    var result = [Int]()
    var node = head
    result.append(node!.data)

    while node?.next != nil {
        result.append(node!.next!.data)
        node = node?.next
    }

    print(result)
}

 

노드를 하나하나 만들며 연결하는 방법 말고

LinkedList 라는 클래스를 만들어서 더 쉽게 연결리스트를 만들어보자

 

---

Linked List

class LinkedList {
    private var head: Node?
}

연결리스트 클래스는 기본적으로 nil 일 수 있는 head를 가지고 있다.

리스트의 모든 것은 head로 부터 시작되기 때문

 

클래스 내부에 

 

- addFront / getFirst / addBack / getLast

- insert

- deleteFirst / deleteLast / delete

- isEmpty / clear

 

메서드를 만들었다

---

 

addFront

func addFront(_ data: Int) {

    let newNode = Node(data)
    newNode.next = head
    head = newNode
    
}

 

getFirst

func getFirst() -> Int? {

    if head == nil {
        return nil
    }
    return head!.data
    
}

addBack

func addBack(_ data: Int) {

    let newNode = Node(data)

    if head == nil {
        head = newNode
        return
    }

    var node = head!
    while node.next != nil {
        node = node.next!
    }

    node.next = newNode
    
}

getLast

func getLast() -> Int? {

    if head == nil {
        return nil
    }

    var node = head!
    while node.next != nil {
        node = node.next!
    }
    return node.data
    
}

---

insert

func insert(position: Int, data: Int) {

    if position == 0 {
        addFront(data)
        return
    }

    let newNode = Node(data)
    var currentNode = head
    for _ in 0 ..< position - 1 {
        currentNode = currentNode?.next!
    }
    newNode.next = currentNode?.next!
    currentNode?.next = newNode
    
}

---

deleteFirst

func deleteFirst() {
    head = head?.next
}

deleteLast

func deleteLast() {

    var prevNode: Node?
    var currentNode = head
    while currentNode?.next != nil {
        prevNode = currentNode
        currentNode = currentNode?.next
    }
    prevNode?.next = nil

}

delete

func delete(at position: Int) {

    if position == 0 {
        deleteFirst()
        return
    }

    var prevNode: Node?
    var currentNode = head
    for _ in 0 ..< position {
        prevNode = currentNode
        currentNode = currentNode?.next
    }
    prevNode?.next = currentNode?.next
    
}

---

isEmpty

var isEmpty: Bool {
    return head == nil
}

clear

func clear() {
    head == nil
}

 

---

배열 VS 연결리스트

 

배열은 맨 앞에 요소를 더하거나 제거하려고 하면 그 뒤의 모든 요소를 복사해야 한다

또한 배열에 요소를 추가할 때 배열의 크기를 고려해야하고 공간 낭비가 생길 수도 있다

 

연결리스트는 addFront , deleteFront, getFront 모두 O(1) 이다

또 크기를 미리 정의할 필요 없어서 낭비되는 메모리가 없다

 

하지만 큰 단점 -> index가 없고 연결되어 있기 때문에 임의의 요소에 접근하는 것이 시간이 오래걸린다

 

그리고 맨 앞 빼고는 모든 get, set이 O(n)이다

 

 

이런 리스트에 특성은 스택과 큐를 쓸 때 용이하다

스택과 큐는 first element 작업이 많기 때문

 

---

What you need to know

 

1. Anything to do with the front is O(1) -> addFront / getFirst / deleteFirst

전면에서 수행하는 모든 것은 O(1)이다

 

2. Anytime you need to walk - O(n) -> addBack / getBack / deleteLast / ...

전면 외의 모든 작업은 O(n) 이다. for / while 루프를 써서 탐색해야하기 때문

 

3. No random access

index 개념이 없고 연결된 노드들을 통해 탐색해야 하기 때문에 임의 접근 불가

 

4. Always the right size