[자료구조] Double Linked List
코딩문제를 푸는데 힙은 나름 잘 구현하는데 Linked list만 나오면 막혀서… 이번에 짬내서 짜 보았다.
자신의 앞과 뒤를 가리키는 포인터를 가진 노드를 생성하고, 첫 번째 노드를 가리키는 head역할을 하는 자료구조를 별도로 생성했다.
노드의 추가는 맨 앞에 추가하는 것으로 만들었고,
삭제의 경우 같은 값을 가지는 모든 노드를 찾아 삭제하는 방식으로 했다.
|
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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include <stdio.h> #include <stdlib.h> #define MAX 100 //double linked list... typedef struct _node{ int v; struct _node *p ; struct _node *n ; } Node; typedef struct _head{ int cnt; Node *head; } Head; Head list[MAX]; void push(int v, Head *list){ Node *new = (Node *) malloc(sizeof(Node)) ; new->v = v; new->n = NULL; new->p = NULL; if(list->head == NULL) { list->head = new; list->cnt++; return; } new->n = list->head; list->head->p = new; list->head = new; list->cnt++; } void delete(int v, Head *list){ Node* cur = list->head; Node* next ; Node* prev ; while(cur){ next = cur->n; if (cur->v == v){ prev = cur->p; if (next) next->p = prev; if (prev) prev->n = next; else list->head = next; list->cnt--; free(cur); } cur = next; } } void print(Head *list){ Node *p = list->head; while(p){ printf("%d ", p->v); p = p->n; } printf(" , cnt : %d\n", list->cnt); } void init(){ for (int i = 0; i< MAX; i++){ Node *cur = list[i].head; Node *next; while(cur){ next = cur->n; free(cur); cur = next; } list[i].head = NULL; list[i].cnt = 0; } } int main(){ init(); push(1, &list[0]); push(2, &list[0]); push(3, &list[0]); push(1, &list[0]); push(2, &list[0]); push(3, &list[0]); print(&list[0]); delete(2, &list[0]); print(&list[0]); delete(3, &list[0]); print(&list[0]); init(); push(1, &list[0]); push(1, &list[0]); push(1, &list[0]); push(2, &list[0]); push(3, &list[0]); print(&list[0]); } |