remove와 find

들어가기 전에

임의의 위치의 노드를 제거하는 remove와 노드를 찾는 find에 대해 살펴보도록 하겠습니다.

 

학습 목표

연결 리스트에서 노드의 remove, find 함수를 만드는 방법을 이해할 수 있습니다.

 

핵심 단어

• 연결 리스트
• Comparable 인터페이스
• 경계 조건

find

 

Comparable 인터페이스를 사용하여 노드를 찾습니다.

 

remove

 

1. Comparable 인터페이스를 사용하여 제거하고 싶은 요소의 위치를 찾습니다.

2. 바로 앞 노드의 next 포인터가 다음 노드를 가리키게 만들어 가운데 노드를 제거합니다.
previous, current의 2가지 포인터를 사용하여 각각 바로 앞의 노드와 제거하고자 하는 노드를 가리키게 합니다.

 

노드가 1개만 있는 경우, 첫 번째 노드를 제거하는 경우에는 removeFirst 메소드를 사용합니다. 그리고 마지막 요소를 제거하는 경우에는 removeLast 메소드를 사용합니다.

 

 

---

 

생각해보기

1) remove와 removeFirst 메소드, removeLast 메소드와의 차이점은 무엇인가요?
2) 리스트가 비어있는 경우에 remove를 사용하면 어떻게 되나요?

 

나의 생각:

 

1) removeFirst는 head=head.next를 하면 첫 번째가 지워진다.

2) removeLast 메소드로 마지막 노드를 삭제하려면, '마지막 노드 바로 이전 노드의 위치'를 알아야 한다. 그래야 그 노드의 next 포인터를 null로 설정해서 마지막 노드를 삭제할 수 있기 때문이다. 그런데, 단일 연결 리스트에서는 뒤에서 앞으로 갈 수 없기 때문에 '마지막 노드 바로 이전 노드의 위치'를 알기 위해서는 previous, current라는 두 개의 포인터가 추가적으로 필요하다. 이 포인터들을 이용해 앞에서 뒤로 순차적으로 리스트를 탐색하다가, current.next == null 또는 current == tail이 되면 current가 마지막 노드까지 왔기 때문에 previous.next = null로 마지막 노드를 삭제한다. 그리고 tail = previous를 통해 tail의 위치를 갱신한다.

 

3) remove는 Comparable 인터페이스를 사용하여 제거하고 싶은 요소의 위치를 찾는다.

바로 앞의 노드의 next가 다음 노드를 가리키게 하고 중간의 노드를 삭제한다.

previous 와 current를 사용하여 앞 노드와 뒷 노드를 찾고 가리키게 한다.

 

4) 리스트가 비어있는 경우는 head와 current가  null이기 때문에 반복문을 진입하지않고 바로 null을 반환한다.

 

출처 : https://www.boostcourse.org/cs204/lecture/625945?isDesc=false 네이버커넥트재단