연결 리스트

연결리스트

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

리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 합니다

포인터 기반의 연결리스트는 필요할 때마다 메모리 공간을 할당 받습니다

 

연결 리스트의 필요성

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

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

 

배열 기반의 리스트 예시

#include <stdio.h>
#define INF 10000
 
int arr[INF];
int count = 0;
 
void addBack(int data) {
    arr[count] = data;
    count++;
}
 
void addFirst(int data) {
    for (int i = count; i >= 1; i--) {
        arr[i] = arr[i - 1];
    }
    arr[0] = data;
    count++;
}
 
void removeAt(int index) {
    for (int i = index; i < count - 1; i++) {
        arr[i] = arr[i + 1];
    }
    count--;
}
 
void show() {
    for (int i = 0; i < count; i++) {
        printf("%d ", arr[i]);
    }
}
 
int main(void) {
    addBack(5);
    addBack(8);
    addBack(7);
    addFirst(3);
    addFirst(4);
    show();
}

#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int data;
    struct Node* next;
} Node;
 
Node* head;
 
int main(void) {
    head = (Node*)malloc(sizeof(Node));
    Node* node1 = (Node*)malloc(sizeof(Node));
    node1->data = 1;
    Node *node2 = (Node*)malloc(sizeof(Node));
    node2->data = 2;
    head->next = node1;
    node1->next = node2;
    node2->next = NULL;
    Node* cur = head->next;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    return 0;
}

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) {
        pritnf("%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);
    return 0;
}

 

연결 리스트 구현에 있어서 주의할 점

위 소스 코드들에 덧붙여서 삽입 및 삭제 기능에서의 예외 사항을 처리할 필요가 있습니다

(삭제할 원소가 없는데 삭제하는 경우, Head 노드 자체를 잘못 넣은 경우 등을 체크해야합니다)

 

연결 리스트의 특징

삽입과 삭제가 배열 기반 리스트의 비해서 간단합니다

배열 기반 리스트와 다르게 특정 인덱스로 즉시 접근하지 못하며, 원소를 차례대로 검색해야 합니다

추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비됩니다

 

삽입과 삭제가 많은 경우에서 효율적이지만

특정한 인덱스에 바로 참조해야 할 때가 많다면 배열을 이용하는 것이 효율적입니다