#007_자료구조와 알고리즘_너와 나의 연결고리! 연결 리스트 (더미 노드X)

안녕하세요 삽잡이 입니다.

이번 시간에는 더미 노드가 없는 상태의 리스트를 만들 때에 대해서 알아보려고 합니다.

일반적으로 지난시간에 봤듯이 

더미노드가 있는 상태의 리스트에서는 데이터가 담긴 노드가 10개 일지라도,

총 노드의 개수는 12개였습니다.

왜냐? 더미 노드가 있는 연결 리스트에서는 데이터가 없는 노드 두 개가 있었기 때문입니다.

하지만 더미 노드가 없는 리스트의 경우

데이터가 보관 된 노드의 개수와 실제 리스트에 총 노드의 개수가 동일합니다.

음... 그렇다면 더미 노드가 있는 리스트와 차이점은 이게 끝일까요?

아닙니다...

더미 노드가 있는 리스트는 리스트 최초 구현시 Head와 Tail 이라는 더미 노드들이 생성되기 때문에

데이터를 추가하거나, 삭제할 때 둘다 모두 방법이 동일합니다.

iterator 즉, 반복자는 노드 추가 및 검색 시 begin(), end() 메소드를 사용하게 되는데요,

이때 이미 생성된 head와 tail을 참조할 수 있게되어 굳이 코드를 구현하는데 복잡하지 않습니다.

하지만, 더미 노드가 없는 상황에서 노드를 추가했을 경우에 대한 생각을 해봅시다.

1. 아무것도 없는 상황에서 최초의 노드를 생성하는 상황.

2, 맨 뒤에 노드를 추가하는 상황

3. 맨 앞에 노드를 추가하는 상황

4. 그 외 중간에 노드를 추가하는 상황

음... 생각해봤을 때 이와 같이 크게 네가지의 경우로 노드를 생성할 수 있다고 한다면,

이 4가지 모두 구현하는 코드가 다르게 됩니다.

여기서 여담으로 말씀드리자면,

더미 노드가 있는 리스트의 경우 모든 상황이 4번째 상황가 동일하기 때문에

코드를 한가지 종류로 구현 할 수 있게 된다는 뜻이었습니다.

아무튼... 이 네가지의 경우를 구현하기 위해서 하나씩 나눠 보기로 하겠습니다.

우선, 첫번째 상황과 두번째 상황은 공통점이 있습니다.

모두 어디에 보관할지에 대한 iterator 값이 모두 NULL 이라는 것입니다.

이해가 안가시나요? 잘 생각해보자구요...

아무 것도 없는 상황이라면, 처음과 끝 모두 NULL을 가리키고 있는 상황입니다.

이 상황에서 노드를 하나 추가한다고 생각해보세요...

어디에 보관할지에 대한 iterator의 위치를 알 수 있을까요? 아무 것도 없는 상태에서?

다음으로, 맨 뒤에 보관하고자 할때 iterator 위치 또한 NULL 을 가리키고 있는 상황입니다.

맨 뒤에 보관하고자 하니 맨 뒤에는 아무것도 없게 되지요...

따라서 '맨 뒤에 보관해줘!'라는 뜻은 즉, '내 뒤에 아무것도 없으면 보관해줘!' 

와 같은 뜻이 되는 것이지요...

그렇다면 노드를 추가할 iterator가 NULL 이 아닌 경우인 세번째, 네번째 상황은

어떻게 구현할 수 있을까요?

우선, 맨 앞에 보관하기 위해서는 iterator의 값이 head를 가리키고 있어야 합니다.

그래야만이 head 바로 뒤에 노드를 추가할 수 있기 때문이지요...

그렇다면 네번째 상황은 그 외의 경우를 생각하실 수 있게 됩니다.

삭제하는 것 또한... 비슷하겠습니다...

절대 귀찮은게 아닙니다? 하하하... 왜냐하면 이렇게 말로 주절 거리는 것보다

코드를 구현해서 소개하는 것이 훨씬 효율적일 것이라 생각하기 때문입니다...

지금까지 간략하게(?) 더미 노드가 없는 연결 리스트에 대해서 글로 설명 해봤습니다.

물론, 부족할게 수두룩하지만...

다음시간에는 코드로 찾아뵙도록 하겠습니다.

이상 삽잡이였습니다!