[Data Structure / Algorithms] Linked List (2)

전성훈·2023년 10월 31일
AlgorithmsdatastructureiOSswift
0

Data Structure-Algorithm

목록 보기
3/35
post-thumbnail

주제: Linked List 심화 구조

Swift Collection Protocols

  • Swift standard library는 특정 타입에 대해 무엇이 필요한지 정의해주는 여러 set 프로토콜이 있다.
  • 각 각의 프로토콜은 고유의 특징과, 성능을 보장한다.
  • set 프로토콜의 기본 종류로선 Sequence, Collection, BidirectionalCollection, RandomAccessCollection 등 이 있다.
  • Sequence

    Sequence 타입은 해당 요소에 대한 순차적 접근을 제공한다.
    무한하거나 유한하다.
    한 번 이상 이터레이트할 수도 있지만 한 번 이상 이터레이트가 가능할지에 대해서는 장담할 수 없다
    이터레이트(Iterate): 반복하다라는 의미로 요소를 순회하며 반복 작업을 수행하는 과정을 말한다.

  • Collection

    모든 Collection은 Sequence를 상속받아 구현되었으며, Collection은 Sequence가 지닌 두 가지 문제점을 해결했다.
    우선, 모든 Collection은 유한하며, 몇 개의 요소로 구성되어 있는지 항상 알 수 있다.
    또한 Sequence에서는 오직 한 번만 이터레이트가 가능했던 것을 Collection에서는 원하는 만큼 할 수 있다.

  • BidirectionalCollection

    BidirectionalCollection은 한 가지만 제외하고는 Collection과 매우 유사하다. Collection이 Sequence를 상속받은 것처럼, BidirectionalCollection은 Collection을 상속받았지만 정방향뿐만 아니라 역방향으로도 탐색할 수 있다는 차이가 있다.
    역방향으로 이동하는 기능을 위해 index(before: ) 함수가 추가되었다.

  • RandomAccessCollection

    RandomAccessCollection은 빠르게 요소에 접근할 수 있게 도와준다. 순서대로 하나씩 요소에 접근하는 대신, 해당 요소로 바로 접근할 수 있다.

  • RandomReplaceableCollection

    Collection 중간의 요소를 다른 것으로 교체할 수 있는 기능을 제공한다.

  • MutableCollection

    요소들의 값을 설정할 수 있는 기능을 제공한다.

  • Linked list는 두 가지의 Swift Collection protocols을 채택할 수 있다.
  1. nodes들로 이루워진 체인이므로 Sequence 프로토콜을 채택할 수 있다.
  2. nodes들의 체인은 유한하므로 Collection 프로토콜을 채택할 수 있다.

Becoming a Swift collection

  • Swift의 Collection은 서브스크립트를 통한 접근도 가능하며, 이는 인덱스를 컬렉션 내의 값에 매핑할 수 있다는 고급 용어이다.
  • Collection 프로토콜 메서드의 성능을 결정하는 주요 지표는 Index를 값에 매핑하는 속도이다.
  • Swift Array와 같은 다른 저장 옵션과는 달리, 연결 리스트는 정수 인덱스를 사용하여 O(1) 서브스크립트 연산을 달성할 수 없다.

    서브스크립트 연산: 컬렉션, 리스트, 시퀀스 등의 요소에 접근하기 위해 사용되는 짧은 문법이다. 서브스크립트를 사용하면, 인스턴스 뒤에 대괄호를 사용해 인덱스를 넣어 값을 가져오거나 설정할 수 있다. 예를 들어, Swift의 배열(Array)에서 서브스크립트를 사용해 특정 위치의 요소를 가져오거나 변경할 수 있다. 

var numbers = [10, 20, 30, 40, 50]
let firstNumber = numbers[0]  // 10을 가져옴
numbers[1] = 25              // 배열의 두 번째 요소를 25로 변경
  • 따라서, 목표는 각각의 노드에 대한 참조를 포함하는 사용자 정의 인덱스를 정의하는 것이다.
