Linked List

Linked List

Array List와 다르게 연결되어 있기 때문에 개별 하나를 Node라고 부른다. Node 안에는 2개의 변수를 가지는데 첫 번째는 저장되는 값인 Data Field, 두 번째는 다음 Node의 Reference를 알기 위한 Link Field 가 있습니다. 

Linked List를 사용하기 위해서는 첫번째 Node를 알고 있어야만 Link Field를 통해 다음 Node로 갈 수가 있습니다. 첫 번째 Node가 무엇인지의 데이터를 가지고 있는 변수를 HEAD라고 합니다.  

 

Implementing the Node Class

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

extension Node : CustomStringConvertible {
    var description: String {
        guard let next = next else {
            return "\(value.self)"
        }
        return "\(value.self) ->" + String(describing: next) + " "
    }
}

let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)

node1.next = node2
node2.next = node3

print(node1)
// 1 ->2 ->3  

 

Node 클래스를 만들기 위해 Node 에 어떤 타입이든지 가능한 Value타입을 지정한 후 Data Field가 될 변수 value와 Link Field가 될 변수 next를 만든 후 초기화를 통해 값과 다음 노드가 될 변수들을 초기화시켜줍니다. 

extension 은 연결리스트를 실제 볼 수 있도록 만들기 위해 구현합니다. CustomStringConvertible 프로토콜은 description을 통해 콘솔에 출력될 값들을 지정해줄 수 있습니다. 만약 next(다음 노드를 지정하는 Reference)가 없다면 Node의 값을 리턴하고 만약 값이 있다면 Node의 값과 ->을 리턴하고 String(describing: next) 메서드는 다음 노드의 description을 호출합니다. 이 메소드는 Node의 Tail이 될 때까지 Linked List를 보여줍니다.

이제 노드 클래스를 완성했으므로 Node1, Node2, Node3의 Node 클래스 인스턴스를 만듭니다. 인스턴스를 만든 후 Node 클래스 속성의 next에 다음 노드가 될 인스턴스를 넣어줍니다. 

Node1을 프린트해보면 extension으로 구현한 description이 실행됩니다. 

Implementing the Linked List Structure

struct LinkedList<Value> {

    var head : Node<Value>?
    var tail : Node<Value>?

    init() {}
    
    var isEmpty : Bool {
        return head == nil
    }
}

var list = LinkedList<Int>()

 

앞선 과정에서 Node를 만들면 비효율적이기 때문에 Linked List를 관리하는 구조체를 만듭니다. 

head와 tail을 지정할 변수를 만들고 만약 head가 비어있다면 빈 LinkedList를 확인하기 위해 isEmpty 변수를 만듭니다.

앞선 과정과 마찬가지로 CustomStringConvertible 프로토콜을 통해 만약 head가 비어있다면 Empthy List를 리턴하고 헤드가 있다면 

헤드에 연결하면 모든 Linked List를 연결할 수 있으므로 head 노드를 연결합니다. 

Implementing Push

Push의 경우 List의 맨 앞에 값을 추가합니다. 

struct LinkedList<Value> {

    var head : Node<Value>?
    var tail : Node<Value>?

    init() {}
    
    var isEmpty : Bool {
        return head == nil
    }
    mutating func push(_ value : Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
}    

extension LinkedList : CustomStringConvertible {

