이중연결리스트 전격해부!!!

본 포스트는 c언어를 중심으로 작성되었습니다.

이중연결리스트 전격해부!!!

 

저번 포스트에 이어 이중연결리스트를 전격적으로 해부해보았습니다. 방식은 이전과 동일합니다.

 

이중연결리스트를 설명을 잠깐 드리면 

 

first(1000)

NULL (1000)

1. data field

1004 ->

<- 1000

2. data field

1008 ->

<- 1004

3. data field

NULL

위의 논리적 구조를 따릅니다. 즉 first의 첫번째 노드가 주소가 1000인 1.data field의 주소를 링크합니다. 1.data field는 본인노드의 왼쪽 링크는 가르킬 것이 없기에 null이 들어가는 것입니다. 두번째로 2.data field를 보시면 첫번째 링크에는 1.data field의 주소인 1000을 가지고 있습니다. 오른쪽 링크는 3.datafield의 주소인 1008을 가지고있습니다. 

 

정리하자면 이중연결리스트는 하나의 노드에 두 개의 링크를 가지고 있다는 것입니다. 단순 연결리스트와 차이점은 단순연결리스트는 어떤 노드에 엑세스하려 할때 무조건 한바퀴 순회해야합니다. 반면에 이중연결리스트는 양쪽으로 순회가 가능하기에 그런 문제를 해결할 수 있죠.

 

아래코드를 보시면서 이해를 하시면 더빠를것 같습니다.

//이중연결리스트 코드
//** code by hazard3_000sung **
 
#include <stdio.h>//표준 입출력 라이브러리
#include <stdlib.h>//문자열 변환, 동적 메모리관리 라이브러리
#include <string.h>//c형식 문자열을 다룰 수 있는 함수+메모리 블럭
 
//연결리스트의 노드 구조 구조체 정의 블록
typedef struct ListNode
{
    //이중 연결이기때문에 한 노드에 할당되는 링크는 좌우로 두개입니다.
    struct ListNode* llink;
    struct ListNode* rlink;
    char value[4];
}listNode;
 
typedef struct 
{
    listNode* first;
}linkedList_f;
 
//이중연결리스트를 생성하는 알고리즘
linkedList_f* makeDoubleLinkedList(void)
{
    linkedList_f* L;
    L = (linkedList_f*)malloc(sizeof(linkedList_f));
    L -> first = NULL;//초기 값으로 null을 선언
    return L;
}
 
//앞에서 보다시피 출력하는 함수
void PrintList(linkedList_f* L)
{
    listNode* N;
    printf("N = {");
    N = L -> first;
    //listNode의 포인터 변수 N이 NULL이 나올때까지 연산해서 출력합니다.
    while(N != NULL)
    {
        printf("%s", N -> value);
        N = N -> rlink;
        if(N!=NULL)printf(",");
    }
    printf("}\n");
}
 
//노드를 삽입해주는 함수입니다.
//앞서 단순연결리스트와 다른 점은 llink, rlink가 있어서
//양쪽으로 잡아서 넣어주어야합니다.
void insertNode(linkedList_f* L, listNode *sec, char* a)
{
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode -> value, a);
    if(L -> first = NULL)
    //링크드리스트의 첫번째 노드가 null이라면
    {
        newNode -> rlink = NULL;
        newNode -> llink = NULL;
        L -> first = newNode;//first노드가 listnode를 가르킴
        //본 블록내에 기재된 코드가 활성화
    }
    else
    {
        newNode -> rlink = sec -> rlink;
        //listNode의 포인터 변수 newnode는 오른쪽(다음)노드를 가르킵니다.
        //함수의 목적은 노드를 삽입하는것이지요. 그렇기 때문에 sec포인터 변수가 가르키는 노드 뒤로 삽입할수 있는것입니다.
        sec -> rlink = newNode;
        newNode -> llink = sec;
        if(newNode -> rlink != NULL)
            newNode -> rlink ->llink = newNode;
    }
}
 
//노드삭제하는 함수
void eraseNode(linkedList_f* L, listNode* zero)
{
    if(L -> first == NULL)
    //리스트 전체가 null인 경우도 null반환
        return;
    else if (zero == NULL)
    //삭제할 노드가 null이라면 null반환 
        return;
    else
    {
        //노드를 삭제합니다
        zero -> llink -> rlink = zero -> rlink;
        zero -> rlink -> llink = zero -> llink;
        free(zero);//동적메모리 해제
    }
}
 
//c언어는 절차지향프로그램입니다. 그말은 즉슨, 위에서부터 아래로 내려오는
//코드로 동작을 한다는 말입니다. main진입점위에서만 코드를 작성해야하느냐 그건 아닙니다.
//main진입점아래에 함수를 생성하고 main진입점 위에 함수원형을 선언해주면 사용가능합니다!
linkedList_f* searchNode(linkedList_f* L, char* a);
 
int main()
{
    linkedList_f* L;
    listNode* N;
    L = makeDoubleLinkedList();
    printf("이중 연결리스트를 생성하는 코드입니다.");
    PrintList(L);
 
    printf("1. 이중 연결리스트 첫번째 노드에 사과 연결");
    insertNode(L, NULL, "사과");
    PrintList(L);
 
    printf("2. 이중 연결 리스트 [사과] 노드 뒤에 [귤] 삽입하겠습니다");
    N = searchNode(L, "사과");
    insertNode(L, N, "귤");
 
    printf("3. 이중 연결리스트 [귤] 노드 뒤에 [오렌지] 삽입하겠습니다.");
    N = searchNode(L, "귤");
    insertNode(L,N,"오렌지");
 
    printf("4. 귤 노드 삭제하겠습니다");
    N = searchNode(L, "귤");
    eraseNode(L, N);
    PrintList(L);
 
    return 0;
 
}
 
//노드를 검색해주는 알고리즘
linkedList_f* searchNode(linkedList_f* L, char* a)
{
    //listNode의 포인터변수로 search선언
    listNode* search;
    search = L -> first;
    while(search != NULL)
    {
        if(strcmp(search -> value, a)==0)
        //strcmp는 문자열비교함수입니다. 
        {
            return search;
        }      
        else
            search = search -> rlink;
    }
    return search;
}

댓글 피드백 환영합니다!!