Problem

배열을 사용할 때의 문제점이 있다. 값을 삽입할때 느리고(선형시간) 크기가 정해져있기 때문에 사용하지 않는 부분은 메모리 낭비가 될 수 있다. 하지만 연결 리스트를 사용하면 값을 삽입하는 것이 빠르고 크기를 정해놓을 필요 없이 동적으로 크기를 조절할 수 있다.

Linked List

연결리스트는 노드(Node)의 연결로 구성된 데이터의 모음이다. 노드는 값과 다음 노드의 주소를 저장하고 있다. 기차를 생각하면 이해가 쉬운데 기차를 연결 리스트로 생각하고 기차의 각 칸을 노드라고 생각하면 된다. 연결리스트에는 헤드와 테일이 있는데 헤드는 첫번째 노드, 테일은 맨 끝 노드를 말한다. 맨 끝 노드의 다음 노드는 존재하지 않으므로 nil값이 저장된다. 연결 리스트를 코드로 구현하면 다음과 같이 할 수 있다.

class Node {
    var data: Int // Int뿐만 아니라 어느 타입의 데이터든 저장 가능하다.
    var next: Node? // 테일은 nil값을 저장하므로 옵셔널로 지정한다.
    
    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)
}


printLinkedList(node1)
// [1, 2, 3]

위와 같이 연결리스트를 구현할 수 있지만 실전에서는 LinkList 이름의 클래스를 만들어서 메소드를 구현하여 사용한다.

연결 리스트는 UIKit의 responder chain에도 사용된다.

Methods

import Foundation

class Node {
    var data: Int
    var next: Node?
    
    init(_ data: Int, _ next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

class LinkList {
    private var head: Node?
    
    func addFront(_ data: Int) {
        let newNode = Node(data)
        newNode.next = head
        head = newNode
    }
    
    func getFirst() -> Int? {
        if head == nil {
            return nil
        }
        return head!.data
    }
    
    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
    }
    
    func getLast() -> Int? {
        if head == nil {
            return nil
        }
        
        var node = head!
        while(node.next != nil) {
            node = node.next!
        }
        return node.data
    }
    
    
    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
    }
    
    // O(1)
    func deleteFirst() {
        head = head?.next
    }
    
    // O(n)
    func deleteLast() {
        var nextNode = head
        var previousNode: Node?
        while(nextNode?.next != nil) {
            previousNode = nextNode
            nextNode = nextNode?.next
        }
        previousNode?.next = nil
    }
    
    // O(n)
    func delete(at position: Int) {
        if position == 0 {
            self.deleteFirst()
            return
        }
        
        var nextNode = head
        var previousNode: Node?
        for _ in 0..<position {
            previousNode = nextNode
            nextNode = nextNode?.next
        }
        previousNode?.next = nextNode?.next
    }
    
    var isEmpty: Bool {
        return head == nil
    }
    
    func clear() {
        head = nil
    }
    
    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)
    }
}

let linkedList = LinkList()

addFront

새 노드를 헤드에 삽입하는 메소드. 배열처럼 값들을 복사해서 다른 인덱스로 붙여넣을 필요 없이 단순히 헤드의 포인터를 변경하여 상수시간으로 삽입이 가능하다.

getFirst

헤드를 리턴하는 메소드. 헤드가 nil이라면 nil을 리턴하고 아니라면 헤드의 데이터를 리턴한다.

addBack

새 노드를 테일에 삽입하는 메소드.

getLast

테일을 리턴하는 메소드.

insert

원하는 위치에 노드를 삽입하는 메소드.

deleteFirst

헤드를 삭제하는 메소드.

deleteLast

테일을 삭제하는 메소드.

delete(at:)

원하는 위치의 노드를 삭제하는 메소드.

Linked List vs Array

장점

• 첫번째 인덱스에 삽입하거나 접근하거나 삭제하는 것이 빠르다.(O(1))
• 크기가 동적으로 조절된다.

단점

• 배열처럼 무작위 접근을 하지 못한다.
• 마지막 인덱스에 삽입하거나 접근하거나 삭제하는 것이 느리다.(O(n))

순환 찾기

import UIKit

/*
 Detect A Cycle
 https://www.hackerrank.com/challenges/ctci-linked-list-cycle/problem
 https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare
 
 A linked list is said to contain a cycle if any node is visited more than once while traversing the list. For example, in the following graph there is a cycle formed when node 5 points back to node 3.
 
        4
      /   \
 1 2 3      5
     \_____/
 
 */

class Node {
    var data: Int
    weak var next: Node?
    
    init(_ data: Int, _ next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

func hasCycle(first: Node) -> Bool {
    var slow: Node? = first
    var fast: Node? = first
    
    while fast != nil && fast!.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        
        if slow?.data == fast?.data {
            return true
        }
    }
    return false
}

let node5 = Node(5)
let node4 = Node(4)
let node3 = Node(3)
let node2 = Node(2)
let head = Node(1)

head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node3

hasCycle(first: head)

The Tortoise & The Hare 알고리즘을 사용한 예시.
slow는 한번 움직일때 한 칸씩 이동하고 fast는 두 칸씩 이동한다. slow와 fast는 무조건 언젠가 만나게 되어있다.