    var description: String {
        guard let head = head else{
            return "Empty List"
        }
        return String(describing: head)
    }
}

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

extension Node : CustomStringConvertible {
    var description: String {
        guard let next = next else {
            return "\(value.self)"
        }
        return "\(value.self) ->" + String(describing: next) + " "
    }
}

var list = LinkedList<Int>() // Empty List
list.push(3) // 3 
list.push(11) // 11 ->3 
list.push(54) // 54 ->11 ->3  

 

push라는 함수를 만들고 List의 맨 앞에 값을 추가하기 때문에 새로운 값은 무조건 head가 되어야 합니다. head = Node를 통해 새로 만들어지는 값은 무조건 head가 되고 만약 처음 값이 들어가 1개의 Node밖에 없을 경우 tail이 없는 경우를 방지하기 위해 tail이 없다면 tail = head가 됩니다.

CustomStringConvertible 프로토콜을 통해 만약 head가 없다면 Empty List를 반환하고 head가 있다면 head가 실행됩니다. 

변수 list에 LinkedList의 인스턴스를 만듭니다. 인스턴스를 생성했을 때 head를 지정한 적이 없기 때문에 Empty List가 반환됩니다. 

list.push(3)을 넣을 경우 push 메소드의 head = Node(value: value, next: head)의 value 값에 3이 들어가고 Node 클래스의 init(value : Value, next : Node? = nil) 이 실행되고 Node 값이 3이고 next는 기본값인 nil이 되는 Node 가 만들어집니다. 만들어진 Node는 head가 되고 tail은 아직 값이 없기 때문에 nil이 되고 tail = head 이므로 Node는 head 이자 tail이 됩니다. 

list.push(11)을 넣을 경우 push 메소드의 head = Node(value: value, next: head)의 value 값에 11이 들어가고 head에는 값이 3인 Node가 들어갑니다. tail은 값이 3인 Node가 있기 때문에 nil이 아니게 되고 아무것도 실행되지 않습니다. head는 Node(11)로 변경됩니다.

list.push(54)를 넣을 경우 push 메소드의 head = Node(value: value, next: head)의 value 값에 54가 들어가고 head에는 값이 11인 Node가 들어갑니다. tail은 값이 3인 Node가 있기 때문에 nil이 아니게 되고 아무것도 실행되지 않습니다. head는 Node(54)로 변경됩니다.

Implementing Append

Append의 경우 List의 맨 뒤에 값을 추가합니다. 

struct LinkedList<Value> {

    var head : Node<Value>?
    var tail : Node<Value>?

    init() {}
    
    var isEmpty : Bool {
        return head == nil
    }
    mutating func push(_ value : Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    mutating func append(_ value : Value) {
        guard !isEmpty else {
            push(value)
            return
        }
        
        let node = Node(value: value)
        tail!.next = node
        tail = node
    }
}

extension LinkedList : CustomStringConvertible {

    var description: String {
        guard let head = head else{
            return "Empty List"
        }
        return String(describing: head)
    }
}

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

extension Node : CustomStringConvertible {
    var description: String {
        guard let next = next else {
            return "\(value.self)"
        }
        return "\(value.self) ->" + String(describing: next) + " "
    }
}

var list = LinkedList<Int>()

list.append(12) // 12
list.append(1)  // 12 ->1
list.append(34) // 12 ->1 ->34  

 

append라는 함수를 만들고 만약 LinkedList가 비어있지 않다면 아무것도 하지 않고 만약 비어있다면 Push를 이용해 Node를 하나 만듭니다. (위 참고)

두 번째 노드를 추가할 때는 Push로 추가한 12는 tail = head이고 next는 nil입니다. tail.next에 새로 만드는 Node(1)을 넣어줍니다. 사실상 tail의 next를 바꾼 거지만 동시에 tail = head이기 때문에 head의 next도 바꾼 셈입니다. Node12의 head의 next는 nil이었지만 이제 새로 만든 Node(1)이 들어갔습니다. 이제 tail에 기존 Node(12) 대신 새로 만든 Node(1)을 넣어주고 Node는 init(value : Value, next : Node? = nil) 생성자를 통해 기본 값 nil을 가지고 있기 때문에 node(1)의 next는 nil이 됩니다.

세 번째 노드를 추가할 경우 tail!. next에 새로운 Node(34)를 넣어줍니다. 기존 tail.next가 nil이기 때문에 next는 이제 Node(34)가 되었고 기존 tail이었던 Node(1)은 next로 Node(34)를 가리킵니다. tail = Node를 통해 기존 tail이었던 Node(1) 대신 Node(34)로 대체됩니다. 

Implementing Insert

리스트의 특정 노드 뒤에 값을 추가합니다.

struct LinkedList<Value> {

