#008_자료구조와 알고리즘_너와 나의 연결고리! 연결 리스트 예제

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

이번 시간에는 지난 시간에 배웠었던 

더미가 있는/없는 연결 리스트에 대한 코드를 소개하고자 합니다.

물론, 귀차니즘에 절정인 삽잡이는 전체 코드를 소개하지 않을 것입니다.

푸하하...

더미가 없는 연결리스트는

노드를 처음 생성할 때, 맨 앞에 추가할 때, 맨 뒤에 추가할 때, 중간에 추가할 때

각각의 경우에 따라 코드의 차이가 있습니다.

하지만 더미가 있는 연결리스트의 경우에는

더미가 없는 연결리스트에서 중간에 노드를 추가하는 방식과 차이가 없기 때문에

어떠한 경우에서도 코드의 차이가 없습니다.

그렇다면, 잔소리는 집어치우고...

각각의 경우 어떻게 코드를 구현하면 좋을지에 대해서 소개하겠습니다.

물론, 이 코드는 굳이 이해하실 필요는 없습니다.

간략하게 list의 기능들 중 push_back, insert, erase 등에 대한 이해를 해보기 위해 

논리적인 표현을 코드로 옮겨 놓은 것이기 때문입니다.

참고로, 더미 노드가 있는 연결 리스트의 경우 

더미 없는 연결 리스트의 코드의 일부와 다를 것이 없기 때문에 생략하도록 하겠습니다.

우선, 더미 없는 연결 리스트의 초기화 입니다.

// 더미 X 연결리스트 초기화
list()
{
    head = 0;
    tail = 0;
}

다음으로, 더미 없는 연결 리스트의 노드 추가 입니다.

// 더미 X 연결리스트 노드 추가
void hang_node(node *pos,node *now)
{
        if(pos)
        {
            if(pos == head)//맨 앞에 보관
            {
                now->next = pos;
                pos->prev = now;
                head = now;
            }
            else//중간에 보관
            {
                now->prev = pos->prev;
                now->next = pos;
                pos->prev->next = now;
                pos->prev = now;
            }
        }
        else//pos가 NULL이다.
        {
            if(head)//맨 뒤에 보관
            {
                tail->next = now;
                now->prev = tail;
                tail = now;
            }
            else//처음으로 보관
            {
                head = now;
                tail = now;
            }
        }
}

노드 삭제 입니다.

// 더미 X 연결리스트 노드 삭제
void dehang_node(node *now)
{
    if(now->prev)
    {            
        now->prev->next = now->next;
    }
    else
    {
        head = head->next;
    }
    if(now->next)
    {
        now->next->prev = now->prev;
    }
    else
    {
        tail = tail->prev;
    }
}

마지막으로, 리스트 소멸의 경우에는,

iterator 가 가리키는 위치가 시작과 끝이 아닐 때까지 모두 지운 다음 마지막 노드를 지우면 되겠습니다.

STL 에서 제공하는 연결 리스트의 메소드들에 대한 기능 이해를 끝내도록 하겠습니다.

이상 삽잡이였습니다~!