[알고리즘][c언어][c++] 링크드 리스트

알고리즘 프로 등급을 준비하기로 하였다..

입사 준비를 위해 DFS, BFS, 브루트포스, DP 등 과같은 알고리즘과 다른 방식으로 출제된다.

 

특정 자료구조를 활용한 문제가 나오기 때문에 우선 자료구조를 공부하기로 하였다.

 

어느 글에서 동적 할당대신 구조체 배열을 이용하여 링크드리스트를 만드는 글을 보았고

구연해 보았다.

 

특별한 것은 동적할당 없이 이미 선언된 노드 배열에서 노드를 가져온다.

주석을 달아 놓았다.

 

장점은 동적할당보다 속도가 우수하며 디버깅이 쉽단다!! 아직 활용을 안 해봐서 모르겠다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

#include <iostream>   int node_index;   // NODE 배열 선언 struct NODE {     int value;     NODE * preNODE; }node[1001];   // 호출 시 마다 NODE 반환 NODE * myalloc() {     if (node_index == 1000)         return NULL;       return &node[node_index++]; }   // NODE 삽입 void insert(NODE ** head, int value){       // NODE 하나 얻어옴     NODE * temp= myalloc();       if (temp == NULL){         printf("모든 노드 사용");         return;     }     // value값과 preNODE값 대입     temp->value = value;     temp->preNODE = *head;       // node가 추가되면 head값에 현재 NODE 주소를 저장     // 다른 NODE가 추가되면 이 주소를 preNODE에 대입     // 먼저 생긴 NODE의 값을 가지고 있는다.     *head = temp; }   // NODE 제거 void remove(NODE ** head, int value){       //head가 NULL인지 체크     if (*head == NULL)         return;     else if ((*head)->value == value){         *head = (*head)->preNODE;         return;     }       NODE * Temp = *head;       for (NODE * p = *head; p != NULL; p = p->preNODE){           //현재 노드의 앞에 노드의 value와 비교           if (value == p->preNODE->value){               //현재 노드 preNODE값을 변경!             p->preNODE = p->preNODE->preNODE;             return;         }         else if (p->preNODE == NULL){             return;         }     } }   int main() {     NODE * head = NULL;       // 0~9까지 value 값을 가지는 NODE 생성     for (int i = 0; i < 10; i++){         insert(&head, i);     }          // 노드가 제대로 생성되었는지 체크!!     for (NODE * p = head; p != NULL; p = p->preNODE) {         printf("%d \n", p->value);     }       printf("\n\n");     remove(&head, 0);     //remove(&head, 5);     printf("\n\n");     // 값이 잘 제거 되었는지 체크     for (NODE * p = head; p != NULL; p = p->preNODE){         printf("%d \n", p->value);     }     return 0; } Colored by Color Scripter

cs