[Data Structure] Singly Linked List (3)

이번 포스트에선 header에 정의한대로 Data Node를 삽입하되, 그걸 head node의 뒤에 삽입할 것이냐, tail node의 앞에 삽입할 것이냐에 대한 의미를 부여할 수 있겠다. 구현은 다음과 같다.

int insertFirst(List *lp, int data)
{
    Node *tmp;
 
    if(lp == NULL){
        return -1;
    }
 
    tmp = (Node *)malloc(sizeof(Node));
    if(tmp == NULL){
        return -1;
    }
 
    tmp->data = data;
    tmp->next = lp->head->next;
    lp->head->next = tmp;
    lp->size += 1;
 
    return 0;
}

 line 5~7 : 이전 구현부와 동일하게 참조 포인터에 대한 NULL pointer 체크이다.

 line 9~12 : Node도 데이터를 가진 자료형이며, 이를 유지하기 위해서는 메모리상에 Node 구조체의 크기만큼 할당받아야 한다. 역시 할당이 정상적으로 이뤄졌는지 여부를 확인하는 예외처리 구문이 들어갔다.

 line 14~17 : 어떻게 보면 이 삽입함수의 핵심 내용이라고 할 수 있다. Linked List의 정의와 같이 각각의 Node는 반드시 데이터와 다음 Node를 가리키는 포인터를 포함해야 한다. 그런데 이점도 고려해야 한다. Node가 다음 Node를 가리킬 수있다면, 알수없는 Node중 하나도 지금 해당 Node를 가리킬 수 있는 것이다. Linked List에서 삽입의 의미는 중간에 구멍이 없이 연결되어 있는 형태를 유지하는 것이므로 이 포인터에 대한 관계 정립이 이뤄져야 한다. 그림으로 표현하면 다음과 같다.

<처음으로 InsertFirst를 실행한 경우>

위와 같이 점선으로 표시된 화살표가 처음 createList를 했을 때 Head Node가 Tail Node를 가리키는 경우이다. 그런데 함수의 이름이 내포한 것과 같이 처음으로 Node를 삽입하겠다는 것은 결국 Head pointer가 새로 생성한 Node를 가리키게 하고 새로 생성한 Node가 이전에 Head의 Next 포인터가 가리키던 Node를 가리키게 하면 되는 것이다. 약간 순서를 조절하자면 새로 Node가 생성됬을때 이전 Head의 Next pointer가 가지고 있던 값을 tmp Node의 Next pointer가 갖게끔하고, 그다음에 Head pointer의 Next pointer가 tmp Node를 가리키게 하는 것이 위 함수의 동작이다. 당연히 Data Node가 삽입되었으므로 전체적인 Linked List의 size는 1 증가할 것이다.

다음은 tail node의 앞에 새 Node를 삽입하는 InsertLast에 대한 구현부이다.

int insertLast(List *lp, int data)
{
    Node *tmp;
    Node *frontNode;
 
    if(lp == NULL){
        return -1;
    }
 
    tmp = (Node *)malloc(sizeof(Node));
    if(tmp == NULL){
        return -1;
    }
 
    tmp->data = data;
    tmp->next = lp->tail;
    lp->size += 1;
 
    frontNode = lp->head;
    while(frontNode != lp->tail){
        frontNode = frontNode->next;
    }
    frontNode->next = tmp;
 
    return 0;
}

 line 3~4 : 전체적인 함수기능으로 놓고 보면 insertLast나 앞에서 소개한 insertFirst는 동일한 Node 삽입 기능을 수행한다. 문제는 지금 다루고 있는 자료형이 singly Linked List 라는 것이다. 이전포스트에서 다뤘던 구조체 속에 포함된 자료형을 살펴보면 데이터 자체와 자신의 다음 Node를 가리키는 포인터만 가지고 있기 때문에 뭔가 앞에새로운 Node를 삽입하기 위해서는 임시로 이전 Node를 가리킬 변수가 필요하다. 이때문에 insertFirst와 다르게 frontNode라는 변수를 추가했다.

 line 6~8 : 이전과 동일하게 넘겨받은 List 포인터에 대한 예외처리이다.

 line 10~13 : 동일하게 데이터를 삽입할 임시 Node에 대해 메모리 할당을 수행하는 부분이다.

 line 15~23 : 이제 선언한 임시 Node에 값을 저장하고 전체 연결리스트내에서의 관계 정립하는 과정이 필요하다. 지금 이 함수의 역할은 tail Node의 앞에 값을 저장하는 것이므로 큰 맥락에서 보자면 새로 생성할 Node의 Next 포인터는 당연히 tail Node를 가리켜야 한다. 

 그런데 문제는 과연 어떤 Node가 이 임시 Node를 Next Node로써 가리킬 것인가? 계속 강조했다시피 Singly Linked List는 자신의 다음 Node를 가리키지 이전 Node에 대한 정보를 가지고 있지 않다. 이때문에 line 3~4에서 정의한 바와 같이 이전 Node에 대한 정보를 가리킬 또다른 임시 Node가 필요하다. 단 해당 Node는 단순히 이전 Node를 가리키는 역할만 할 뿐, 값을 저장하는 역할을 수행하는 것이 아니기 때문에 따로 메모리의 특정 영역을 할당할 필요가 없다.

 그러면 이제 이 Node를 어떻게 찾냐가 관건이 된다. 그런데 tail Node의 기능을 기억하면 해당 Node를 찾기 쉽다. 분명 tail node의 역할은 Linked List의 마지막 Node이지만 이 자체는 데이터를 가지고 있지 않기 때문에 결과적으로는 tail node의 바로 앞에 있던 Node가 제일 마지막 Node가 된다. 그러면 위 함수를 통해 데이터를 삽입하는 것은 결과론 적으로는 제일 마지막 Node의 Next가 새로 데이터를 가진 임시 Node(tmp)를 가리키게 하면 되는 것이다. 그런데 삽입하기 전 마지막 Node는 Next 포인터가 tail Node를 가리키고 있었으므로, 이를 통해 바로 앞 Node를 찾을 수 있게 된다. 그 해당 부분이 line 19~23에서 구현한 내용이다. 그림으로 설명하면 다음과 같다.

[그림]

 해당 부분에 대해서는 뭔가 장황하게 설명했는데, 결국 Singly Linked List에서 구조체로 표현할 수 없는 이전 Node를 가리키는 정보가 없기 때문에 insertFirst와 다르게 이런 과정이 필요했다.