LinkedList
Linked List
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 를 참조했습니다.