주제: 단일 연결 리스트 기본 구현
Linked Lists는 선형적이고, 단방향적인 sequence 정렬된 값들의 collection이다.
What is Linked Lists
- Linked Lists는 list의 앞에서 삽입과 삭제는 선형시간을 가진다.
- 신뢰할 수 있는 성능 특성을 가지고 있다.
- Linked list 는 nodes들의 연결 묶음이다.
Node Code
- Node는 값을 가지고 있다.
- Node는 다음 노드를 참조하고 있다. 마지막 노드는 nil value를 갖는다.
public class Node<Value> {
public var value: Value
public var next: Node?
public init(value: Value, next: Node? = nil) {
self.value = value
self.next = next
}
}
extension Node: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "\(value) 끝!"
}
return "\(value) -> " + String(describing: next) + " "
}
}extension Node: CustomStringConvertible-> Node 출력시 나오는 형태를 Custom 하는 protocol
LinkedList Code
- head와 tail을 선언할 수 있는 변수를 만들어서 LinkedList의 뼈대를 만든다.
public struct LinkedList<Value> {
public var head: Node<Value>?
public var tail: Node<Value>?
public init() { }
public var isEmpty: Bool {
head == nil
}
}
extension LinkedList: CustomStringConvertible {
public var description: String {
guard let head = head else {
return "Empty List"
}
return String(describing: head)
}
}Adding Values to the list
push: List의 앞에 값을 더한다.append: List의 마지막에 값을 더한다.insert(after: ): 특정 노드 앞에 값을 더한다.- push
head의 값을 더하고, 기존 head값을 새로운 head의 next에 대입한다.
tail이 nil 값일땐 (처음 값 대입 시) 새로운 head을 tail에 대입해줘서 처음 최초 값이 head이자 tail인 상태로 되게 선정한다.
시간 복잡도: O(1)
public mutating func push(_ value: Value) {
head = Node(value: Value, next: head)
if tail == nil {
tail = head
}
}- append
Linked List의 값이 없는 상태일 땐 push 함수를 불러드린다.
기존 tail의 next 값(nil)의 새롭게 들어온 값을 포함한 Node를 선언하고
새롭게 선언된 tail.next(Node(value, next: nil)) 값을 기존 tail에 덮어쓴다.
시간 복잡도: O(1)
public mutating func append(_ value: Value) {
guard !isEmpty else {
push(value)
return
}
tail!.next = Node(value: Value)
tail = tail!.next
}- insert(after: )
func node(at index: Int)를 통해 인덱스 값을 받고 그 인덱스값이 나타내는 노드 값을 반환한다.
새롭게 추가할 노드의 위치가 tail일 경우 append 함수를 불러온다.
새롭게 받은 값과 기존 노드의 next을 받는 새로운 node를 생성 후, 새롭게 생성된 노드를 기존 node의 next에 대입 해준다.
node(at:) 시간 복잡도: O(n)
insert(after: ) 시간 복잡도: O(1)
public func node(at index: Int) -> Node<Value?> {
var currentNode = head
var currentIndex = 0
while currentNode != nil && currentIndex < index {
currentNode = currentNode!.next
currentIndex += 1
}
return currentNode
}@discardableResult public mutating func insert(
_ value: Vlaue,
after node: Node<value>
) -> Node<Value> {
guard tail !== node else {
append(value)
return tail!
}
node.next = Node(value: value, next: node.next)
return node.next!
}| push | append | insert(after:) | node(at:) |
|---|---|---|---|
| O(1) | O(1) | O(1) | O(i) |
Removing values from the list
pop: list의 맨 앞 값을 삭제한다.removeLast: list의 마지막 값을 삭제한다.remove(after: ): list의 특정 위치 값을 삭제한다.- pop
return으로 head의 값을 반환하고 defer로 head의 node을 head의 next 노드로 변경한다.
만약 head만 있는 linkedList 값을 뽑아냈으면 tail을 nil로 대입 시켜준다.
"swift ARC로 인해 기존 head가 참조하는 것이 없으면 자동 메모리 해제 된다."
@discardableResult public mutating func pop() -> Value? {
defer {
head = head?.next
if isEmpty {
tail = nil
}
}
return head?.value
}- removeLast
head가 nil이면 제거할것이 없으므로 nil 반환
node의 구성이 하나면, removeLast의 작동방식은 pop과 동일하다. 왜냐하면 pop은 head와 tail의 참조를 헨들링할 수 있기 때문이다.
current.next 가 nil이 되기 전까지 while문을 실행 시키고, current가 tail이 되기 전에 tail전 node가 prev가 되고 tail이 current가 된다.
prev.next를 nil로 선언 후 tail을 prev로 선언하면 기존 tail의 node값은 초기화 된다.
@discardableResult public 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
cuerrent = next
}
prev.next = nil
tail = prev
return current.value
}- remove(after: )
제거되는 node.next가 tail일 경우 기존 노드를 tail로 선언해준다.
그렇지 않다면 제거할 노드의 값을 방출하고 제거할 노드의 next 노드를 기존 노드의 next로 할당시켜서 기존 노드의 next 노드를 할당 해제 시켜준다.
@discardalbeResult public mutating func remove(after node: Node<Value>) -> Value? {
defer {
if node.next == tail {
tail = node
}
node.next = node.next?.next
}
return node.next?.value
}| pop | removeLast | remove(after:) |
|---|---|---|
| O(1) | O(n) | O(n) |
출처(참고문헌)
제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.
감사합니다.
