[Data Structure] Array & Linked List(2) - Implementation

이번 포스팅에선 List ADT 중 Linked List를 Swift를 통해 구현해 보자. 

개념에 관해 보고 싶다면 이전 포스팅을 참고 바란다.

 

전체적인 구현은 여기에서 확인 할 수 있다. 

https://github.com/jungseokyoung-cloud/Data-Structure

GitHub - jungseokyoung-cloud/Data-Structure: Data Structures implemented with Swift

 

Simple Linked List 

기본적인 프로퍼티는 다음과 같이 구성된다. 

struct SimpleLinkedList<T> {
	
	typealias Node = SimpleLinkedNode<T>
	
	private var head: Node?
	private weak var tail: Node?
	
	var isEmpty: Bool { head == nil }
	
	init() { }
}

 

"마지막에 원소 뒤에 삽입"하기 위해선, 마지막 원소를 탐색해야 한다. 

하지만, 후속 노드만 알 수 있는 단순 연결 리스트 특성상 마지막 원소 탐색에 O(N) 시간이 소요된다. 

 

따라서, 마지막 원소 탐색을 O(1)으로 하기 위해 tail이라는 마지막 노드의 포인터를 프로퍼티로 추가해주었다.  

 

또한, head노드의 경우, reference count를 1로 유지해주기 위해, 강한 참조를 사용했지만, tail의 경우 이전 노드에 의해 이미 reference count가 1이다.

따라서, tail을 약한 참조로 reference count를 증가시키지 않도록 구현했다.

 

Simple Linked Node 

우선, 단순 연결리스트의 노드는 다음과 같다. 

final class SimpleLinkedNode<T> {
	var data: T
	var next: SimpleLinkedNode<T>?
	
	// MARK: - Initalizers
	init(data: T, next: SimpleLinkedNode<T>? = nil) {
		self.data = data
		self.next = next
	}
}

노드의 경우에는 Swift의 ARC를 이용하기 위해 class로 구현했다.

Swift의 class는 ARC에 의해 해당 class에 대한 reference count가 0일 경우 메모리에서 해제된다. 
따라서, 이전 노드가 해당 노드를 안가리키게 되면 별다른 코드 없이 메모리에서 해제가 가능하다.

 

Insert Methods

append(_:)

// O(1)
mutating func append(_ data: T) {
	guard !isEmpty else {
		// 연결리스트가 빈 경우, head로 지정
		head = Node(data: data)
		tail = head
		return
	}

	tail?.next = Node(data: data)
	tail = tail?.next
}

append(_:)메서드는 연결리스트의 가장 맨뒤에 원소를 추가한다. 

 

비어 있는 경우라면

• 새로운 노드를 head, tail로 지정한다.

비어 있지 않다면,

• tail의 next를 "새로운 노드"로 지정한 후, 
• tail을 "새로운 노드"로 지정한다.

 

insert(_:after:)

// O(1)
mutating func insert(_ data: T, after node: Node) {
	guard !isEmpty && node !== tail else {
		append(data)
		return
	}
	
	let nextNode = node.next
	node.next = Node(data: data, next: nextNode)
}

insert(_:after:)메서드는 node뒤에 새로운 노드를 추가한다. 

 

비어 있거나 node와 tail과 같다면,

• append(:_)를 수행한다.

반대의 경우,

• "새로운 노드"의 next를 기존의 node의 next로 지정해준다.
• node의 next를 "새로운 노드"로 지정한다.

 

Delete Methods

pop_front()

@discardableResult
// O(1)
mutating func pop_front() -> T? {
	defer { head = head?.next }
	
	return head?.data
}

 

pop_front()메서드의 경우에는 head를 head의 next로 지정해 준다. 즉, head를 그다음 노드로 지정한다.

 

만약 defer를 사용하지 않는다면, head?.data를 저장하기 위한 추가적인 변수가 필요하다. 

로직 자체도 간편하며, 추가적인 스택 메모리 할당이 불필요하다 판단해 defer를 사용했다.

defer는 함수가 스택 메모리 영역에서 해제되기 전에 수행된다. 즉, return까지 완료된 후에 수행된다.

 

마지막 노드(head === tail)인 경우를 살펴보자!

만약 tail을 강한 참조로 가져갔다면, head와 tail에 의해 마지막 노드의 reference count는 2이다. 

하지만, tail을 약한 참조로 가져갔기 때문에, reference count는 1로 head만 해제해 주면 해당 노드는 자연스레 삭제된다. 

 

이때, 마지막 원소라면, head?.next는 nil이기 때문에, head = nil이 된다.

 

pop_back()

@discardableResult
// O(N)
mutating func pop_back() -> T? {
	guard !isEmpty else { return nil }
	guard head !== tail else { return pop_front() }
	
	var node = head
	
	while node?.next !== tail {
		node = node?.next
	}
	
	defer { node?.next = nil; tail = node }

	return node?.next?.data
}