extension LinkedList: Collection { 

	public struct Index: Comparable { 
	
		public var node: Node<Value>?
		
		static public func ==(lhs: Index, rhs: Index) -> Bool { 
			switch (lhs.node, rhs.node) { 
				case let (left?, right?) : 
					return left.next === right.next 
				case (nil, nil): 
					return true
				default: 
					return false
			}
		}
		
		static public func < (lhs: Index, rhs: Index ) -> Bool { 
			guard lhs != rhs else { 
				return false
			}
			let nodes = sequence(first: lhs.node) { $0?.next } 
			return nodes.contains { $0 === rhs.node }
		}
	}
	
	public var startIndex: Index { 
		Index(node: head)
	}
	
	public var endIndex: Index { 
		Index(node: tail?.next)
	}
	
	public func index(after i: Index) -> Index { 
		Index(node: i.node?.next)
	}
	
	public subscript(position: Index) -> Value { 
		position.node!.value
	}
}
  1. startIndex는 linked list의 head이다.
  2. Collection 에서 endIndex는 마지막으로 접근 가능한 값의 바로 다음 인덱스이므로 tail?.next로 할당한다.
  3. index(after:)는 node의 next node를 반환한다.
  4. subscript는 Index를 collecton 값에 매핑하는데 사용한다. 사용자 정의 인덱스를 생성했으므로 노드의 값을 참조하여, 일정한 시간 내에 쉽게 인덱스를 생성할 수 있다.

Value semantics and copy-on-write

  • Swift Collection의 또 다른 중요한 특징은 값 타입 성격이다. 이는 COW(Copy-on-Write)를 사용하여 효율적으로 구현된다.

    COW는 프로그래밍에서 효율적인 데이터 관리를 위해 사용되는 기법 중 하나이다. 이 전략은 데이터의 복사본을 만들 때 실제 복사가 필요한 시점까지 기다렸다가, 데이터에 변경이 발생할 때에만 복사본을 생성한다.
    COW를 사용하면 메모리 사용량을 줄일 수 있고, 프로그램의 성능을 향상시킬 수 있다. 데이터를 복사할 때마다 전체 데이터를 복사하는 대신, 데이터를 변경해야 하는 시점에서만 복사를 수행하므로 효율적이다. 

let array1 = [1, 2] 
var array2 = array1
print("array1: \(array1)") 
print("array2: \(array2)")
print("---After adding 3 to array 2---") 
array2.append(3) 
print("array1: \(array1)") 
print("array2: \(array2)") 

array1: [1, 2]
array2: [1, 2]
---After adding 3 to array 2---
array1: [1, 2]
array2: [1, 2, 3]
var list1 = LinkedList<Int>()  
list1.append(1)  
list1.append(2) 
var list2 = list1   
print("List1: \(list1)") 
print("List2: \(list2)") 
print("After appending 3 to list2") 
list2.append(3)  
print("List1: \(list1)")   
print("List2: \(list2)") 

List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2 
List1: 1 -> 2 -> 3
List2: 1 -> 2 -> 3
  • 위 코드를 보면 알 수 있듯이 Linked List는 값 타입(value semantics)을 가지고 있지 않다.
  • 이는 내부 저장소가 참조 타입(Node)을 사용하기 때문이다. 이는 LinkedList가 구조체이며 값의 성질을 가져야 하기 때문에 심각한 문제이다.
  • 이를 COW를 구현함으로써 해결할 수 있다.
  • COW를 사용하여 값의 성질을 달성하기 위한 방법은 비교적 간단하다. 연결 리스트의 내용을 변경하기 전에 내부 저장소를 복사하고 모든 참조를 새로운 복사본으로 업데이트 하면 된다. 
