[자료구조] Single Linked List 예제 코드 #2 (C)

Single Linked List 구현하기 #2

 

따로 list의 크기를 입력받는 상황은 구현하지 않고 정적으로 이미 만들어진 노드에서 circular list로 만들고 검색하는 기능을 구현했다.

 

구현을 위한 메서드들

• struct Node : list의 한 노드를 구성하는 구조체
• struct Node* Create(int data) : list의 새 노드를 만드는 함수
• struct Node* Insert(struct Node* current, int data) : current 라는 노드 뒤에(after라는 노드 앞에) 노드를 새로 만들고 data값을 설정 후 노드를 반환하는 함수
• void destroy(struct Node* destroy, struct Node* head) : head 노드부터 탐색해서 destroy 노드를 찾으면 메모리를 할당 해제하고 해제된 노드의 양쪽을 이어주는 함수
• void Search(struct Node* head, struct Node* search) : search라는 노드가 존재하는지 head 노드부터 찾아보는 함수
• int Count(struct Node* head) : 연결된 노드의 개수를 반환하는 함수
• void Circle(struct Node* head) : 마지막 노드가 head를 가리키게 만들어 주는 함수(circular)

 

 

#include <stdio.h>
#include <stdlib.h>
 
struct Node* Create(int data);
void printNode(struct Node* from);
struct Node* Insert(struct Node* current, int data);
int Count(struct Node* head);
int Search(struct Node* head, struct Node* search);
void Circle(struct Node* head);
 
struct Node{
    int data;
    struct Node* nextNode;
    struct Node* prevNode;
};
 
int main()
{
    struct Node* Node1 = Create(100);
    struct Node* Node2 = Insert(Node1,200);
    struct Node* Node3 = Insert(Node2,300);
    struct Node* Node4 = Insert(Node2,250);
 
    printNode(Node1);
    printf("노드는 %d개\n",Count(Node1));
    Search(Node1, Node4);
    Circle(Node1); 
    printf("%d",(Node1->prevNode)->data);
    
    return 0;
}
 
void printNode(struct Node* from){
    int i = 1;
    while(from){
        printf("%d번째 노드 : %d\n",i,from->data);
        i++;
        from = from->nextNode;
    }
}
/* 새 노드를 만드는 함수 */
struct Node* Create(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    newNode->data = data;
    newNode->nextNode = '\0';
    newNode->prevNode = NULL;
    
    return newNode;
}
/* current 라는 노드 뒤에(after라는 노드 앞에) 노드를 새로 만들어 넣는 함수 */
struct Node* Insert(struct Node* current, int data){
    
    struct Node* after = current->nextNode;
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    newNode->data = data;
    newNode->nextNode = after;
    newNode->prevNode = current;
    current->nextNode = newNode;
    if(after!=NULL){
        after->prevNode = newNode;
    }
    
    return newNode;
}
/* 선택된 노드를 파괴하는 함수 */
void destroy(struct Node* destroy, struct Node* head){
    
    struct Node* next = head;
    
    if(destroy == head){
        free(destroy);
        return;
    }
    
    while(next){
        if(next->nextNode == destroy){
            next->nextNode = destroy->nextNode;
        }
        next = next->nextNode;
    }
    free(destroy);    
}
 
int Count(struct Node* head){
    int i=1;
    while(head->nextNode != NULL){
        i++;
        head = head->nextNode;
    }
    return i;
}
 
int Search(struct Node* head, struct Node* search){
    if(head==search){
        printf("head가 search입니다. %d\n",search->data);
    }
    while(head){
        if(head == search){
            printf("찾았습니다. %d\n",head->data);
            break;
        }
        else{
            head=head->nextNode;
            continue;
        }
    }
}
 
// 마지막 노드가 HEAD를 가리키게 만들어 준다.
void Circle(struct Node* head){
    struct Node* temp = head;
    while(temp->nextNode != NULL){
        temp = temp->nextNode;
    }
    //temp는 마지막 노드를 가리키게 된다. 
    struct Node* tail = temp;
    tail->nextNode = head;
    head->prevNode = tail;
}