List

리스트

• 배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당되므로, 이것을 리스트의 순차적 표현이라 함
• 일상생활에서의 리스트
  • 버킷 리스트
  • 해야 할 일 목록 등등…

리스트 구현

• init() : 리스트의 사이즈를 0으로 초기화

• isEmpty() : 리스트의 사이즈가 0이면 비어있음 1 리턴
• isFull() : 리스트의 사이즈가 리스트의 크기와 같으면 꽉 참 1리턴
• insertLast() : 리스트가 꽉 차있는지 확인 이후 리스트에 원소 삽입
• insert() : 리스트가 꽉 차있는지 확인 이후 원하는 Index에 원소 값 삽입 -> 원하는 Index의 값을 넣기 위해 값을 하나씩 미뤄넣고 넣어야 함
• deleteLast() : 리스트가 비어있는지 확인 후 리스트의 값을 삭제
• delete() : 리스트가 비어있는지 확인 후 원하는 Index에 원소값을 삭제 -> 원하는 Index의 값을 삭제 하기 위해 값을 삭제 후 Index를 하나씩 당겨야 함
• print() : 리스트의 값을 하나씩 출력

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100

typedef struct{
    int data[N];
    int size ;
}ListType;

void init(ListType *L){
    L->size = 0;
}

int isEmpty(ListType *L)
{
    return L->size == 0;
}

int isFull(ListType *L)
{
    return L->size == N;
}




void insertLast(ListType *L, int elem){
    if(isFull(L)){
        printf("List is Full!!!\n");
        return ;
    }
    else{
        L->data[L->size] = elem;
        L->size ++ ;
    }
}

void insert(ListType *L, int pos, int elem)
{
    if(isFull(L)){
        printf("FULL\n");
        return;
    }

    for(int i=L->size-1; i>=pos; i-- ){
        L->data[i+1] = L->data[i];
    }
    L->data[pos] = elem;
    L->size++;

}
int deleteLast(ListType *L){
    if(isEmpty(L)){
        printf("isEmpty\n");
        return -1;
    }
    int elem = L->data[L->size -1];
    L->size -- ;
    return elem;
}

int delete(ListType *L, int pos){
    if(isEmpty(L)){
        printf("isEmpty\n");
        return -1;
    }
    int elem = L->data[pos];
    for(int i=pos; i < L->size-1; i++)
        L->data[i] = L->data[i+1];
    L->size -- ;
    return elem;
}


void print(ListType *L){
    for(int i=0; i<L->size; i++){
        printf("%d -> ", L->data[i]);
    }
    printf("\b\b\b   \n");
}

int main(){

    ListType L;
    init(&L);

    insertLast(&L, 10); print(&L);
    insertLast(&L, 20); print(&L);
    insertLast(&L, 30); print(&L);
    getchar();
    insert(&L, 1, 40); print(&L);
    insert(&L, 0, 50); print(&L);
    insert(&L, 3, 60); print(&L);
    getchar();

    printf("[%d] is deleted.\n", deleteLast(&L)); print(&L);
    printf("[%d] is deleted.\n", delete(&L, 2)); print(&L);
    getchar();
    return 0;
}

연결된 표현(연결된 리스트)

• 리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장
• 노드(node)는 데이타 필드와 링크 필드로 구성
  • 데이타 필드 - 리스트의 원소 , 즉 데이타 값을 저장한는 곳
  • 링크 필드 - 다른 노드의 주소값을 저장하는 장소(포인터)

  노드(node) = 데이타 필드 + 링크필드

  # 포인터만 잘 설정해주면 삽입삭제가 기존 리스트보다 쉬움

• 장점 : 삽입, 삭제가 용이 , 연속된 메모리 공간이 필요없으며 크기 제한이 없다.
• 단점 : 구현이 어려우며, 오류가 발생하기 쉽다.

1. 단순 연결리스트(한방향) : 하나의 링크필드만 가지고 있고 마지막 링크필드의 값은 무조건 NULL 포인터가 멈추는 지점이 필요

2. 원형 연결리스트(끝에서 다시 처음으로) :
3. 이중 연결리스트(양방향) :

단순 연결리스트(한방향) 구현

#include <stdio.h>
#include <stdlib.h>


typedef struct ListNode{
    char data;
    struct ListNode* next ;

}ListNode; // Node의 구성요소 링크필드 + 데이타 필드

typedef struct{
    ListNode * Head;
}ListType; // 리스트 타입 리스트를 사용 시 이 타입을 선언

void init(ListType *L){
    L->Head = NULL;
}

void insertFirst(ListType *L, char elem){
    ListNode* node =(ListNode*) malloc(sizeof(ListNode)); // 동적으로 메모리 할당
    //Node 초기화
    node->data = elem;
    //데이터 초기화
    node->next = L->Head;
    // 널값 가져오기
    L->Head = node;
    // 이전 노드가 현재 노드를 가르키는 포인터
}

void insertLast(ListType *L, char elem){
    ListNode* node =(ListNode*) malloc(sizeof(ListNode)); // 동적으로 메모리 할당
    node->data = elem;
    node->next = NULL;

    ListNode* p = L->Head;

    if(p==NULL){
        L->Head = node;
    }
    else
    {
    while(p->next != NULL)
        p = p->next;
    p->next = node;
    }

}   

void print(ListType * L){
    ListNode* p; //리스트 노드를 가르키는 빨간 화살표

    for(p = L->Head; p != NULL; p = p->next){
        printf("%c->", p->data);
    }
    printf("\n");
}

int main(void){

    ListType L;
    init(&L);
    insertLast(&L, 'E'); print(&L);
    insertFirst(&L, 'A');  print(&L);
    insertFirst(&L, 'B');  print(&L);
    insertFirst(&L, 'C');  print(&L);
    getchar();

    insertLast(&L, 'D'); print(&L);
   
    return 0;
}