연결리스트

<연결리스트의 필요성>

- 일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고, 나열할 수있다.

- 배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있다.

 

<배열기반리스트의 특징>

- 배열로 만들었으므로 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있다.

- 데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점이 있다.

- 원하는 위치로 삽입이나 삭제가 비효율적

 

 

<연결리스트>

- 일반적으로 연결리스트는 구조체와 포인터를 함께 사용하여 구현한다.

- 연결리스트는 리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 한다.

- 필요할 때마다 메모리 공간을 할당 받는다.

- 포인터를 이용해 단방향적으로 다음 노드를 가리킨다.

- 일반적으로 연결 리스트의 시작 노트를 헤드(Head)라고 하며 별도로 관리한다.

- 다음 노드가 없는 끝 노드의 다음 위치값으로는 NULL을 넣는다.

 

<코드구현>

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

//연결 리스트 구조체 만들기
typedef struct { 
    int data; 
    struct Node *next; 
} Node;

Node *head;

//연결 리스트 삽입함수
void addFront(Node *root, int data) { 
    Node *node = (Node*) malloc(sizeof(Node)); 
    node->data = data; 
    node->next = root->next; 
    root->next = node; 
}

//연결 리스트 삭제함수
void removeFront(Node *root) { 
    Node *front = root->next; 
    root->next = front->next; 
    free(front); 
}

//연결 리스트 메모리 해제 함수
void freeAll(Node *root) { 
    Node *cur = head->next; 
    while (cur != NULL) { 
        Node *next = cur->next; 
        free(cur); 
        cur = next; 
    } 
}

//연결 리스트 전체 출력 함수
void showAll(Node *root) {
    Node *cur = head->next; 
    while (cur != NULL) { 
        printf("%d ", cur->data); 
        cur = cur->next; 
    } 
}

// 완성된 연결 리스트 사용하기
int main(void) { 
    head = (Node*) malloc(sizeof(Node)); 
    head->next = NULL; 
    addFront(head, 2); 
    addFront(head, 1); 
    addFront(head, 7); 
    addFront(head, 9); 
    addFront(head, 8); 
    removeFront(head); 
    showAll(head); 
    freeAll(head); 
    system("pause"); 
    return 0; 
}