    var head : Node<Value>?
    var tail : Node<Value>?

    init() {}
    
    var isEmpty : Bool {
        return head == nil
    }
    mutating func push(_ value : Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    
    func node(at index : Int) -> Node<Value>? {
    
        var currentIndex = 0
        var currentNode = head
        
        while(currentNode != nil && currentIndex < index) {
            currentNode = currentNode?.next
            currentIndex += 1
        }
        return currentNode
    }
    
    
    func insert(_ value : Value, after node : Node<Value>) {
        node.next = Node(value : value, next : node.next)
    }
    
    
    
    mutating func append(_ value : Value) {
        guard !isEmpty else {
            push(value)
            return
        }
        
        let node = Node(value: value)
        tail!.next = node
        tail = node
    }
    
    
}

extension LinkedList : CustomStringConvertible {

    var description: String {
        guard let head = head else{
            return "Empty List"
        }
        return String(describing: head)
    }
}

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

extension Node : CustomStringConvertible {
    var description: String {
        guard let next = next else {
            return "\(value.self)"
        }
        return "\(value.self) ->" + String(describing: next) + " "
    }
}

var list = LinkedList<Int>()

list.append(12) // 12
list.append(1)  // 12 ->1
list.append(34) // 12 ->1 ->34

let middleNode = list.node(at: 1)!
list.insert(321, after: middleNode) // 12 ->1 ->321 ->34   

 

node라는 함수를 만들고 원하는 위치의 노드를 입력하는 매개변수를 만들고 노드를 return하는 함수를 만듭니다. 

currentNode라는 변수에 LinkedList의 처음 시작인 head를 넣어주고 변수 currentIndex에는 몇 번 탐색하는지 알 수 있는 숫자 0을 넣습니다. 

while 구문을 통해 currentNode가 nil이 아닌지 확인하고(빈 Linked List인지 확인) currentIndex가 내가 원하는 index위치 보다 작을 때 까지 반복합니다. currentNode = currentNode?.next에서 currentNode는 = head입니다. 예제에서는 currentNode는 Node(12)입니다. currentNode?.next는 Node(12)의 다음인 Node(1)을 가리키고 currentNode는 Node(1)이 됩니다. currentIndex는 0에서 1을 추가한 1이 됩니다. 

예제에서는 index에 1을 넣었고 currentIndex는 1이 되었기 때문에 while문을 종료하고 currentNode를(Node(1))을  리턴합니다.

middleNode = Node(1)이 되었고 list.insert에는 값 321과 after에는 Node(1)을 넣었습니다.

insert 메소드 안의 Node에 값이 321이고 next에는 Node(1)의 next인 Node(34)가 들어갑니다. node.next = Node(value : value, next : node.next)이기 때문에 새롭게 만들어진 Node(321)은 Node(1)의 next에 들어갑니다. 

Implementing Pop

List의 맨 앞의 노드를 제거합니다.

struct LinkedList<Value> {

    var head : Node<Value>?
    var tail : Node<Value>?

    init() {}
    
    var isEmpty : Bool {
        return head == nil
    }
    mutating func push(_ value : Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    
    func node(at index : Int) -> Node<Value>? {
    
        var currentIndex = 0
        var currentNode = head
        
        while(currentNode != nil && currentIndex < index) {
            currentNode = currentNode?.next
            currentIndex += 1
        }
        return currentNode
    }
    
    
    func insert(_ value : Value, after node : Node<Value>) {
        node.next = Node(value : value, next : node.next)
    }
    
    mutating func pop() -> Value? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }
    
    mutating func append(_ value : Value) {
        guard !isEmpty else {
            push(value)
            return
        }
        
        let node = Node(value: value)
        tail!.next = node
        tail = node
    }
}

extension LinkedList : CustomStringConvertible {

