[알고리즘] 연결리스트 struct 를 이용한 이중연결리스트 (예제코드)

네이버 블로그에 돌아당기는 이중연결리스트 예제

• 예제코드

예제코드

#include  <stdio.h>

// 노드 구조체 
struct Node 
{ 
        int value; 
        Node *prev; 
        Node *next; 
}; 

Node *head; 

// 연결 리스트 초기화 - 머리를 할당한다. 
void InitList() 
{ 
        head=(Node *)malloc(sizeof(Node)); 
        head->prev=NULL; 
        head->next=NULL; 
} 

// 지정한 노드의 오른쪽에 삽입한다. 
Node *InsertNodeRight(Node *Target,Node *aNode) 
{ 
        Node *New; 
        Node *Right; 

        New=(Node *)malloc(sizeof(Node)); 
        *New=*aNode; 

        Right=Target->next; 
        New->next=Right; 
        New->prev=Target; 
        Target->next=New; 
        if (Right) { 
            Right->prev=New; 
        } 
        return New; 
} 

// 지정한 노드의 왼쪽에 삽입한다. 
Node *InsertNodeLeft(Node *Target,Node *aNode) 
{ 
        Node *Left; 
        Left=Target->prev; 
        if (Left) { 
            return InsertNodeRight(Left,aNode); 
        } 
        return NULL; 
} 

// 제일 끝에 노드를 추가한다. 
void AppendNode(Node *aNode) 
{ 
        Node *tail; 
        for (tail=head;tail->next;tail=tail->next) {;} 
        InsertNodeRight(tail,aNode); 
} 

// 단순 연결 리스트와는 달리 자기 자신을 지울 수 있다. 
BOOL DeleteNode(Node *Target) 
{ 
        Node *Left,*Right; 
        // 헤더는 지울 수 없음 
        if (Target==NULL || Target==head) { 
            return FALSE; 
        } 
        Left=Target->prev; 
        Right=Target->next; 

        Left->next=Right; 
        if (Right) {                   // 타겟이 끝 노드일 경우 
            Right->prev=Left; 
        } 
        free(Target); 
        return TRUE; 
} 

// idx번째 노드를 찾는다. 
Node *FindNodeByIndex(int idx) 
{ 
        Node *Now; 
        int Index=0; 

        for (Now=head->next;Now;Now=Now->next) { 
            if (Index == idx) { 
                return Now; 
            } 
            Index++; 
        } 
        return NULL; 
} 

// 노드의 순서값을 구한다. 
int GetNodeIndex(Node *Target) 
{ 
        Node *Now; 
        int Index=0; 

        for (Now=head->next;Now;Now=Now->next) { 
            if (Now == Target) { 
                return Index; 
            } 
            Index++; 
        } 
        return -1; 
} 

// 노드의 개수를 조사한다. 
int GetListCount() 
{ 
        Node *Now; 
        int Count=0; 

        for (Now=head->next;Now;Now=Now->next) { 
            Count++; 
        } 
        return Count; 
} 

// 연결 리스트의 모든 노드와 머리를 해제한다. 
void UnInitList() 
{ 
        while (DeleteNode(head->next)) {;} 
        free(head); 
        head=NULL; 
}

typedef struct _dnode 
{ 
    int           key; 
    struct _dnode *prev; 
    struct _dnode *next; 
} dnode; 


// 노드의 head, tail 초기화 
void init_dlist(void) 
{ 
    head = (dnode *)malloc(sizeof(dnode)); 
    tail = (dnode *)malloc(sizeof(dnode)); 

    head->prev = head; 
    head->next = tail; 
    tail->prev = head; 
    tail->next = tail; 
} 

// 주어진 정수를 가지고 순환하면서 node를 찾고 그것을 리턴 
dnode *find_dnode(int k) 
{ 
    dnode *snode = head; 

    while (snode->key != k && snode != tail) 
        snode = snode->next; 

    return snode; 
} 


// 주어진 키에 해당되는 노드를 찾아 delete 
int delete_dnode(int k) 
{ 
    dnode *delnode = head; 

    while (delnode->key != k && delnode != tail) 
        delnode = delnode->next; 

    delnode->prev->next = delnode->next; 
    delnode->next->prev = delnode->prev; 

    return k; 
} 

// t의 값을 갖는 노드 전에 
// k값을 값는 노드를 생성해서 연결 
dnode *insert_dnode(int k, int t)   
{ 
    dnode *snode = head; 
    dnode *anode; 

    if ((anode = (dnode *)malloc(sizeof(dnode))) == NULL) 
        printf("노드가 생성되지 않았습니다.\n"); 
    anode->key = k; 

    while (snode->key != t && snode != tail) 
        snode = snode->next; 

    if (snode == tail) { 
        printf("데이터 %d 를 가지는 노드가 없습니다.\n", t); 
        return snode; 
    } 
    else { 
        snode->prev->next = anode; 
        anode->prev = snode->prev; 
        anode->next = snode; 
        snode->prev = anode; 
    } 

    return snode; 
} 

// k값의 순으로 정렬해서 연결 
dnode *ordered_insert(int k) 
{ 
    dnode *snode = head; 
    dnode *anode; 

    if ((anode = (dnode *)malloc(sizeof(dnode))) == NULL) 
        printf("노드가 생성되지 않았습니다.\n"); 
    anode->key = k; 

    while (snode->key <= k && snode != tail) 
        snode = snode->next; 

    snode->prev->next = anode; 
    anode->prev = snode->prev; 
    anode->next = snode; 
    snode->prev = anode; 

    return snode; 
} 

int delete_dnode_ptr(dnode *p) 
{ 
    if (p == head || p == tail) 
        return 0; 
    p->prev->next = p->next; 
    p->next->prev = p->prev; 
    free(p); 
    return 1; 
} 

dnode *insert_dnode_ptr(int k, dnode *t) 
{ 
    dnode *i; 
    if (t == head) 
        return NULL; 
    i = (dnode*)malloc(sizeof(dnode)); 
    i->key = k; 
    t->prev->next = i; 
    i->prev = t->prev; 
    t->prev = i; 
    i->next = t; 
    return i; 
} 


// 전체 노드의 key값 출력 
void print_dlist(dnode *p) 
{ 
    while (p->next != tail && p != tail) { 
        printf("%d --> ", p->key); 
        p = p->next; 
    } 
    printf("%d", p->key); 
} 

// 노드 전체 삭제 
void delete_all(void) 
{ 
    dnode *delnode = head->next; 
    dnode *snode = delnode->next;; 

    while (delnode != tail) { 
        free(delnode); 
        delnode = snode; 
        snode = delnode->next; 
    } 
}