Linked List (with Swift) - Node and Adding Values to List

Linked List란 선형의 단방향으로 이루어진 값들의 집합이라 할 수 있습니다.

Linked List는 Swift의 Array와 같은 연속적인 저장에 다양한 이론적인 이점을 가지고 있습니다. (상수 시간에 삽입과 삭제가 이루어질 수 있음) 위의 그림과 같이 Linked List는 Node들이 연결된 형태로 존재합니다. 

---

Node?

Node는 값을 가질 수 있고, 또한 다음 Node와의 Reference를 가집니다. 만약 Reference의 값이 nil 이라면 이 Node가 마지막이라는 의미가 됩니다. 

Node 타입을 코드로 작성해 보면

public class JoonsNode<T> {
    public var value: T
    public var nextNode: JoonsNode?
    
    public init(value: T, nextNode: JoonsNode? = nil) {
        self.value = value
        self.nextNode = nextNode
    }
}

extension JoonsNode: CustomStringConvertible {
    public var description: String {
        guard let next = nextNode else {
            return "\(value)"
        }
        return "\(value) -> " + String(describing: next) + " "
    }
}

이제 Node를 생성해 보겠습니다.

let node1 = JoonsNode(value: "Joons")
let node2 = JoonsNode(value: "Like")
let node3 = JoonsNode(value: "Swift")

node1.nextNode = node2
node2.nextNode = node3
print(node1)

결과를 볼까요?

마지막에 있는 "Swift"라는 value를 가진 Node의 nextNode의 값은 nil이 됩니다. 자신이 마지막임을 알리는 표시라고도 볼 수 있습니다.

---

Linked List

이제 이 Node를 가지고 LinkedList를 만들어 보도록 하겠습니다!

Linked List는 head와 tail의 개념을 가지고 있습니다. 

public struct JoonsLinkedList<T> {
    public var head: JoonsNode<T>?
    public var tail: JoonsNode<T>?
    
    public init() {}
    
    public var isEmpty: Bool {
        head == nil
    }
}

이 List에 값을 추가하는 방법에 대해서 알아보겠습니다.

• push : List의 제일 앞에 값을 추가
• append : List의 제일 뒤에 값을 추가
• insert(after: ) : 어떤 Node 뒤에 값을 추가

우선 push부터 보겠습니다. push는 List의 제일 앞에 값을 추가하는 과정입니다. 그러므로 head부분에 새로운 값이 들어가는 과정이 필요합니다. head-first insertion이라고도 불립니다.

push

이러한 형태가 된다고 볼 수 있겠죠? 코드로 작성해 보겠습니다.

    public mutating func push(_ value: T) {
        head = JoonsNode(value: value, nextNode: head)
        // Linked List에 Node가 한개만 존재했다면
        if tail == nil {
            tail = head
        }
    }

위의 그림과 같은 리스트를 만들어 보겠습니다. 

var list = JoonsLinkedList<Int>()
list.push(2)
list.push(1)
list.push(5)

print(list)

이렇게 표현할 수 있고 출력을 보면

이렇게 그림과 같이 만들어 지는 것을 볼 수 있습니다.

 

이번에는 append에 대해서 알아보겠습니다.

 

 

push와는 반대로 append는 tail에 값을 넣어주는 형식입니다.

append를 할 때 고려해야 할 점은 List가 비어있을때만 고려해주면 됩니다.

바로 코드로 보겠습니다.

 

 

    public mutating func append(_ value: T) {
        //비어있는 List이면 append한 값이 head가 되는것과 같다.
        guard !isEmpty else {
            push(value)
            return
        }
        
        //현재 tail의 다음이 append한 node가 된다.
        tail!.nextNode = JoonsNode(value: value)
        
        //그리고 현재 tail 은 방금 추가해 준 Node가 된다.
        tail = tail!.nextNode
    }

append를 활용하여 위의 그림과 같은 Linked List를 만들어 보면 다음과 같이 작성될 수 있습니다.

list.append(1)
list.append(2)
list.append(3)

print(list)

마지막으로 insert입니다.

 

 

insert는 우선 특정 Node를 찾은 후에, Node를 삽입하고 다시 연결을 해주는 작업을 필요로 합니다. 

그렇기에 단계가 두가지로 분리됩니다. 

 

 

 

첫번째로, insert하고자 하는 위치를 찾는 것입니다. 

    public func node(at index: Int) -> JoonsNode<T>? {
        var nowNode = head
        var nowIndex = 0
        
        //찾고자 하는 위치까지 이동
        while nowNode != nil && nowIndex < index {
            nowNode = nowNode?.nextNode
            nowIndex += 1
        }
        
        return nowNode
    }

 

두번째로, insert를 진행하는 것입니다. 

    @discardableResult
    public mutating func insert(_ value: T, after node: JoonsNode<T>) -> JoonsNode<T> {
        guard tail !== node else {
            append(value)
            return tail!
        }
        
        node.nextNode = JoonsNode(value: value, nextNode: node.nextNode)
        return node.nextNode!
    }

위 그림과 같이 만들어 보겠습니다.

list.append(1)
list.append(2)
print(list)

우선 1 -> 2의 형식을 가진 List를 만들어 두고, 그림과 같이 insert를 진행하려면 0번 인덱스에 3이라는 value를 추가해야 합니다. 

let insertPos = list.node(at: 0)!
list.insert(3, after: insertPos)

insert할 위치를 찾은 다음, 그 위치에 insert를 해줍니다. 

그러면 위와 같이 insert가 성공적으로 작동한 모습을 확인할 수 있습니다. 

List에서 값을 제거하는 방법 부터는 다음 포스팅에서 작성해보도록 하겠습니다! 🙏