    var description: String {
        guard let head = head else{
            return "Empty List"
        }
        return String(describing: head)
    }
}

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

extension Node : CustomStringConvertible {
    var description: String {
        guard let next = next else {
            return "\(value.self)"
        }
        return "\(value.self) ->" + String(describing: next) + " "
    }
}

var list = LinkedList<Int>()

list.append(12) // 12
list.append(1)  // 12 ->1
list.append(34) // 12 ->1 ->34

let middleNode = list.node(at: 1)!
list.insert(321, after: middleNode) // 12 ->1 ->321 ->34 

list.pop() //12
list // 1 ->321 ->34  

 

함수 pop을 만들고 제거되는 값을 return 해주기 위해 Value를 리턴합니다. defer 키워드는 함수의 가장 마지막에 실행되는 키워드기 때문에 return head?. value를 리턴합니다. 예제에서는 head가 Node(12)이기 때문에 12를 리턴합니다.

head = head?.next는 head를 다음 Node로 주기 위해 head를 현재 head의 next로 변경합니다. 예제에서는 Node(12)의 head?. next는 Node(1)이기 때문에 이제 head는 Node(1)이 됩니다. ARC에 의해 Node(12)는 참조되는 것이 없기 때문에 자동으로 메모리에서 참조 해제됩니다. 

만약 Linked List에 Node가 1개 였다면 Node는 하나도 남지 않았기 때문에 tail까지 nil로 반환하고 메모리에서 모두 지웁니다. 예제에서는 Node가 여러 개이기 때문에 아무것도 실행 안 하고 넘어갑니다. 

Implementing Remove Last

List의 맨 마지막 노드를 제거합니다.

struct LinkedList<Value> {

    var head : Node<Value>?
    var tail : Node<Value>?

    init() {}
    
    var isEmpty : Bool {
        return head == nil
    }
    mutating func push(_ value : Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    
    func node(at index : Int) -> Node<Value>? {
    
        var currentIndex = 0
        var currentNode = head
        
        while(currentNode != nil && currentIndex < index) {
            currentNode = currentNode?.next
            currentIndex += 1
        }
        return currentNode
    }
    
    
    func insert(_ value : Value, after node : Node<Value>) {
        node.next = Node(value : value, next : node.next)
    }
    
    mutating func pop() -> Value? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }

    mutating func removeLast() -> Value? {
        guard let head = head else {
            return nil
        }
        guard head.next != nil else {
            return pop()
        }
        var prev = head
        var current = head
        
        while let next = current.next {
            prev = current
            current = next
        }
        prev.next = nil
        tail = prev
        return current.value
        
    }

    mutating func append(_ value : Value) {
        guard !isEmpty else {
            push(value)
            return
        }
        
        let node = Node(value: value)
        tail!.next = node
        tail = node
    }
}

extension LinkedList : CustomStringConvertible {

    var description: String {
        guard let head = head else{
            return "Empty List"
        }
        return String(describing: head)
    }
}

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

extension Node : CustomStringConvertible {
    var description: String {
        guard let next = next else {
            return "\(value.self)"
        }
        return "\(value.self) ->" + String(describing: next) + " "
    }
}

var list = LinkedList<Int>()

list.append(12) // 12
list.append(1)  // 12 ->1
list.append(34) // 12 ->1 ->34

list.removeLast() // 34
list // 12 ->1 

 

removeLast라는 함수를 만들고 제거되는 값을 리턴해주기 위해 리턴 Value를 넣습니다. head가 비어있다면 nil을 리턴하는 guard문을 작성합니다. (Linked List가 비었는지 확인) 

head.next가 nil 이라면 pop을 실행합니다. 위에서 Linked List가 비어있지 않다는 것을 확인했고 그렇다면 1개 이상의 Node가 존재합니다. head.next가 nil이라는 것은 Node가 1개라는 것을 의미하고 pop()을 통해 1개의 Node를 제거합니다.

prev라는 변수를 설정하고 head를 넣어줍니다. prev는 제거할 마지막 노드의 바로 전 Node를 일컫습니다. current라는 변수를 설정하고 head를 넣습니다. current는 현재 찾고 있는 Node를 일컫습니다.

while문을 실행하고 next = current.next에서 current는 = head이기 때문에 예제에서 Node(12)의 next 인 Node(1)이 next가 되고 prev = current이기 때문에 현재 current는 Node(12)이기 때문에 prev와 current는 Node(12)입니다. current = next에서 next는 Node(1)이기 때문에 current는 Node(1)로 변경됩니다. 

다시 while문 처음으로 돌아와서 next = current.next에서 current는 Node(1)이기 때문에 예제에서 Node(1)의 next 인 Node(34)가 next가 되고 prev = current이기 때문에 현재 current는 Node(1)이기 떄문에 prev와 current는 Node(1)입니다. current = next에서 next는 Node(34)이기 때문에 current는 Node(34)로 변경됩니다. 

다시 while문 처음으로 돌아와서 next = current.next에서 current는 Node(34)이고 Node(34)는 tail이기 때문에 next가 nil이고 while문은 종료됩니다. 

perv.next에서 perv는 Node(1)이므로 Node(1)의 next는 nil이되고 prev는 tail이 됩니다.

current였던 Node(34)의 값을 반환해줍니다. 

Implementing Remove After

List의 특정 Node다음의 Node를 제거합니다. 

struct LinkedList<Value> {

