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

-구조체와 포인터로 구현

 

장점

 

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

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

 

단점

 

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

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

 

 

void addFirst(List *target, int data); void addLast(List *target, int data); void deleteEle(List*target, int pos); int isEmpty(List *target); #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; }