LinkedList

Linked List

출처: https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/

Linked Lists 는 Singly Linked List, Doubly Linked List 두개로 나뉘어요.

Linked List 는 우선, List 가 Linked 되어있는... 형태의 Data Structure 입니다. 

다시 말하면, 여러개의 요소들 (List) 이 서로 연결되어있는 (Linked) 모양의 띠어요.

 

 

Singly Linked List

Singly Linked List 부터 설명드리면, 

가장 앞에 있는 element 는 head 라고 부르고, 이 head 는 값과 다음 값을 가리키는 pointer 를 갖습니다. 

만약 다음 값이 없다면 pointer 는 null (Swift 내에서는 nil ) 값을 가지겠지요. 

 

반대로 가장 뒤에 있는 element 는 tail 이라 부르고, 이 부분의 pointer 는 항상 nil 을 갖습니다. (뒤에 아무것도 없기 때문에) 

 

 

Sinly Linked List 가 Array 에 대해 가지는 이점으로는 prepend, 할때나 맨 앞에 있는 element 를 delete 할 때 훨씬 더 빠르게 해줄 수 있습니다. 

 

아래는 Swift 로 구현한 Singly Linked List 입니다 ~~ !

(lookup func 구현에서 equality check 가 필요했기 때문에 모든 element 에 대해 Equatable protocol constraint 을 주었습니다.)

 

public class LLNode <T : Equatable>{ // added Equatable protocol because of lookup function
    var value: T
    var next: LLNode?
    
    public init(value: T) {
        self.value = value
    }
}

public class LinkedList<T : Equatable> {
    public typealias Node = LLNode<T>
    
    private var first: Node?
    
    public var head: Node? {
        return first
    }
    
    public var tail: Node? {
        guard var node = first else { return nil }
        while let next = node.next {
            node = next
        }
        return node
    }
    
    
    public func prepend(value: T) {
        let newNode = Node(value: value)
        guard first != nil else { first = newNode; return }
        
        let temp = first
        first = newNode
        first!.next = temp
    }
    
    
    public func append(value: T) {
        let newNode = Node(value: value)
        
        if let lastNode = tail {  // at least one node in the list
            lastNode.next = newNode
        } else { // no nodes in list
            first = newNode
        }
    }
    
    
    public func lookup( value: T ) -> Bool{
        guard var node = first else { return false }
        if node.value == value { return true }
        while let next = node.next {
            if next.value == value { return true}
            node = next
        }
        return false
    }
    
    
    public func insert(index: Int, value: T) {
        var count = 0
        if index == 0 { prepend(value: value) ; return} // initial index
        guard index > 0 else { return }
        
        guard var node = first else { return }
        
        while let next = node.next {
            if count == index - 1 {
                let newNode = Node(value: value)
                newNode.next = next
                node.next = newNode
                return
            }
            node = next
            count += 1
        }
    }
    
    
    public func delete(index: Int) {
        guard var node = first else { return }
        
        if index == 0 {
            first = node.next
            return
        }
        var count = 0
        while let next = node.next {
            
            count += 1
            if count == index {
                node.next = next.next
                return
            }
            node = next
        }
    }
}

 

이제 기능별로 나누어서 하나하나 뜯어보겠습니다. 

    private var first: Node?
    
    public var head: Node? {
        return first
    }
    
    public var tail: Node? {
        guard var node = first else { return nil }
        while let next = node.next {
            node = next
        }
        return node
    }

우선, 가장 먼저 property 에 대해 알아볼게요. 

 

head 는 public var 로, first 는 private, computed property 로 선언되었습니다. 따라서, first 는 외부에서 접근 불가하고, head 는 외부에서 접근은 가능하지만 임의로 바꿔줄 수 없어요 (read-only). 단지 어떤 값이 head 에 있는지 확인만 가능할 뿐입니다. 

 

tail 역시 head 와 마찬가지로 public var 로 선언되었고, computed read-only property 로, 외부에서 오직 읽을 수만 있게 설정되었습니다. 또한, 값이 필요할 때마다 'first' 로부터 하나씩 뒤로 이동하여 마지막 node 값을 반환하게 됩니다. 

 

 

이제 각 method 가 어떻게 작동하는지 살펴볼게요. 

 

 

 

 

prepend(_:)

public func prepend(value: T) {
        let newNode = Node(value: value)
        guard first != nil else { first = newNode; return }
        
        let temp = first
        first = newNode
        first!.next = temp
    }

prepend(_:) method 는 가장 앞에 위치한 head 를 다른 node 로 변경할 때 사용합니다. 'head' property 는 외부에서 수정 불가하기 때문에, 이 method 를 사용하여 바꿔주어야 합니다.

 

 

 

1. 기존 head 를 다른 곳에 임시 저장 (let temp = first)

2. head 에 새로운 값 할당 (first = newNode)