private mutating func copyNodes() { 
	
	guard !isKnownUniquelyReferenced(&head) else { 
		return 
	}
	
	guard var oldNode = head else { 
		return
	}
	
	head = Node(value: oldNode.value)
	var newNode = head
	
	while let nextOldNode = oldNode.next { 
		newNode!.next = Node(value: nextOldNode.value)
		newNode = newNode.next
		
		oldNode = nextOldNode
	}
	tail = newNode
}
  • 이제 LinkedList에서 mutating 키워드로 표시된 모든 다른 메서드를 찾아서 각 메서드의 최상단에서 copyNodes를 호출한다. Linked List(1) 참고
    • push
    • append
    • insert(after: )
    • pop
    • removeLast
    • remove(after: )

Optimizing COW(Copy-on-Write)

  • 모든 변경 호출에 대해서 O(n) 오버헤드는 허용할 수 없다. 이를 해결하기 위해서는 두 가지 전략이 이 문제를 완화하는 데 도움이 된다.

isKnownUniquelyReferenced

  • 노드가 단일 소유자인 경우 복사를 피하는 것이다.
  • Swift 표준 라이브러리에는 isKnownUniquelyReferenced라는 함수가 있다. 이 함수는 객체가 정확히 하나의 참조를 가지고 있는지 여부를 확인하는 데 사용할 수 있다. 
guard !isKnownUniquelyReferenced(&head) else { 
	return 
}
  • 위의 코드를 copyNodes의 맨 위에 다음 조건을 추가하여, 내부 노드 객체가 공유되는지 여부를 확인할 수 있다.

A minor predicament (작은 문제)

print("Removing middle node on list2") 
if let node = list2.node(at: 0) {
	list2.remove(after: node)
 } 
 print("List2: \(list2)")

---Example of linked list cow--- 
List1: 1 -> 2 
List2: 1 -> 2 
After appending 3 to list2 
List1: 1 -> 2 
List2: 1 -> 2 -> 3 
Removing middle node on list2
List2: 1 -> 2 -> 3
  • remove 작업이 정상 작동되지 않는다. 그 이유는 CoW 최적화 때문이다.
  • 위에서 보면 head가 하나만 소유하고 있을 때 return하고 그렇지 않다면 복사 함수를 실행하는데 list2.node(at:0)에서 head 노드를 가리키고 있어서 head가 임시적으로 두 개가 소유하고 있어 복사 함수가 실행되어, 기존 list2의 제거가 실행되지 않는다.
  • 이를 해결하기 위해서는 copyNods 메서드의 전용 버전을 작성해 준다. 
private mutating func copyNodes(returningCopyOf node: Node<Value>?) -> Node<Value>? { 
	guard !isKnownUniquelyReferenced(&head) else { 
		return nil 
	}
	
	guard var oldNode = head else { 
		return nil
	}
	
	head = Node(value: oldNode.value)
	var newNode = head
	var nodeCopy: Node<Value>? 
	
	while let nextOldNode = oldNode.next { 
		if oldNode === node { 
			nodeCopy = newNode
		}
		newNode!.next = Node(value: nextOldNode.value)
		newNode = newNode!.next
		oldNode = nextOldNode 
	}
	return nodeCopy
}
  • 위 코드는 이전 함수와 매우 비슷하다. 하지만 주요 차이점으로 전달된 매개변수를 기반으로 새로 복사된 노드를 반환한다는 것이다.
  • 위 함수를 활용하여 remove(after: ), insert(after: )두 함수를 변경해줘야 한다. 
@discardableResult 
public mutating func remove(after node: Node<Value>) -> Value? { 
	guard let node = copyNodes(returningCopyOf: node) else { return nil }
	 defer {
		  if node.next === tail { 
			  tail = node 
			  } 
			  node.next = node.next?.next 
		}
	 return node.next?.value
 }
  • 하지만 이렇게 코드를 만들게 될 경우 after node에 '0'이 아닌 0 이상의 1,2,3 등 의 숫자를 넣게 되면 nil이 방출된다. 왜냐하면 after 위치에 node가 0이 아닌 다른 위치를 참조하므로써 0(head)를 참조하는 값은 기존 값 혼자 이기 때문에 맨위 guard 문에서 걸러져 nil을 방출한다.
  • 해결방법으로는 node의 위치가 0일때와 아닐때로 구분해서 코드를 짜서 해결했다. 
    @discardableResult
    public mutating func insert(_ value: Value,
                                after node: Node<Value>
    ) -> Node<Value> {
        if node === head {
            let node = copyNodes(returningCopyOf: node)!
            guard tail !== node else {
                append(value)
                return tail!
            }
            node.next = Node(value: value, next: node.next)
            return node.next!
        } else {
            copyNodes()
        }
        guard tail !== node else {
            append(value)
            return tail!
        }
        node.next = Node(value: value, next: node.next)
        return node.next!
    }
  • 하지만 이렇게 코드를 실행했을 때 또다른 문제점을 발견했다. 
