[Python] 더블리 링크드 리스트 삭제 연습

자료구조 강의 중 필기.

 

 

노드의 첫번째를 head 노드라고하고 마지막 노드를 tail 노드라고 한다.

 

더블리 링크드 리스트 노드는 앞 노드(next)와 전 노드(prev)를 동시에 가지고 있다.

 

더블리 링크드 삭제 연산은 파라미터로 지우려는 노드 자체를 넘겨주면 된다.

 

더블리 링크드 리스트는 4개의 경우의 수를 가진다

 

삭제 메소드를 del, 삭제하고 싶은 노드를 node_del이라고 이름을 정했다.

 

첫 번째 경우

 

지우려는 노드가 링크드 리스트의 마지막일경우.

 

해당 노드는 head와 tail 둘다 가지고 있다. 따라서 head와 tail을 None으로 지정 해주면 더이상 연결된 노드가 존재하지 않으므로 완전히 지워졌다고 볼 수 있다.

 

두 번째 경우

 

지우려는 노드가 head 노드이고 마지막 남은 노드가 아닐경우.

 

2, 3, 5, 7 을 저장하고 있는 링크드 리스트가 있다고 가정

2를 삭제할때 2는 head 노드이면서 지우려는 노드 node_del이다.

먼저, head 노드를 3으로 바꿔주고(next), 2는 None으로 지정한다.

 

세 번째 경우

 

tail 노드를 지울 때, 지우려는 노드가 마지막 남은 노드가 아닐 경우.

 

2, 3, 5, 7 중 7을 삭제하는경우이다.

 

이전 노드인 5를 tail 노드로 지정해준다. 그후에 5의 next는 None으로 지정한다.

 

7은 tail 노드이면서 5의 next로 지정되어있었는데 이 두가지 연결을 모두 끊은것

 

네 번째 경우

 

2, 3, 5, 7 중에 5를 삭제하는것

 

노드 3의 next를 7로 지정해준다. 7의 prev를 3으로 지정.

 

5를 지정하는 레퍼런스가 없어져 삭제됐다고 볼 수 있다.

 

 

지우고 싶은 노드가 생기면, 두개의 레퍼런스만 바꾸면 된다. 이러한 방식으로 삭제하면 시간복잡도는 O(1)이라고 한다.

 

 

이렇게 완성되었다. 

 

더블리 링크드 리스트는 next와 prev를 둘다 지정하기때문에 next만 지정하는 싱글리 링크드 리스트에 비해 약 2배의 저장공간을 사용하는 단점이 있음.

맨앞, 맨뒤를 참고하는  조건이 있다면 더블리가 괜찮은 옵션이 될 수 있고 저장공간을 아낄려면 싱글리가 좋은 옵션이 될 수 있다.