3. 새로운 값 뒤에, 기존 head 이어붙이기. (first!.next = temp)

(위에서 first 에 대한 nil check 를 해주었기 때문에 force-unwrapping 하였습니다. ) 

 

Array 에서는 맨 앞의 element 를 바꿔주기 위해서는 모든 element 를 한칸씩 뒤로 이동시켜줘야 했지만 (O(n)) , linked list 에서는 3 steps 만 밟아주면 돼요 (O(1)). 

 

3 --> 5 -->7
prepend(1)
1 --> 3 --> 5 --> 7 

 

 

 

 

append(_:)

public func append(value: T) {
        let newNode = Node(value: value)
        
        if let lastNode = tail {  // at least one node in the list
            lastNode.next = newNode
        } else { // no nodes in list
            first = newNode
        }
    }

append(_:) 는 원하는 값을 갖는 Node 를 tail 의 마지막 부분에 추가시켜주는 method 입니다. 

 

 

1. tail 이 존재하는지 확인한다. 

2. 있으면 그 뒤에 해당 값을 갖는 Node 를 붙여준다.

3. 없는 경우 (Linked List 에 아무런 값도 없는 경우입니다.) head 에 해당 값을 갖는 Node 를 넣는다.

 

Array 에서의 append 와는 약간 다른 방식이지만, Singly Linked List 에서도 Array 와 마찬가지로 O(1) 의 Time Complexity 로 처리가능합니다. 

 

1 --> 3 --> 5 --> 7
append(9)
1 --> 3 --> 5 --> 7 --> 9

 

 

 

 

 

lookup(_:)

public func lookup( value: T ) -> Bool{
        guard var node = first else { return false }
        if node.value == value { return true }
        while let next = node.next {
            if next.value == value { return true}
            node = next
        }
        return false
    }

lookup(_:) 은, 어떠한 값이 Linked List 내에 존재하는지 확인할 때 사용하는 method 입니다.

(해당 function 을 이용하기 위해 Node 내 value type 을 'Equtable' 로 제한해주었었죠? )

 

 

과정은 아래와 같습니다. 

1. head 가 있는지 확인합니다. (없으면 false 반환)

2. head 가 있다면, 갖고있는 값이 찾고있는 값인지 확인합니다. (맞으면 true 반환)

3. 그 값이 아니라면, 다음 Node 에 대하여 값을 확인하고, 이 과정을 반복합니다. 

 

lookup(_:) method 는, 위와 같이 node 에 일일이 방문하여 value 를 확인해야 하기때문에 최악의 경우 모든 node 를 확인해야합니다. 따라서 O(n) 의 Time Complexity 를 갖습니다.

 

 

 

 

insert(_:_:)

public func insert(index: Int, value: T) {
    var count = 0
    if index == 0 { prepend(value: value) ; return } // initial index
    guard index > 0 else { return }
        
    guard var node = first else { return }
        
    while let next = node.next {
        if count == index - 1 {
           let newNode = Node(value: value)
            newNode.next = next
            node.next = newNode
            return
        }
        node = next
        count += 1
    }
}

insert(_:_:) 는 linked list 중간 어딘가에 값을 새로 넣고 싶을 때 사용하는 method 입니다.

 

 

순서는 다음과 같습니다. k 번째 인덱스에 a 라는 값을 넣고 싶을 때를 가정하겠습니다. 

1. k -1 번째 node 를 찾아갑니다. 

2. a 라는 값을 가지고 있는 새로운 node 를 생성합니다.

3. 새로운 node 의 next node 로 k 번째 node (next) 를 연결시켜줍니다.

2. k -1 번째 node 와 새로운 node 를 연결시켜줍니다. 

 

insert(_:_:) 는 위와 같이 k 번째 node 까지 방문해서 몇가지 작업을 해주어야 하기때문에 O(n) 의 Time Complexity 를 갖습니다

 

 

delete(_:)

public func delete(index: Int) {
        guard var node = first else { return }
        
        if index == 0 {
            first = node.next
            return
        }
        var count = 0
        
        while let next = node.next {
            count += 1
            if count == index {
                node.next = next.next
                return
            }
            node = next
        }
    }

delete(_:) 는 원하는 index 에 있는 node 를 제거하는 method 입니다.

 

k번째 node 를 제거 할때의 과정은 다음과 같습니다. 

1. k 번째 node 를 찾아갑니다.

2. k+1 번째 node (next.next) 를 k - 1번째 node 의 next 로 설정해줍니다. 

 

delete 의 경우에도 원하는 index 까지 일일이 방문해야 하기때문에 O(n) 의 Time Complexity 를 갖습니다.

 

 

 

 

LLNode 와 append(_:) 부분에서 아래 youtube 를 참조했습니다.

https://www.youtube.com/channel/UCtegvRiZKojo8MG1gCF-NMg