    var head : Node<Value>?
    var tail : Node<Value>?

    init() {}
    
    var isEmpty : Bool {
        return head == nil
    }
    mutating func push(_ value : Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    
    func node(at index : Int) -> Node<Value>? {
    
        var currentIndex = 0
        var currentNode = head
        
        while(currentNode != nil && currentIndex < index) {
            currentNode = currentNode?.next
            currentIndex += 1
        }
        return currentNode
    }
    
    
    func insert(_ value : Value, after node : Node<Value>) {
        node.next = Node(value : value, next : node.next)
    }
    
    mutating func pop() -> Value? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }

    mutating func removeLast() -> Value? {
        guard let head = head else {
            return nil
        }
        guard head.next != nil else {
            return pop()
        }
        var prev = head
        var current = head
        
        while let next = current.next {
            prev = current
            current = next
        }
        prev.next = nil
        tail = prev
        return current.value
        
    }
    
    mutating func remove(after node : Node<Value>) -> Value? {
        
        defer {
            if node.next === tail {
                tail = node
            }
            node.next = node.next?.next
            
        }
        return node.next?.value
    }

    mutating func append(_ value : Value) {
        guard !isEmpty else {
            push(value)
            return
        }
        
        let node = Node(value: value)
        tail!.next = node
        tail = node
    }
}

extension LinkedList : CustomStringConvertible {

    var description: String {
        guard let head = head else{
            return "Empty List"
        }
        return String(describing: head)
    }
}

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

extension Node : CustomStringConvertible {
    var description: String {
        guard let next = next else {
            return "\(value.self)"
        }
        return "\(value.self) ->" + String(describing: next) + " "
    }
}

var list = LinkedList<Int>()

list.append(12) // 12
list.append(1)  // 12 ->1
list.append(34) // 12 ->1 ->34


let index = 1 // 1
let node = list.node(at: index - 1)! // 12 ->1 ->34  
let removedValie = list.remove(after: node) // 1
list // 12 ->34  

 

remove 함수를 만들고 특정 노드를 선택한 Node 매개변수를 지정하고 삭제되는 값을 리턴해주기 위해 리턴에 Value를 넣습니다.

defer키워드는 함수의 마지막에 실행되기 때문에 return node.next?.value가 실행되고 예제에서는 Node(12)를 Node 매개변수에 넣었기 때문에 Node(12)의 next인 Node(1)의 값이 리턴됩니다.

만약 node.next가 tail 과 같다면 node = tail에서 만약 예제에서 12 -> 1이었다면 node.next는 Node(1)이 되고 tail도 Node(1)이므로 같게 되고 Node(12)는 tail이 되고 Node는 한 개가 됩니다.

하지만 예제는 12 -> 1 -> 34 이므로 node.next 는 Node(1)이고 tail은 Node(34)이기 때문에 실행되지않고 넘어갑니다.

node.next?. next는 Node(34)이고 이는 Node(12)의 next가 됩니다.