C언어 연결리스트 구현

1 개요[ | ]

C언어 링크드 리스트, 연결 리스트
C Language Linked LIst

C언어에서 링크드 리스트 구현

2 예시 1[ | ]

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

// 노드 타입 정의
typedef struct nodeTag {
    int v;
    struct nodeTag *next;
} nodeType;

// 노드 생성 - malloc() 함수로 공간을 확보한 뒤 v값을 넣어주고 생성된 공간의 주소를 돌려준다.
nodeType* createNode(int v) {
    nodeType *p;
    p = malloc(sizeof(nodeType));
    p->v = v;
    p->next = NULL;
    return p;
}

/*
void destroyNode(nodeType **node) {
    free(*node);
    *node = NULL;
}
*/

// 노드 추가 
void appendNode(nodeType **head, nodeType *newNode) {
    nodeType *ptr = *head;
    if(ptr == NULL) {
    	*head = newNode;
    }
    else {
    	while(ptr->next != NULL) {
    		ptr = ptr->next;
    	}
    	ptr->next = newNode;
    }
}

// 선택 위치에 노드 추가
void insertAfter(nodeType *ptr, nodeType *newNode) {
    newNode->next = ptr->next;
    ptr->next = newNode;
}

// 노드 가져오기 - 인덱스에 해당하는 노드를 가져옴
nodeType *getNode(nodeType *head, int index) {
    nodeType *ptr = head;
    while(ptr->next != NULL && index > 0) {
    	index--;
    	ptr = ptr->next;
    }
    return ptr;
}

// 노드 출력
void printList(nodeType *head) {
    nodeType *ptr = head;
    while(ptr != NULL) {
    	printf("%d\n", ptr->v);
    	ptr = ptr->next;
    }
}

int main() {
    // 링크드 리스트 헤드 포인터 생성
    nodeType *head = NULL;
    nodeType *ptr;
    
    // 1, 2, 3, 4의 값을 가지는 각각의 노드를 head에 추가
    appendNode(&head, createNode(1));
    appendNode(&head, createNode(2));
    appendNode(&head, createNode(3));
    appendNode(&head, createNode(4));
    
    // 전체 노드 출력
    printList(head);
    
    // 인덱스 1에 해당하는 노드 가져오기
    ptr = getNode(head, 1);
    // 그 노드 뒤에 33 값을 가지는 노드를 추가
    insertAfter(ptr, createNode(33));
    
    // 전체 노드 출력
    printf("---\n");
    printList(head);
}

→ appendNode()에서 보면 head를 이중 포인터로 넘겨 주는데, 이 경우는 head의 값 자체의 수정이 필요하기 때문이다.

3 예시 2[ | ]

#include<stdio.h>
#include<malloc.h>

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->prev = NULL;
    node->next = NULL;
    node->data = data;
    return node;
}

Node* insertAfter(Node* head, Node* newNode) {
    Node* next = head->next;
    head->next = newNode;
    newNode->next = next;
    newNode->prev = head;
    if (next != NULL) {
        next->prev = newNode;
    }
    return newNode;
}

int removeByData(Node* head, int data) {
    Node* it = head->next;
    int removedCount = 0;
    while (it != NULL) {
        if (it->data == data) {
            Node* prev = it->prev;
            Node* next = it->next;
            Node* tmp = it;
            it = it->next;
            prev->next = next;
            if (next != NULL) {
                next->prev = prev;
            }
            free(tmp);
            removedCount++;
        } else {
            it = it->next;
        }
    }
    return removedCount;
}

void printList(Node* head) {
    for (Node* it = head->next; it != NULL; it = it->next) {
        printf("%d ", it->data);
    }
    printf("\n");
}

int main() {
    Node* head = createNode(0); // 더미 헤드
    Node* node1 = createNode(1);
    Node* node2 = createNode(2);
    Node* node3 = createNode(3);

    insertAfter(head, node1);
    insertAfter(node1, node2);
    insertAfter(node2, node3);

    printList(head); // 1 2 3
    removeByData(head, 2);
    printList(head); // 1 3

    // 메모리 해제
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }
}

4 같이 보기[ | ]