본 내용은 공부를 위한 내용으로 틀린내용이 있을수 있습니다.
이전에는 linked list insert 연산을 알아보았다.
이제는 Delete 연산에 대해서 살펴보자.
Delete 연산 역시 Insert 연산의 패턴만 안다면 쉽게 알수 있다.
다시한번 code 를 통해 현재 구현한 class 를 살펴보자,
interface Node {
data: string
link: Node
}
type NodeType = Node | null
class LinkedList {
constructor(head: NodeType = null) {}
insertLastNode(data: string) {
const newNode: Node = { data, link: null };
if(this.head == null) {
this.head = newNode
} else {
let tmp: NodeType = head
while(tmp != null) tmp = tmp.link
tmp.link = newNode
}
}
insertMiddleNode(preNode: Node, data: string) {
if (preNode == null) return
const newNode: Node = {data, link: null}
newNode.link = preNode.link
preNode.link = newNode
}
}
insert pattern 을 보면 간단하다.
새로운 newNode 를 만들고 newNode 를 연결한다.
Last Delete 는 연결된 마지막 노드의 연결을
해제하면 된다,
1) 밑의 Linked List 가 있다고 생각하자.
2) 마지막 Node 에 연결된 link 를 해제하고, link property 에 NULL 을 할당하면 된다.
이를 코드를 통해 구현해본다.
deleteLastNode() {
if (this.head == null) return
if(this.head.link == null) {
this.head = null
} else {
let pre: Node = this.head
let tmp: NodeType = this.head.link
while(tmp.link != null) {
pre = tmp
if (pre.link != null) tmp = pre.link
}
pre.link = null
}
}
code 를 하나씩 되짚어보자.
if (this.head == null) return
이 코드는 head 가 null 일때 해당 함수를 중단시키는 역할을 한다.
당연하게도 head 가 null 인데 다음 link 를 알수 없으며, linked list 가 구현되어 있지 않았다고 보아도 된다.
if (this.head.link == null) {
this.head = null
}
head.link 가 null 이면 head 가 참조하고 있는 Node 가 1개라는 것이다.
그러므로, 1개 있는 Node 를 삭제하니 this.head 는 null 이 된다.
else {
let pre: Node = this.head
let tmp: Node = this.head.link
}
이 코드에 pre 와 tmp 2개의 지역변수를 선언한다.
pre 는 마지막 노드 앞 노드를 가리키는 역할을 한다.
tmp 는 마지막 노드를 가리키는 역할을 한다.
다음을 보자.
else {
let pre: Node = this.head
let tmp: Node = this.head.link
while(tmp.link != null) {
pre = tmp
if (pre.link != null) tmp = pre.link
}
}
tmp.link 가 null 인지 확인하며 아니면,
pre 에 tmp 를 할당하고,
tmp 에 pre.link 를 할당한다.
이러한 반복문을 사용하면 pre 가 tmp 의 앞 Node 를 가리킬수 있으며, tmp 가 마지막 노드이면 반복을 멈춘다.
else {
let pre: Node = this.head
let tmp: Node = this.head.link
while(tmp.link != null) {
pre = tmp
(pre.link != null) tmp = pre.link
// 사실 이 부분이 조금 이상하다
// 위의 while 문
// 조건식이 ture 이면 pre 는 tmp 가 된다.
// 그러므로, 내 생각에는 pre 에 type check 를 할 필요가 없다고 생각한다.
// 그런데 TypeScript 에서는 pre.link 가 null 일 수 있어
// tmp 인 Node type 에 할당이 안된다고 나온다.
// 그래서 pre.link 에 null check 를 주었다.
// 굳이 주어야만 TypeCheck 가 될까?
// 싶은데 TypeCheck 에 대해 더 공부해야 할것같다.
}
pre.link = null
}
tmp.link 가 null 이면 tmp 는 마지막 노드라는 뜻이다.
tmp 이전의 Node 가 pre 이니, pre.link 에 null 을 할당하면 더 이상 마지막 노드를 참조하지 않는다.
즉 pre 가 가리키는 Node 가 마지막 노드가된다.
이상으로 마지막 노드를 없애는 로직을 구현해 보았다.
Insert 연산에 대해서 이해하고 보았다면, 쉽게 이해할 내용이라고 생각한다.
그럼 다음에는 Node 를 탐색하여, 해당 Node 를 반환하는 SearchNode 를 구현해보자.
부디 장수와 번영이 함께하길..