[자료구조] 연결리스트(Linked List)

-구조체와 포인터로 구현

 

장점

 

*중간 삽입/ 삭제가 쉽다. (주소를 알아내서 서로 연결만 해 주면 된다.)

*배열의 크기를 동적으로 할당받을 수 있다.

 

단점

 

*탐색 시간이 오래 걸린다. (타고 타고 들어가야 한다.)

*포인터의 개념이 있기 때문에 한 번에 이해하기 어렵다

 

 

?

1 2 3 4

void addFirst(List *target, int data); void addLast(List *target, int data); void deleteEle(List*target, int pos); int isEmpty(List *target);

?

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

#include <stdio.h> #include <stdlib.h>   struct ListNode {     int data;     struct ListNode *next; };   struct List{     struct ListNode *head; };   void addFirst(List *target, int data) {     ListNode *tmp = (ListNode *) malloc(sizeof(ListNode));     tmp->data=data;     if (target->head == NULL) {         tmp->next = NULL;         target->head = tmp;     }     else {         //맨 앞에 놓고 뒤랑 이어준다.         tmp->next = target->head;         target->head = tmp;     } } void addLast(List *target, int data) {     ListNode *tmp = new ListNode;     tmp->data = data;       if (target->head == NULL) {         target->head = tmp;         tmp->next = NULL;     }     else {         //맨 뒤의 값과 이어준다.         ListNode *cur = target->head;         while(cur->next != NULL) {             cur = cur->next;                       }           cur->next = tmp;         tmp->next = NULL;     } }   int isEmpty(List *target) {     if (target->head == NULL) return 1;     return 0; } void deleteEle(List *target, int pos) {     if (isEmpty(target)) return;       ListNode *cur = target->head;     ListNode *pre = NULL;     if (pos == 1) {         //헤드를 없앰         target->head = cur->next;         delete cur;     }     else {         int idx = 1;         while(idx < pos) {             pre = cur;             cur = cur->next;             idx++;         }         pre->next = cur->next;         delete cur;     } } void printList(List *target) {     ListNode *cur = target->head;     while(cur) {         printf("%d ", cur->data);         cur=cur->next;     }     printf("\n"); } int main() {     List *list = new List;     list->head = NULL;     for (int i = 1; i <= 7; i++)     {         addLast(list, i);         printList(list);     }       deleteEle(list, 7);     printList(list);       deleteEle(list, 2);     printList(list);     return 0;   }