[LeetCode] Delete Node in a Linked List (js/연결 리스트)

문제 : 

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory.

1. 단일 연결 리스트(singly-linked list) 헤드 내에 있는 노드를 삭제하고자 한다. 

2. 삭제 해야할 노드가 주어지며, 첫 번째 노드에 대한 엑세스 권한은 부여되지 않는다.

3. 연결 리스트 내 모든 값은 고유하며, 주어진 노드는 마지막 노드가 아님이 보장된다. 

4. 주어진 노드를 삭제하되, 메모리에서 제거해서는 아니된다. 

We mean:

• The value of the given node should not exist in the linked list.
• The number of nodes in the linked list should decrease by one.
• All the values before node should be in the same order.
• All the values after node should be in the same order.

• 주어진 노드의 값은 연결 리스트 내에 존재해서는 안된다. 
• 연결 리스트 내 노드 수는 1감소해야한다.
• 삭제하는 노드 이전의 노드들은 같은 순서로 정렬되어야한다.
• 삭제되는 노드 이후의 노드들은 같은 순서로 정렬되어야한다. 

Custom testing:

• For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
• We will build the linked list and pass the node to your function.
• The output will be the entire list after calling your function

개념 : 

연결 리스트 (Linked List)

Linked list는 선형적인 데이터 구조라는 점에서 배열과 유사하지만, 연결 리스트의 요소(elements)들은 특정 메모리 주소나 인덱스에 저장되지 않는다. 연결리스트의 각 요소를 노드(node)라고 부르며, 노드는 일반적으로 데이터 그리고 다음 노드를 가리키는 링크, 이 2가지 아이템으로 구성된다. 

출처 : https://www.geeksforgeeks.org/what-is-linked-list/

[6,10,12,3]의 연결리스트를 자바스크립트로 표현하면 다음과 같다. 

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

장/단점

장점

: 전체 데이터 구조 재구성 없이 노드를 추가/제거 할 수 있음

단점 

1. 배열과 달리 데이터 요소에 대한 임의 엑세스가 허용되지 않아 첫번째 노트부터 순차적으로 엑세스 되어 검색 작업이 느리다.  

2. 포인터의 저장으로 인해 배열보다 더 많은 메모리 사용. 

 

구현

// 생성자 (constructor)를 사용해 연결리스트 클래스 구현
class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

// 헤드(head) 노드에 아무 값도 전달하지 않으면 null로 초기화
class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

 

연결리스트 구현

let node1 = new ListNode(2)
let node2 = new ListNode(5)

node1.next = node2 // node1에 node2를 가르키는 포인터 생성

let list = new LinkedList(node1) // node1을 사용해 연결리스트 생성

console.log(list.head.next.data) // returns 5

 

연결리스트 메소드 

• size() : 연결 리스트 내 노드 개수 반환
• clear() : 리스트 비우기 
• getLast() : 연결리스트의 마지막 노드 반환
• getFirst() : 연결리스트의 첫 번째 노드 반환

 

풀이 : 

var deleteNode = function(node) {
   
    if (node === null || node.next === null) {
        return null;
    }
    
    node.val = node.next.val;
    node.next = node.next.next;
};

삭제할 노드가 결정되어있기 때문에 주어진 노드의 현재값을 next로. 주어진 노드의 next값에 next.next를 할당해서 다음 노드와 연결을 끊어버리면된다.