[리스트] 리스트구조 - 연결리스트의 구현

다음으로 리스트 구현방법 중 하나인 연결 리스트를 알아보자

연결리스트는 동적으로 크기가 변할 수 있고, 삭제나 삽입 시 데이터를 이동할 필요가 없는 연결된 표현을 사용한다.

이 연결된 표현은 데이터와 링크(link)로 구성되어 있어 링크가 데이터들을 연결하는 역할을 한다.

이러한 연결된 표현은 리스트에서만 쓰이는 것만 아니라 다른 자료구조인 스택, 큐, 트리 등에서도 많이 쓰인다.

연결 리스트에도 여러 모양이 있는데 대표적으로 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트등이 있다.

우선 단순 연결 리스트를 알아볼 것이다.

위 그림과 같은 모양으로 연결 리스트에는 데이터필드(data field)와 링크필드(link field)로 구성되어 있다.

  데이터필드 : 우리가 저장하려 하는 데이터가 들어간다. 데이터는 정수가 될 수도, 구조체 같은 복잡한 데이터가

될 수도 있다.

  링크필드 : 다른 노드를 가리키는 포인터가 저장된다. 이 때 다른 노드 또한 데이터타입은 자기 자신이 있는 구조체이므로 자기 자신의 구조체를 가리키는 포인터로 정의된다.

링크에 대해 더 이해하기 쉽도록 그림을 만들어봤다.

링크는 포인터이기 때문에 연결할 다음 노드의 주소값을 지니게 된다.

만약 저 그림에서 맨 앞에 있는 노드를 ListNode *phead; 라고 하고, 두 번째 노드의 데이터값을 참조하고 싶으면

*phead -> link -> data; 이처럼 하면 두 번째 노드의 데이터값인 20을 참조할 수가 있는 것이다.

그럼 단순 연결리스트를 C언어적으로 어떻게 구현할까?

typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode *link;
}ListNode;

바로 다음과 같이 정의가 되는 것이다. 위 코드가 바로 단순 연결 리스트의 구현이다.

일반적으로 연결 리스트에서는 동적 메모리 할당을 이용하여 노드를 동적으로 생성한다.

ListNode *p1;
p1 = (ListNode *)malloc(sizeof(ListNode));

위 코드에서는 임시 포인터 변수 p1을 만들고 이 변수에 노드의 크기만큼 메모리를 할당받는다.

그럼 단순 연결 리스트의 삽입에 대하여 알아보자

먼저 기본적으로 2개의 노드 ListNode *p1, ListNode *p2 가 있다고 가정하고 2개의 노드를 서로 연결하고자 한다면, 

p2->link = NULL;
p1->link = p2;

이처럼 p1->link 가 p2를 지정하도록 하면 간단하게 연결할 수 있다.

하지만 기본적으로는 단순 연결 리스트의 삽입은 총 3가지의 경우로 나누어 생각한다.

1. 리스트가 비어있을 경우 (리스트의 헤드 포인터 phead 가 NULL일 경우)

2. 리스트의 맨 앞에 새로운 노드를 삽입할 경우 (선행노드 p가 NULL 일 경우)

/* 여기서 선행 노드는 삽입할 노드 바로 앞의 노드를 말한다 */

3. 리스트의 사이에 삽입할 경우 (phead와 p가 NULL이 아닐 경우)

먼저 1.리스트가 비어있을 때는 간단하다.

헤드 포인터의 포인터 *phead가 새로운 노드를 가리키게만 하면 끝난다.

어차피 리스트가 비어있기 때문에 새로운 노드가 헤드 즉 리스트의 맨 앞의 노드가 되는 것이다.

다음으로 2. 리스트의 맨 앞에 새로운 노드를 삽입할 경우를 보자

이해가 가는가? 먼저 (1) 새로운 노드의 링크가 맨 앞의 노드(head)를 가리키도록 한 후,

(2) 헤드포인터가 새로운 노드를 가리키게 하면 끝이다.

연결 리스트에서 삽입을 할 땐 순서를 꼭 지켜야 한다는 점을 유념해야 한다!

저 그림에서 만약 (2)를 먼저 수행한다면 새로운 노드의 링크가 data:10의 노드에게 연결할 방도가 없기 때문이다.

