C언어 자료구조 - 링크드리스트

1. LinkedList.h

#pragma once                    // 이 헤더파일 컴파일시 한 번만 실행하기
 
#ifndef LINKED_LIST_H            // LINKED_LIST_H가 정의되어 있지 않다면 정의하고, 이미 정의되어 있다면 재정의하지 않음
#define LINKED_LIST_H
 
/* 단일연결리스트 ADT - 데이터 타입 정의 */
typedef char Item;                // 노드의 데이터 타입 Item형 지정
 
typedef struct _Node{            /* 노드 구조체(자기참조 구조체) */
    Item data;                    // 노드 데이터
    struct _Node *next;            // 다음 노드에 대한 포인터
}Node;
 
typedef struct _LinkedList{        /* 연결리스트 구조체 */
    int size;                    // 연결리스트 항목수
    Node *head;                    // 헤드포인터 - 시작노드를 가리킴(시작노드 주소를 가짐)
}LinkedList;
 
typedef LinkedList List;        // LinkedList 타입명을 List로 재정의
 
/* 단일연결리스트 ADT - 연산 선언 */
void Init(List *list);            // 리스트 초기화
int isEmpty(List *list);        // 리스트가 비어있는지 확인
int getSize(List *list);        // 리스트의 크기(항목수) 반환
 
void Insert(List *list, int position, Item item);    // 원하는 위치에 데이터 삽입
void Delete(List *list, int position);                // 원하는 위치의 데이터 삭제
Item Retrieve(List *list, int position);            // 원하는 위치의 데이터 탐색
void Display(List *list);                            // 전체 리스트 내용 보여줌
 
void Insert_front(List *list, Item item);            // 리스트의 첫번째 위치에 데이터 추가
void Insert_rear(List *list, Item item);            // 리스트의 제일 끝에 데이터 추가
void Delete_front(List *list);                        // 리스트의 첫번째 위치 데이터 삭제
void Delete_rear(List *list);                        // 리스트 마지막 위치의 데이터 삭제
 
 
void Delete_item(List *list, Item item);            // 선택과제1
void Delete_all(List *list);                        // 선택과제2
void Insert_order(List *list, Item item);            // 선택과제3
 
#endif

2.LinkedList.c

#include <stdio.h>
#include <stdlib.h> 
#include "LinkedList.h"
 
void Init(List *list){
    list->size = 0;
    Node *head = NULL;
}
 
int getSize(List *list){
    return list->size;
}
int inEmpty(List *list){
    return list->size == 0 ? 1 : 0;
}
void Insert(List *list, int position, Item item){
    if (position< 1 || position>list->size + 1){
        printf("out of range\n");
    }
    else{
        Node *new_node = (Node*)malloc(sizeof(Node));
        new_node->data = item;
        if (position == 1){
            new_node->next = list->head;
            list->head = new_node;
        }
        else{
            Node *pre_node = list->head;
            for (int i = 1; i < position - 2; i++){
                pre_node = pre_node->next;
            }
            new_node->next = pre_node->next;
            pre_node->next = new_node;
        }
        list->size++;
    }
}
    void Display(List *list){
        if (isEmpty(list)){
            printf("list empty\n");
        }
        else{
            Node *P = list->head;
            for (int i = 1; i <= list->size; i++){
                printf("List[%d] : %c\n", i,P->data);
                P = P->next;
            }
        }
    }
}
    void Delete(List *list, int position){                                           
        if (isEmpty(list))
            printf("list empty\n");
        else if (position<1 || position >list->size)
            printf("out of range\n");
 
        else{
            Node *del_node;
            if (position == 1){
                del_node = list->head;
                list->head = del_node->next;
            }
            else{
                Node *pre_node = list->head;
                    for (int i = 1; i <; i++){
                        pre_node = pre_node -> next;
                    }
                    del_node = pre_node->next;
                    pre_node->next = del_node->next;
            }
            free(del_node);
            link -> size  -=1;
            return 1;
        }
    }
   Item Retrieve(List *list, int position) {
   if (isEmpty(list)) {
      printf("list empty\n");
   }
   else if (position < 1 || position > list->size) {
      printf("out of range\n");
   }
   else {
      Node *p = list->head;
      for (int i = 1; i < position; i++) {
         p = p->next;
      }
      return p->data;
   }
}

3.LinkedListMain.c

#include <stdio.h>
#include "LinkedList.h"
 
int main()
{
    List list1;
 
    Init(&list1);
 
    Insert(&list1, 1, 'A');
    Insert(&list1, 2, 'C');
    Insert(&list1, 3, 'E');
    Insert(&list1, 2, 'B');
    Insert(&list1, 4, 'D');
    Insert(&list1, 1, 'D');
 
    printf("[ 삽입연산 후 리스트 ]\n");
    Display(&list1);
 
    Delete(&list1, 3);
    printf("\n[ 3번째 데이터 삭제 후 리스트 ]\n");
    Display(&list1);
 
    printf("\n[ 2번째 위치의 데이터 찾기 ]\n");
    printf("%d번째 항목 %c\n", 2, Retrieve(&list1, 2));
 
    printf("\n[ 리스트 끝에 'F' 추가 후 리스트 ]\n");
    Insert_rear(&list1, 'F');
    Display(&list1);
 
    printf("\n[ 리스트 제일 앞에 'G' 추가 후 리스트 ]\n");
    Insert_front(&list1, 'G');
    Display(&list1);
 
    printf("\n[ 리스트 끝의 데이터 삭제 후 리스트 ]\n");
    Delete_rear(&list1);
    Display(&list1);
 
    printf("\n[ 리스트 제일 앞 데이터 삭제 후 리스트 ]\n");
    Delete_front(&list1);
    Display(&list1);
 
    printf("\n\n");
    return 0;
}