pop_back() 메서드는 연결리스트의 가장 마지막 노드를 제거한다.

앞서 말했듯, 단순 연결 리스트는 후속 노드만 와의 관계를 나타내기 때문에, tail의 이전 노드를 알아야 한다. 

이를 탐색하는 과정에서 O(N)이 소요된다.

 

노드가 하나 밖에 안 남았다면(head === tail)

• pop_front()와 pop_back()의 동작은 동일해진다. (남은 노드가 1개이기 때문에)
• 하지만, 마지막 노드는 head에서 참조한 reference count를 감소시켜야 하기에 pop_front()를 호출한다.

반대의 경우

• tail의 이전 노드를 탐색한 후, 
• 삭제할 노드의 reference count를 감소시키기 위해, node?.next = nil로 지정한다.
• 마지막으로 tail을 node(tail의 이전 노드)로 갱신해 준다.

 

remove(after:)

@discardableResult
// O(1)
mutating func remove(after node: Node) -> T? {
	guard !isEmpty && node !== tail else { return nil }
	
	if tail === node.next { tail = node }
	
	defer { node.next = node.next?.next }

	return node.next?.data
}

remove(after:)메서드는 node뒤의 노드를 제거해 리턴합니다.

 

만약, 비어있거나, node가 tail 인 경우,

• nil을 리턴한다.

node.next가 tail인 경우, 즉 마지막 원소를 삭제하는 경우,

• pop_back()을 호출해도 되지만, O(N)이기에 호출하지 않는다. 
• 대신, tail을 node로 갱신해 준다.

이후, 

• node의 next를 삭제할 노드(node.next)의 next로 지정한다.

 

Find Method

find method에 앞서, Linked List는 순차적으로 iterate 할 수 있기 때문에, Sequence를 채택했다. 

// MARK: - Sequence
extension SimpleLinkedList: Sequence {
	public func makeIterator() -> SimpleLinkedListIterator<T> {
		return SimpleLinkedListIterator(head: self.head)
	}
}

public struct SimpleLinkedListIterator<T>: IteratorProtocol {
	var current: SimpleLinkedNode<T>?
	
	init(head: SimpleLinkedNode<T>?) {
		self.current = head
	}
	
	mutating public func next() -> SimpleLinkedNode<T>? {
		guard let thisCurrent = current else { return nil }
		
		defer { self.current = thisCurrent.next }
		return current
	}
}

 

traversal() 

func traversal() -> [T] {
	var values: [T?] = []
	self.forEach { values.append($0.data) }
	
	return values.compactMap { $0 }
}

traversal()메서드는 연결리스트의 모든 노드를 순회에 데이터만 리스트 형태로 리턴한다. 

 

앞서, Sequence를 채택했기에 forEach, map, first 등과 같은 고차함수를 사용할 수 있다.

 

node(at:) 

func node(at index: Int) -> Node? {
	return self.enumerated()
		.first { $0.offset == index }
		.map { $0.element }
}

index에 해당하는 node를 리턴한다.

 

Circular Linked List

Circular Linked List는 Simple Linked List로 구현했다. 

따라서, 대부분의 메서드는 Simple Linked List와 동일하다.  하지만, 양 끝단에서의 노드 추가 및 삭제는 다르기에 이들만 살펴보자. 

우선, 기본적인 프로퍼티는 다음과 같다. 

public struct CircularLinkedList<T> {
	public typealias Node = SimpleLinkedNode<T>
	
	private var head: Node?
	private weak var tail: Node?
	
	public var isEmpty: Bool { head == nil }
	
	public init() { }
}

 

Insert Methods 

append(_:)

// O(1)
mutating func append(_ data: T) {
	guard !isEmpty else {
		// 연결리스트가 빈 경우, head로 지정
		head = Node(data: data)
		tail = head
		return
	}
	
	tail?.next = Node(data: data)
	tail = tail?.next
	tail?.next = head
}

• tail?.next를 "새로운 노드"로 지정하고, 
• tail을 "새로운 노드"로 갱신한다. 
• 원형 연결 리스트이기에, tail?.next를 head로 지정한다.

 

Delete Methods

pop_front()

@discardableResult
// O(1)
mutating func pop_front() -> T? {
	defer {
		if head === tail { head = nil }
		
		head = head?.next
		tail?.next = head
	}
	
	return head?.data
}

노드가 한 개 남을 경우를 살펴보자. 

단순 연결 리스트에선 head.next가 nil이기 때문에, 추가적인 로직이 필요하지 않았지만, 

원형 연결 리스트에선 head.next는 자기 자신을 가리키게 된다. 

head.next는 tail이고, tail의 next가 head를 가리키기 때문에, head.next는 자기 자신을 가리킨다.

 

따라서, 추가적인 if문을 통해 노드가 한 개 남을 경우를 처리해 준다.

