[열혈자료구조] 5강. 연결 리스트(Linked List) 3 - (2)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

드디어!!!!! 길고 길었던 연결 리스트 마지막 포스팅이다. 그동안 3개의 챕터에 걸쳐 연결 리스트에 관해 공부했고, 아래와 같은 내용을 공부했었다. 오늘 포스팅에서는 연결 리스트의 마지막 내용인 양방향 연결 리스트에 관해 다룰 예정이다.

3강	ADT와 배열 리스트
4강	단순 연결 리스트
5강	원형 연결 리스트, 양방향 연결 리스트

 

단순 연결 리스트나 원형 연결 리스트는 노드가 한쪽으로만 연결되어 있지만, 양방향 연결 리스트는 노드가 양쪽으로 연결되어 있다는 것이 차이점이다. 즉, 노드의 구조체 형태가 기존과 달리 아래와 같이 구성된다.

typedef struct _node{
    Data data;
    struct _node * next;
    struct _node * prev;
} Node;

 

하나의 노드에는 아래와 같이 왼쪽와 오른쪽을 가리키는 포인터 변수가 각각 들어간다.

이때, 첫 번째 노드는 단순 연결 리스트에서처럼 더미 노드일 수도 있으며, 더미 노드를 설정했을 때의 장점은 단순 연결 리스트와 동일하다.

이때 처음(더미 노드 혹은 첫번째 노드)과 마지막 노드는 다른 노드와 달리 연결이 한쪽 방향으로만 이루어지는데, 이것이 불편하다면 원형 연결 리스트처럼 처음과 마지막도 연결해 버릴 수도 있다.

양방향 연결 리스트에서는 일부 구현하기 쉬운 요소들이 있는데, 그 중 하나는 LNext와는 반대로 방금 조회한 방향의 반대 노드를 조회할 수 있는 LPrevious 함수이다. 또한, 조회할 때 before 없이 cur만 사용해도 된다. 교재에서 구현한 양방향 연결 리스트는 위에서 살펴본 예시 중에서는 더미 노드 없이 양쪽 끝 노드가 하나씩만 가리키는 형식이다.

 

초기화, 노드의 삽입

 

양방향 연결 리스트의 초기화는 비교적 간단하다. plist->head = NULL, numOfData를 0으로 초기화하기만 하면 되므로 코드는 따로 첨부하지 않으려고 한다.

 

노드의 삽입은 이제까지와 마찬가지로 첫 노드와 두 번째 이후의 노드를 분리하여 생각한다. 첫 노드의 삽입은 노드의 next와 prev를 모두 NULL로 초기화하고, plist->head가 첫 노드를 가리키도록 하면 된다.

void LInsert(List * plist, Data data){
    Node * newNode = (Node *) malloc (sizeof(Node));
    newNode->data = data;

    newNode->next = plist->head;

    newNode->prev = NULL;
    plist->head = newNode;

    (plist->numOfData)++;
}

 

두 번째 이후의 노드를 추가할 때는 plist->hea->next가 newNode를 가리키도록 하는 과정만 추가하면 된다. 따라서 코드는 아래와 같은 조건문을 추가하기만 하면 된다.

void LInsert(List * plist, Data data){
    Node * newNode = (Node *) malloc (sizeof(Node));
    newNode->data = data;

    newNode->next = plist->head;

    if(plist->head != NULL){
        plist->head->next = newNode;
    }
    newNode->prev = NULL;
    plist->head = newNode;

    (plist->numOfData)++;
}

 

이때 head의 위치는 new node를 가리키는 쪽으로 1칸 이동한다.

데이터 조회

 

데이터 조회를 위해 앞서 적은 대로 LFirst, LNext, LPrevious 를 구현한다. 이때 단방향에서 썼던 before를 사용하지 않아도 된다. 이들의 구현은 앞선 리스트와 매우 비슷하며, LPrevious는 LNext에서 cur의 이동방향을 next에서 prev으로 바꿔주기만 하면 된다.

 

1) LFirst

int LFirst(List * plist, Data * pdata){
    if(plist->head == NULL){
        return FALSE;
    }
    plist->cur = plist->head;
    * pdata = plist->cur->data;
    return TRUE;
}

 

2) LNext

int LNext(List * plist, Data * pdata){
    if(plist->cur->next = NULL){
        return FALSE;
    }
    plist->cur = plist->cur->next;
    * pdata = plist->cur->data;
    return TRUE;
}

 

3) LPrevious

int LPrevious(List * plist, Data * pdata){
    if(plist->cur->prev = NULL){
        return FALSE;
    }
    plist->cur = plist->cur->prev;
    * pdata = plist->cur->data;
    return TRUE;
}

 

---

다음 포스팅부터는 6장의 스택(stack)의 구현에 대해 공부해보고자 한다.