본 내용은 공부를 위한 내용으로 틀린내용이 있을수 있습니다.

연결리스트 Last delete 연산을 알아보아요.

이전에는 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 를 하나씩 되짚어보자.

head 가 null 일때


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 이 된다.

pre, tmp 가 왜 필요한가


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 가 마지막 노드가된다.

TO BE CONTINUED

이상으로 마지막 노드를 없애는 로직을 구현해 보았다.

Insert 연산에 대해서 이해하고 보았다면, 쉽게 이해할 내용이라고 생각한다.

그럼 다음에는 Node 를 탐색하여, 해당 Node 를 반환하는 SearchNode 를 구현해보자.

부디 장수와 번영이 함께하길..

profile
익숙해지면 다 할수 있어!!

0개의 댓글