마지막 원소라면(head === tail),

• head = nil을 해주어 reference count를 0으로 만들어 준다. 

만약 tail이 강한 참조였다면, reference count는 4가 된다. (head, head.next, tail, tail.next) 
또한, head.next = tail이고 tail.next가 head이기 때문에 순환 참조가 발생한다. 

 

아니라면,

• head를 head의 next로 지정하고, 
• tail.next를 새로운 head로 지정한다.

 

pop_back()

@discardableResult
// O(N)
mutating func pop_back() -> T? {
	guard !isEmpty else { return nil }
	guard head !== tail else { return pop_front() }
	
	var node = head
	
	while node?.next !== tail {
		node = node?.next
	}
	
	defer { node?.next = head; tail = node }
	
	return node?.next?.data
}

나머지는 단순 연결리스트와 같으며, 새로운 tail 노드의 next를 head로 지정해 준다.

 

Double Linked List

public struct DoubleLinkedList<T> {
	public typealias Node = DoubleLinkedNode<T>
	
	private var head: Node?
	private weak var tail: Node?

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

이 역시 마찬가지로 노드가 하나 남았을 때, 쓸 때 없는 reference count를 줄이기 위해 tail을 약한 참조를 사용했다.

 

Double Linked Node

이중 연결 리스트는 이전과 후속노드 둘 다 접근이 가능하기 때문에, DoubleLinkedNode를 따로 만들어 주었다. 

노드의 삽입 및 삭제 외에는 단순 연결 리스트와 같기에 이들 위주로 살펴보자.

public final class DoubleLinkedNode<T> {
	public var prev: DoubleLinkedNode<T>?
	public var next: DoubleLinkedNode<T>?
	public var data: T
	
	public init(data: T, prev: DoubleLinkedNode<T>? = nil, next: DoubleLinkedNode<T>? = nil) {
		self.data = data
		self.prev = prev
		self.next = next
	}
}

 

Insert Methods

append(_:) 

mutating func append(_ data: T) {
	guard !isEmpty else {
		...
	}
	
	let newNode = Node(data: data)
	tail?.next = newNode
	newNode.prev = tail
	tail = newNode
}

append(:_)의 경우 새로운 노드를 연결 리스트 뒤에 추가하며, isEmpty에서의 동작은 단순 연결 리스트와 같다. 

• tail의 next를 "새로운 노드"로 지정한다. 
• "새로운 노드"의 prev를 tail로 지정한 후, 
• tail을 "새로운 노드"로 갱신한다.

 

insert(_:after:)

mutating func insert(_ data: T, after node: Node) {
	guard !isEmpty && node !== tail else {
		...
	}
	
	let newNode = Node(data: data)
	newNode.next = node.next
	newNode.prev = node
	
	node.next?.prev = newNode
	node.next = newNode
}

중간에 삽입하는 경우 역시 isEmpty이거나 node가 tail인 경우 append(_:)를 수행한다.

node와 node.next 사이에 새로운 노드를 삽입하는 과정은 다음과 같다. 

• "새로운 노드"의 next를 node의 next로 지정한다. 
• "새로운 노드"의 prev를 node로 지정한다. 
• node.next의 prev와 node의 next를 "새로운 노드"로 지정한다. 

 

Delete Methods

pop_front()

@discardableResult
// O(1)
mutating func pop_front() -> T? {
	defer {
		head = head?.next
		head?.prev = nil
	}
	
	return head?.data
}

head를 head의 다음 노드로 갱신한 후, prev(기존의 head)를 nil을 선언해 메모리에서 해제해 준다. 

 

pop_back()

@discardableResult
// O(1)
mutating func pop_back() -> T? {
	guard !isEmpty else { return nil }
	guard head !== tail else { return pop_front() }

	defer {
		tail = tail?.prev
		tail?.next = nil
	}
	
	return tail?.data
}

단일 연결 리스트는 후속 노드만 알 수 있어 tail의 이전 노드를 탐색하면서 O(N)이 소요되었다.

하지만, 이중 연결 리스트는 이전 노드도 알 수 있기 때문에 O(1)이 소요된다. 

 

우선, tail을 이전 노드로 갱신한 후, next(기존의 tail)을 nil을 선언해 메모리에서 해제해준다.

 

remove(after:_)

@discardableResult
// O(1)
mutating func remove(after node: Node) -> T? {
	guard node !== tail else { return nil }
	guard !isEmpty && node.next !== tail else { return pop_back() }
	
	let removeNode = node.next
	
	node.next = removeNode?.next
	removeNode?.next?.prev = node
	
	return removeNode?.data
}

node.next 노드를 제거하기에 다음과 같이 수행된다.

• node.next를 "삭제할 노드"의 next로 지정한다. 
• "삭제할 노드"의 next의 이전을 node로 지정한다.