// 1 
var list55 = list
list.removeLast()
list.insert(5, after: list.node(at: 3)!)
// 2
var list55 = list
list.insert(5, after: list.node(at: 3)!)
list.removeLast()
  • 1번은 정상적으로 작동하는데 2번 같은 경우 insert되는 곳이 list가 아니라 list55가 된다...
  • 이를 어떻게 해결해야할까
  • 해결법 
@discardableResult
    public mutating func insert(_ value: Value,
                                after node: Node<Value>
    ) -> Node<Value> {
        guard let node = copyNodes(returningCopyOf: node) else {
            guard tail !== node else {
                append(value)
                return tail!
            }
            
            node.next = Node(value: value, next: node.next)
            return node.next!
        }
        guard tail !== node else {
            append(value)
            return tail!
        }
        
        node.next = Node(value: value, next: node.next)
        return node.next!
    }
  • Guard 문 밖과 안을 전부다 nil 값이 아닌 같은 로직으로 구현하면 해결 가능

Linked List 사용하기

  • Linked List의 반전된 버전을 원소 하나 하나 출력해라.

    재귀 함수를 활용하면 쉽게 풀 수 있다.
    노드를 끝까지 재귀함수로 돌고 마지막 노드에서 부터 출력하면 되는데 LinkedList는 node를 가리키는게 head와 tail밖에 없으니, node를 직접 건드릴 수 있는 함수를 생성하고 private 하게 설정하면 안전한 함수를 만들 수 있다.

private func reverseNode<T>(_ node: Node<T>?) { 
	guard let node = node else { return }
	
	reverseNode(node.next)
	print(node.value)
}

func reverseLinkedList<T>(_ list: LinkedList<T>) { 
	reverseNode(list.head)
}

Find the middle node

  • 연결리스트의 중앙값을 찾아내는 함수를 만들어라.

    처음 문제를 풀땐 Collection protocol이 적용되었으니 .count 메서드를 활용해서 문제를 해결했다.
    하지만 Collection protocol이 적용되지 않았을 경우도 생각해서 문제를 해결해야 하는데, 그 방법은 Runner's techique 라는 방법이 있다.
    Runner's techique는 연결 리스트를 순회할 때 두 개의 포인터를 사용하는 기술이다. 보통 두 개의 포인터 중 하나의 다른 하나보다 앞서게 하여 리스트를 한 번만 순회하지만, Runner's technique를 사용하면 리스트를 한 번 더 순회하여 원하는 노드를 찾을 수 있다.
    이를 통해 시간 복잡도를 개선할 수 있다.
    while문에서, 다음 노드를 nextFast에 바인딩한다. 만약 다음 노드가 존재한다면, fast를 nextFast의 다음 노드로 업데이트하여 리스트를 두 번 탐색한다. slow 포인터는 한 번만 업데이트된다. 

// Runner's techique 활용 전 / Collection Protocol 적용 필수 
func getMiddle<T>(_ list: LinkedList<T>) -> Node<T>? { 
	var middleCount = Int(ceil(Double(list.count + 1)/ Double(2)))
	var count = 1 
	var currentNode = list.head
	
	while (currentNode?.next) != nil { 
		count += 1
		currentNode = currentNode?.next
		if count == middleCount { 
			return currentNode
		}
	}
	return currentNode
}
// Runner's techique 활용 후 / Collecton Protocol 적용 필수 x
func getMiddle<T>(_ list: LinkedList<T>) -> Node<T>? { 
	var slow = list.head
	var fast = list.head 
	
	// slow 한 번 이동할때 fast 두 번 이동 -> 1:2 비율 
	while let nextFast = fast?.next { 
		fast = nextFast.next
		slow = slow?.next 
	}
	return slow
}