그럼 3.새로운 노드를 이미 리스트 중간에 삽입하고자 할 경우를 알아보자

그림으로 그 개념을 간단하게 살펴보자

감이 오는가? 연결하고자 하는 곳의 선행 노드(그림에선 data:20)의 링크가 새로운 노드를 가리키게 하고

새로운 노드의 링크가 뒤 노드(그림에선 data:30)를 가리키도록 하면 된다.

물론 여기서도 연산의 순서를 꼭 지켜야 한다.

(2)를 먼저 수행하면 선행노드의 링크가 끊기고 새로운 노드를 가리키게 되므로 (1)을 수행하려 해도 data:30의 노드에

접근할 수 없기 때문이다.

개념을 보았으니 어떻게 삽입연산을 구현하는지 알아보자

// phead: 리스트의 헤드포인터의 포인터 (헤드포인터가 함수 내에서 변경될 수 있으므로 이중포인터 ** 필요
//p : 삽입할 노드의 선행 노드
//new_node : 삽입할 노드
 
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
    if (*phead == NULL)                //공백 리스트인 경우
    {
        new_node->link = NULL;
        *phead = new_node;
    }
    else if (p == NULL)                //리스트 앞에 삽입할 경우
    {
        new_node->link = *phead;
        *phead = new_node;
    }
    else                            //p 다음에 삽입할 경우
    {
        new_node->link = p->link;
        p->link = new_node;
    }
}

처음부터 확 와닿지는 않을 것이다. (필자도 그랬듯)

위 그림들과 같이 보며 천천히 코드를 따라가다보면 충분히 이해할 수 있다.

다음으로 단순 연결 리스트의 삭제 연산에 대하여 알아보자

삭제 연산은 2가지의 경우를 생각해야 한다.

 1. 리스트 맨 앞의 노드를 삭제할 경우 (p가 NULL일 경우)

 2. 리스트 중간의 노드를 삭제할 경우

1. 리스트 맨 앞의 노드를 삭제할 경우는 맨 앞의 노드 즉, head포인터가 가리키는 노드를 삭제하는 것이다.

이는 head포인터가 가리키는 노드의 링크가 가리키는 노드를 헤드 노드로 지시하면 된다.(*phead = *phead->link;)

2. 리스트 중간의 노드를 삭제할 경우는 예시 그림을 보도록 하자

이 그림을 보면 (1) 삭제하고자 하는 노드(Removed)의 선행 노드의 링크가 삭제하고자 하는 노드의 링크가 가리키는 노드를 가리키고 (2) Removed의 링크를 끊어버리면 된다.

삭제 연산 역시 코드로 살펴보도록 하자

//phead : 헤드 포인터의 포인터
//p : 삭제할 노드의 선행 노드
//removed : 삭제할 노드
 
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
    if (p == NULL)                        //리스트 맨 앞의 노드를 삭제할 경우
        *phead = (*phead)->link;
    else                                //선행노드 뒤의 노드를 삭제할 경우
        p->link = removed->link;
 
    free(removed);                        //데이터 삭제
}

삽입 연산 코드보다는 비교적 간단한 것을 알 수 있다. 

이 역시 천천히 코드를 따라가며 보면 이해가 갈 것이다.

마지막으로 이러한 연결 리스트를 방문하여 데이터를 출력하는 함수와 특정 값을 찾는 탐색 함수를 짜보며

마치도록 하겠다.

1. 방문 연산

//포인터를 변경할 필요가 없기에 **head로 쓰지 않는다.
void display(ListNode *head)
{
    ListNode *p = head;
    while (p != NULL)                    //p=p->link 반복하다보면 맨 끝 노드의 링크가 NULL값이기 때문에 조건식!
    {
        printf("%d -> ", p->data);
        p = p->link;
    }
    printf("\n");
}
 
//반환하는 결과값이 ListNode구조체 포인터이기 때문에 *search!
ListNode *search(ListNode *head, int x)
{
    ListNode *p;
    p = head;
    while (p != NULL)
    {
        if (p->data == x)        //찾고자 하는 데이터와 일치하면 p 반환
            return p;
        p = p->link;
    }
    return p;                    //탐색 실패일 경우 NULL 반환
}