211122, 자료구조 Ch. 05-2

오랫만. 금요일엔 진도만 나가고 까먹고 복습을 안했다..

Ch 05-2, Doubly Linked List

우린 지금까지 배열 기반 연결리스트 / DMY 기반의 연결리스트 / CLL 을 배웠다. 이번엔 양방향 연결 리스트 (지금부터 DLL이라고 작성하겠다)을ㅇ 배워보자.

양방향. 말 그대로 "양 방향을 가리킨다"라고 생각해주면 된다.

출처

이런 늑김.

앞선 리스트들은 양방향이 아닌 한쪽 방향으로만 흘러가다보니 next 포인터만 있으면 됐는데, 이번엔 양방향이다 보니 prev 포인터도 필요하다.

typdef struct __node {
	Data data;
    __node *next;
    __node *prev;
} Node;

그리고 뭐 양 끝을 원형 리스트처럼 만들어서 양방향 원형 연결 리스트도 만들 수 있다.

그러면, 본격적으로 양방향 연결 리스트를 이해하며 구현해보도록 하자.

우선, 가장 중요한 헤더파일부터.

/* DBLinkedList.h */

#ifndef __D_B_LINKED_LIST_H__
#define __D_B_LINKED_LIST_h__

#define TRUE	1
#define FASLE	0

typedef int Data;

typdef struct __node { // Node의 구조체
    Data data;
    __node *next;
    __node *prev;
} Node;

typedef struct __dbl { // DBL의 구조체
    Node *head;
    Node *cur;
    int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit (List *plist);
void LInsert(List *plist, Data data);

int LFirst(List *plist, Data *pdata);
int LNext(List *plist, Data *pdata);

int LPrevious(List *plist, Data *pdata);
//LNext 와는 반대로 왼쪽 노드로 이동해서 노드의 데이터를 참조한다.

Data LRemove(List *plist);
int LCount(List *plist);

#endif

그 다음은, 헤더파일의 함수들을 구현해보도록 하겠다. 자세한 설명은 주석으로 달겠다.

/* DBLinkedList.c */

#include <stdio.h>
#include <stdlib.h> // stdlib가 malloc도 포함함
#include "DBLinkedList.h"

void ListInit (List *plist) {
    plist->head = NULL;
    plist->numOfData = 0;
} // 굳이 설명할게..

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->prev = newNode; // 기존 노드가 새 노드를 가리킴
    }
    newNode->prev = NULL; // 새 노드의 앞은 NULL이고
    plist->head = newNode; // head가 새 노드를 가리킴
    
    (plist->numOfData)++;
}

int LFirst(List *plist, Data *pdata) {
    if (plist->head == NULL) { // 추가된 노드가 하나도 없다면
        return FALSE;
    }
    
    plist->cur = plist->head;
    *pdata = plist->cur->data;
    
    return TRUE;
}

int LNext(List *plist, Data *pdata) {
    if (plist->cur->next == NULL) { // 더 이상 조회할 노드가 없다면
        return FALSE;
    }
    
    plist->cur = plist->cur->next;
    *pdata = plist->cur->data;
    
    return TRUE;
}

int LPrevious(List *plist, Data *pdata) {
//LNext 와는 반대로 왼쪽 노드로 이동해서 노드의 데이터를 참조한다.

    if (plist->cur->prev == NULL) {
        return FALSE;
    }
    
    plist->cur = plist->cur->prev;
    *pdata = plist->cur->data;
    
    return TRUE;
 
}

Data LRemove(List *plist){

    Node *rpos = plist->cur;
    Data rdata = plist->cur->data;
    
    if (rpos == plist->head) // 첫 번째 노드 삭제
    
    else if (plist->cur->next == NULL) // 마지막 노드 삭제
    
    else // 그 이외 노드 삭제

}


int LCount(List *plist) {
    return plist->numOfData;
}

뭐.. 요정도다. LRemove는 굳이 코드를 일일히 짜기에는 너무 귀찮은 과정이고, 다른 방법으로 DBL을 구현하는 방법 중 하나인 "더미 노드 기반 양방향 연결리스트"에서 훨씬 쉽게 구현할 수 있기에 굳이 구현하지 않았다.

오늘은, 여기까지.