Reverse a linked list

  • 연결리스트의 구조는 변경하지 않고 연결리스트의 순서를 바꾸는 함수를 만들어라.

    이러한 함수는 Swift 기본 함수처럼 LinkedList 내부 함수로 만드는 것이 더 효율적일 것 같다. 

extension LinkedList { 
	mutating func reverse() { 
		tail = head
		var prev = head
		var current = head?.next
		prev?.next = nil
		
		while current != nil { 
			let next = current?.next
			current?.next = prev 
			prev = current
			current = next 
		}
		head = prev
	}
}

Merge two lists

  • 두 개의 정렬된 연결 리스트를 활용해서 하나의 정렬된 연결 리스트로 병합하라.

    두 함수 비교시 비교연산자를 활용하기 때문에 <\T> 형의 Comparable 프로토콜을 채택해야 한다.

    • 두 연결리스트의 isEmpty 상태를 확인
      최초 head 값 선정
    • 둘 중 다 순회 돌기 전까지 while문 실행
    • 남은 리스트 값 이어 붙이기
// 제너릭을 활용하기 앞서 <T>의 Comparable 프로토콜 선언해줘야 한다!!
func mergeSorted<T: Comparable>(_ left: LinkedList<T>, _ right: LinkedList<T>) -> LinedList<T> { 
	guard !left.isEmpty else { 
		return right
	}
	
	guard !right.isEmpty else { 
		return left
	}
	
	var newHead: Node<T>? 
	// 순회 돌 변수
	var tail: Node<T>?
	
	var currentLeft = left.head 
	var currentRight = right.head
	
	if let leftNode = currentLeft, let rightNode = currentRight { 
		if leftNode.value < rightNode.value { 
			newHead = leftNode
			currentLeft = leftNode.next
		} else { 
			newHead = rightNode 
			currentRight = rightNode.next
		}
		tail = newHead
	} 
	
	while let leftNode = currentLeft, let rightNode = currentRight { 
		if leftNode.value < rightNode.value { 
			tail?.next = leftNode
			currentLeft = leftNode.next
		} else { 
			tail?.next = rightNode
			currentRight = rightNode.next
		}
		tail = tail?.next
	}
	
	if let leftNode = currentLeft { 
		tail?.next = leftNode
	}
	
	if let rightNode = currentRight { 
		tail?.next = rightNode
	}
	
	var list = LinkedList<T>()
	list.head = newHead
	list.tail = {  
		while let next = tail?.next { 
			tail = next
		}
		return tail
	}() 
	
	return list
}

Remove all occurrences

  • Int형 숫자를 파라미터로 주어졌을 때 파라미터와 같은 숫자는 모두 삭제해라.

    reverse() 함수와 마찬가지로 내부함수로 실행하는 것이 효율적이다.
    기존 LinkedList를 돌면서 주어진 값과 같은지 비교검사를 해야하기때문에 Equtable 프로토콜을 채택해야 한다.

extension LinkedList where Value: Equtable { 
	mutating func removeAll(_ value: Value) { 
		while let head = self.head, head.value == value { 
			self.head = head.next 
		}
		
		var prev = head
		var current = head?.next
		while let currentNode = current { 
			guard currentNode.value != value else { 
				prev?.next = currentNode.next 
				current = prev?.next 
				continue
			}
			prev = current
			current = current?.next 
		}
		tail = prev
	}
}

출처(참고문헌)

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.

profile
전성훈
이전 포스트

[Data Structure / Algorithms] Linked List (1)

다음 포스트

[Data Structure / Algorithms] Doubly Linked List

0개의 댓글