반응형
오늘은 Linked List
에 대해서 다뤄보고자 합니다
kodeco
사이트(클릭클릭👆🏻) kodeco에 들어가면 다양한 자료들을 볼 수 있으니 강추👍🏻👍🏻👍🏻👍🏻👍🏻 드립니다
강의보단 책이 좋다는 평이 있어서 저도 책으로 구매하였답니다 :)
Linked List
Linked List는 선형으로 이루어진 단방향 순서로 나열된 배열인
값으로 이루어져 있습니다
Linked List는 배열(Array)에 비해서 장점이 몇 가지 있습니다
목록 앞에서 삽입과 제거가 됩니다
성능적으로 안정적입니다
위 다이어그램에서 알 수 있듯이 Linked List는 일련의 노드들로 구성된 사슬을 나타내고 있습니다
노드에는 두 가지 역할이 있습니다
값을 저장합니다
다음 노드를 참조하는 참조를 가지고 있습니다
nil 값은 리스트의 끝을 나타내고 있습니다
Noded에서는 12의 값을 저장하고 있는걸 볼 수 있습니다
Linked List를 구현하고 그것과관련하여 시간복잡도와 copy-on-write를 구현해보고자 합니다
Node
import UIKit
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
}
}
//사용자 객체를 문자열로 표현할 수 있는데 사용하고 있음
//프로토콜을 준수하는 타입은 description이라는 연산 프로퍼티를 제공
//문자열 표현을 정의할 수 있음
//디버깅이나 로깅 목적으로 객체를 읽기 쉬운 문자열 변환을 할 때 사용
extension Node: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next) + " "
}
}
print("creating and linking nodes")
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
node1.next = node2
node2.next = node3
//1 -> 2 -> 3
print(node1)
세 개의 노드를 생성하고 연결한것을 확인할 수 있습니다
Example of creating and linking nodes --
1->2->3
import UIKit
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
}
}
//사용자 객체를 문자열로 표현할 수 있는데 사용하고 있음
//프로토콜을 준수하는 타입은 description이라는 연산 프로퍼티를 제공
//문자열 표현을 정의할 수 있음
//디버깅이나 로깅 목적으로 객체를 읽기 쉬운 문자열 변환을 할 때 사용
extension Node: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next) + " "
}
}
print("creating and linking nodes")
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
node1.next = node2
node2.next = node3
//1 -> 2 -> 3
print(node1)
public struct LinkedList<Value> {
//연결된 목록의 시작 끝을 저장하도록 head / tail 프로퍼티를 선언한다
public var head: Node<Value>?
public var tail: Node<Value>?
public init() {}
//연결할 노드들이 아예 없는 빈 리스트라면 isEmpty는 true로 변환된다
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)
}
}
//⭐️CustomStringConvertible
//struct Point {
// let x: Int, y: Int
//}
//
//extension Point: CustomStringConvertible {
// var description: String {
// return "(\(x), \(y))"
// }
//}
링크드 리스트를 추가해서 연결된 목록에 각각 첫 번째 노드와 마지막 노드를 참조하는 head와 tail이 있습니다
이렇게 선언해 준 후 목록에 값을 추가해볼까요?
push
목록 앞에 값을 추가
append
목록 끝에 값을 추가
insert(after:)
특정 목록 노드 뒤에 값을 추가
빈 목록에 push하게되면 head와 tail 둘다 새 노드를 향하고 있을겁니다
public mutating func push(_ value: Value) {
head = Node(value: value, next: head)
if tail == nil {
tail = head
}
}
링크드리스트 안에 Push method를 선언해줍니다
print("⭐️push⭐️")
//generic 사용해서 타입 지정
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("✏️list : \(list)")
//⭐️push⭐️
//✏️list : 1 -> 2 -> 3
처음 3을 추가했을 때
3
그다음 2를 push하게 되면
2를 가진 새로운 노드를 생성하게되고
이 노드의 next속성이 현재 머리인 노드3을 가리키게 합니다
2 - 3
그 다음 1을 push하게 되면
동일하게 next 속성이 현재 hea인 노드 2를 가리키게 됩니다
그래서 최종적으로
1 - 2 - 3
으로 출력이 되는걸 볼 수 있습니다
append Operations
|
public mutating func append(_ value: Value) {
guard !isEmpty else {
push(value)
return
}
tail!.next = Node(value: value)
tail = tail!.next
}
링크드리스트 안에 확장 메서드를 넣었습니다
위 코드를 분석하자면
guard문을 통해서 빈 리스트라면 else구문에 들어가서
value를 하나 push하여 새로운 값의 리스트의 머리를 추가합니다
이렇게되면 값이 1개밖에 없기 때문에 꼬리와 머리 둘 다 새 노드를 가리키게 됩니다
그리고 만약에 빈 리스트가 아닌경우에는 꼬리 다음에 새로운 노드를 생성합니다
그리곤 꼬리 다음인 새로운 노드를 꼬리로 변경해줍니다
example(of: "append") {
var list = LinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)
print(list)
}
//⭐️append⭐️
//1 -> 2 -> 3
insert(after:)
|
특정 목록 노드 뒤에 값을 추가
우선 코드를 짜기전 과정에 대해서 알아봅시다
리스트에서 특정 노드를 찾고 새로운 노드를 삽입합니다
//주어진 인덱스 기준으로 리스트에서 노드를 검색
public func node(at index: Int) -> Node<Value>? { //return nil이 될 수도 있음 -> optional type
//머리에서 시작
var currentNode = head
var currentIndex = 0
//머리에서 시작하여 인덱스를 하나씩 이동시키며 입력한 인덱스에 도달할 때까지 반복
//빈 리스트이거나 범위를 벗어난 인덱스는 nil을 반환
while currentNode != nil && currentIndex < index {
currentNode = currentNode!.next
currentIndex += 1
}
return currentNode
}
@discardableResult //메서드의 반환 값을 호출자가 무시할 수 있음 컴파일러가 경고를 표시하지 않음
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
//꼬리와 노드와 동일하지 않을때 else문이 아닌 아래 node.next 시행됨
guard tail !== node else {
//만약 꼬리와 node가 동일하다면 else 구문에 들어와서 확장 메서드를 사용하게됨
append(value)
//꼬리 업데이트 작용이됨
return tail!
}
//그렇지 않을 때 노드를 단순히 새로 만들면서 연결만 하게되는걸 볼 수 있음
node.next = Node(value: value, next: node.next)
return node.next!
}
이렇게 선언해준 후
특정 노드에 추가해보도록합시다
print("inserting at a particular index")
var list2 = LinkedList<Int>()
list2.push(3)
list2.push(2)
list2.push(1)
print("Before inserting: \(list2)") //Before inserting: 1 -> 2 -> 3
var middleNode = list2.node(at: 1)! //미들노드 2를 가리키고 있음
for _ in 1...4 {
middleNode = list2.insert(-1, after: middleNode) //2번째 뒤에 -1이 추가되는 구조
}
print("After inserting: \(list2)")
//1 2 -1 3
현재 간단히 한 번 사이클 돌린걸 주석처리로 작성했습니다
나머지 또한 for구문을 거치면서 어떻게 변하는지 작성해보겠습니다
이런 순서로 링크드 리스트에서 1 2 -1 3
의 1번째 노드는 2 입니다
한 바퀴 포문을 더 돌리게되면
1 2 -1 -1 3
이됩니다
그다음 3번 째 for문입니다
middleNode 즉 1번째 노드는
2 입니다
첫번째라고해서 제일앞이 아닌 배열처럼 두번째를 가지고오면 됩니다
포문을 거치면서
1 2 -1 -1 -1 3
으로 변경된것을 확인할 수 있습니다
그리곤 마지막 포문을 지나게되면
1 2 -1 - 1 - 1 -1 3
으로 변경된걸 확인할 수 있습니다
성능에 대해서 알아보자면
단순히 추가 확장 푸시의 경우엔 시간 복잡도가 O(1)
한 요소만 접근하기 대문에 이럴 수 있습니다
하지만 마지막 node(at:)의 경우
인덱스를 while문을 돌리며 접근하고 있기 때문에
O(i)가 나올 수 밖에 없습니다
Removing values from the list
pop
리스트에서 앞에 있는 값을 제거합니다
removeLast
리스트에서 마지막 값을 제거합니다
remove(at:)
원하는 요소에 들어가서 제거할 수 있습니다
pop
pop 코드에 대해서 분석해볼까요?
@discardableResult
public mutating func pop() -> Value? {
defer {
head = head?.next
if isEmpty {
tail = nil
}
}
return head?.value
}
여기서 눈 여겨 볼 만한건
defer입니다
함수가 종료되기 직전 실행이되는데
그 안에서 head의 다음 헤드를 업데이트 합니다
첫번째 요소를 제거하고 헤드를 다음 요소로 변경해주는 작업입니다
만약 리스트가 비어있다면 tail을 nil로 할당해줍니다
그리곤 현재 head 노드 값을 반환합니다
print("⭐️pop⭐️")
var list3 = LinkedList<Int>()
list3.push(3)
list3.push(2)
list3.push(1)
print("Before popping list: \(list3)")
let poppedValue = list3.pop()
print("After popping list: \(list3)")
print("Popped value: " + String(describing: poppedValue))
//⭐️pop⭐️
//Before popping list: 1 -> 2 -> 3
//After popping list: 2 -> 3
//Popped value: Optional(1)
pop을하게되면
도느 헤드를 1 -> 2로 변경되는걸 볼 수 있습니다
그리곤 기존 head 노드는 더이상 참조되지 않는걸 확인할 수 있습니다
이건 스위프트에서 ARC가 있기에 가능한 부분입니다
그래서 해당 노드를 메모리에서 자동적으로 해제가 가능하구용
removeLast operations
@discardableResult
public mutating func removeLast() -> Value? {
guard let head = head else { return nil } //guard let 구문을 사용해 안전하게 해제시켜준 후
guard head.next != nil else { return pop() } //리스트 크기가 하나이면 pop()을 호출하여 제거해준다
//리스트 크기가 2개 이상이면 여길 실행
//우선 동일하게 head를 넣어준 후
var prev = head
var current = head
//current를 옮기며 변경시켜준다 마지막 노드로 이동 합니다
while let next = current.next {
prev = current
current = next
}
//prev는 마지막 앞이므로 next를 사용해 nil을 할당해준다
prev.next = nil
//그리곤 마지막 앞의 노드를 꼬리로 잡아주고
tail = prev
//마지막 제거된 노드의 값을 반환하고 있습니다
return current.value
}
그리고 작성한 코드를 실행해 봅시당
print("⭐️removing the last node⭐️")
var list4 = LinkedList<Int>()
list4.push(3)
list4.push(2)
list4.push(1)
print("Before removing last node: \(list4)")
let removedValue = list4.removeLast()
print("After removing last node: \(list4)")
print("Removed value: " + String(describing: removedValue))
//⭐️removing the last node⭐️
//Before removing last node: 1 -> 2 -> 3
//After removing last node: 1 -> 2
//Removed value: Optional(3)
remove(afer:)operation
좀전에 배웠던 작업과 비슷하게 수행하게 됩니다
특정 노드를 제거하려면 그 노드의 이전 노드를 찾아야합니다
이전 노드와 다음 노드 포인터를 제거하고 전 후 노드를 이어주는 next를 잘 이어야 하겠죠?
그리고 참조가 끊어지면 자동적으로 참조 카운팅이 사라지면서 메모리에서 해제됩니다
@discardableResult
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
}
다음다음 노드를 넣어주고
다음 노드를 해제시키는걸 볼 수 있습니다
print("⭐️removing a node after a particular node⭐️")
var list5 = LinkedList<Int>()
list5.push(3)
list5.push(2)
list5.push(1)
print("Before removing at particular index: \(list5)")
let index = 1
let node = list5.node(at: index - 1)!
let removedValue1 = list5.remove(after: node)
print("After removing at index \(index): \(list5)")
print("Removed value: " + String(describing: removedValue1))
//⭐️removing a node after a particular node⭐️
//Before removing at particular index: 1 -> 2 -> 3
//After removing at index 1: 1 -> 3
//Removed value: Optional(2)
코드 정리
import UIKit
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
}
}
//사용자 객체를 문자열로 표현할 수 있는데 사용하고 있음
//프로토콜을 준수하는 타입은 description이라는 연산 프로퍼티를 제공
//문자열 표현을 정의할 수 있음
//디버깅이나 로깅 목적으로 객체를 읽기 쉬운 문자열 변환을 할 때 사용
extension Node: CustomStringConvertible {
public var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + String(describing: next) + " "
}
}
print("creating and linking nodes")
let node1 = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
node1.next = node2
node2.next = node3
//1 -> 2 -> 3
print(node1)
//하나씩 연동하기엔 무리가 있어보임
public struct LinkedList<Value> {
//연결된 목록의 시작 끝을 저장하도록 head / tail 프로퍼티를 선언한다
public var head: Node<Value>?
public var tail: Node<Value>?
public init() {}
//연결할 노드들이 아예 없는 빈 리스트라면 isEmpty는 true로 변환된다
public var isEmpty: Bool {
head == nil
}
public mutating func push(_ value: Value) {
head = Node(value: value, next: head)
//공간이 하나일 때 head / tail 동일하게 만들어줌
if tail == nil {
tail = head
}
}
public mutating func append(_ value: Value) {
guard !isEmpty else {
push(value)
return
}
tail!.next = Node(value: value)
tail = tail!.next
}
//주어진 인덱스 기준으로 리스트에서 노드를 검색
public func node(at index: Int) -> Node<Value>? { //return nil이 될 수도 있음 -> optional type
//머리에서 시작
var currentNode = head
var currentIndex = 0
//머리에서 시작하여 인덱스를 하나씩 이동시키며 입력한 인덱스에 도달할 때까지 반복
//빈 리스트이거나 범위를 벗어난 인덱스는 nil을 반환
while currentNode != nil && currentIndex < index {
currentNode = currentNode!.next
currentIndex += 1
}
return currentNode
}
@discardableResult //메서드의 반환 값을 호출자가 무시할 수 있음 컴파일러가 경고를 표시하지 않음
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
//꼬리와 노드와 동일하지 않을때 else문이 아닌 아래 node.next 시행됨
guard tail !== node else {
//만약 꼬리와 node가 동일하다면 else 구문에 들어와서 확장 메서드를 사용하게됨
append(value)
//꼬리 업데이트 작용이됨
return tail!
}
//그렇지 않을 때 노드를 단순히 새로 만들면서 연결만 하게되는걸 볼 수 있음
node.next = Node(value: value, next: node.next)
return node.next!
}
@discardableResult
public mutating func pop() -> Value? {
defer {
head = head?.next
if isEmpty {
tail = nil
}
}
return head?.value
}
@discardableResult
public mutating func removeLast() -> Value? {
guard let head = head else { return nil } //guard let 구문을 사용해 안전하게 해제시켜준 후
guard head.next != nil else { return pop() } //리스트 크기가 하나이면 pop()을 호출하여 제거해준다
//리스트 크기가 2개 이상이면 여길 실행
//우선 동일하게 head를 넣어준 후
var prev = head
var current = head
//current를 옮기며 변경시켜준다 마지막 노드로 이동 합니다
while let next = current.next {
prev = current
current = next
}
//prev는 마지막 앞이므로 next를 사용해 nil을 할당해준다
prev.next = nil
//그리곤 마지막 앞의 노드를 꼬리로 잡아주고
tail = prev
//마지막 제거된 노드의 값을 반환하고 있습니다
return current.value
}
@discardableResult
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
}
}
extension LinkedList: CustomStringConvertible {
public var description: String {
guard let head = head else {
return "Empty list"
}
return String(describing: head)
}
}
//⭐️CustomStringConvertible
//struct Point {
// let x: Int, y: Int
//}
//
//extension Point: CustomStringConvertible {
// var description: String {
// return "(\(x), \(y))"
// }
//}
print("⭐️push⭐️")
//generic 사용해서 타입 지정
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("✏️list : \(list)")
//⭐️push⭐️
//✏️list : 1 -> 2 -> 3
print("⭐️append⭐️")
var list1 = LinkedList<Int>()
list1.append(1)
list1.append(2)
list1.append(3)
print(list1)
print("inserting at a particular index")
var list2 = LinkedList<Int>()
list2.push(3)
list2.push(2)
list2.push(1)
print("Before inserting: \(list2)") //Before inserting: 1 -> 2 -> 3
var middleNode = list2.node(at: 1)! //미들노드 2를 가리키고 있음
for _ in 1...4 {
middleNode = list2.insert(-1, after: middleNode) //2번째 뒤에 -1이 추가되는 구조
}
print("After inserting: \(list2)")
//1 2 -1 3
print("⭐️pop⭐️")
var list3 = LinkedList<Int>()
list3.push(3)
list3.push(2)
list3.push(1)
print("Before popping list: \(list3)")
let poppedValue = list3.pop()
print("After popping list: \(list3)")
print("Popped value: " + String(describing: poppedValue))
//⭐️pop⭐️
//Before popping list: 1 -> 2 -> 3
//After popping list: 2 -> 3
//Popped value: Optional(1)
print("⭐️removing the last node⭐️")
var list4 = LinkedList<Int>()
list4.push(3)
list4.push(2)
list4.push(1)
print("Before removing last node: \(list4)")
let removedValue = list4.removeLast()
print("After removing last node: \(list4)")
print("Removed value: " + String(describing: removedValue))
//⭐️removing the last node⭐️
//Before removing last node: 1 -> 2 -> 3
//After removing last node: 1 -> 2
//Removed value: Optional(3)
print("⭐️removing a node after a particular node⭐️")
var list5 = LinkedList<Int>()
list5.push(3)
list5.push(2)
list5.push(1)
print("Before removing at particular index: \(list5)")
let index = 1
let node = list5.node(at: index - 1)!
let removedValue1 = list5.remove(after: node)
print("After removing at index \(index): \(list5)")
print("Removed value: " + String(describing: removedValue1))
//⭐️removing a node after a particular node⭐️
//Before removing at particular index: 1 -> 2 -> 3
//After removing at index 1: 1 -> 3
//Removed value: Optional(2)
Performance analysis
pop / remover(after:)
은 요소를 찾아가서 끊기 때문에 시간복잡도가 O(1)이지만
마지막 제거는 while문으로 돌면서 마지막노드를 찾아가기 때문에
리스트가 많을 수록 시간이 늘어나기때문에
O(n)의 시간이 걸릴 수 밖에 없다
다음으로
Swift Collection protocol로 구현하는 방법입니다
연결리스트를 Collection protocol로 구현함으로 유한한 시퀀스로서 비파괴적인 순차 접근을 제공하고 서브스크립트를 통해서
배열처럼 인덱스로 접근이 가능하게됩니다
extension LinkedList: Collection {
// 1
public var startIndex: Index {
Index(node: head)
}
// 2
public var endIndex: Index {
Index(node: tail?.next)
}
// 3
public func index(after i: Index) -> Index {
Index(node: i.node?.next)
}
// 4
public subscript(position: Index) -> Value {
position.node!.value
}
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 }
}
}
}
거의 다 정리했는데 티스토리 오류때문에 다시 작성해야하는게 화가 나지만...
작성해보겠습니당..
설명하자면
좌 우 인덱스가 동일하면 false 즉 크기가 1이겠죵?
그게 아니라면 시퀀스를 통해서 노드에 추가하는걸 볼 수 있습니다
그리고 comparable을 통해서 비교하는걸 볼 수 있습니다
print("using collection")
var list6 = LinkedList<Int>()
for i in 0...9 {
list6.append(i)
}
print("List: \(list6)")
print("First element: \(list6[list6.startIndex])")
print("Array containing first 3 elements: \(Array(list6.prefix(3)))")
print("Array containing last 3 elements: \(Array(list6.suffix(3)))")
let sum = list6.reduce(0, +)
print("Sum of all values: \(sum)")
print("array 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)")
//array cow
//array1: [1, 2]
//array2: [1, 2]
//---After adding 3 to array 2---
//array1: [1, 2]
//array2: [1, 2, 3]
이렇게 copy-on-write도 가능하며
서브스크립트로 통해 배열처럼 작성하여 노드에 접근이 가능합니다
반응형
'서적 > 데이터 구조 및 알고리즘' 카테고리의 다른 글
| Kodeco | Swift의 데이터 구조 및 알고리즘 - Stack (0) | 2024.05.28 |
|---|---|
| Kodeco | Swift의 데이터 구조 및 알고리즘 - 복잡성 (0) | 2024.05.23 |