[자료구조] 연결 리스트의 이해(3)

[자료구조] 연결 리스트의 이해(3)

더미 노드 기반의 연결 리스트에 대해 알아보자.

그 전 포스팅에서 보았듯이, 삽입, 삭제, 참조 시에

첫 노드와 그 이외의 노드의 처리과정이 차이가

나는 것을 볼 수 있었다. 모든 노드들을 일관되게

처리를 해주는 것이 좋은 코드라고 말했는데,

이는 더미 노드를 이용하면 쉽게 해결할 수 있다.

더미 노드란?

유요한 데이터를 저장하지 않는 노드이다.

즉, 헤드가 데이터를 가지지 않는 껍데기(?) 뿐인

노드를 물고있는 것이다. 아래 그림을 보자

기존의 연결 리스트

더미 노드 기반 연결 리스트

왜 이렇게까지 해야할까 의문이 들수도 있지만

연결 리스트의 구현이 더욱 복잡해 졌을 때, 코드의

일관성은 무시할 수 없기 때문이다. 때문에 현재

더미 노드 기반의 연결 리스트가 표준에 더욱 가깝다.

더미 노드를 통해 구현한 삽입, 삭제, 참조를 보도록 하자.

첫 노드를 할당했지만, 아무런 데이터를 물고 있지 않다.

데이터는 이 더미노드 뒤부터 추가되게 된다.

01. 삽입

더 이상 head를 다루지 않아도 된다.

head는 더미 노드이고 실제 데이터는 그 후로 저장되어 있기 때문

02. 참조

03. 삭제

기존의 연결 리스트와 다른 차이점이 보이지 않는다.

다만 처음에 head가 데이터를 저장하지 않는 노드를 물고 있다.

즉, 첫 노드는 아무런 데이터가 없다.

첫 노드를 제외한 모든 코드를 다루는 것이기 때문에

기존의 코드에서 첫 노드를 다루는 부분만 삭제해주면 된다.