4. 리스트 - 2
* 방문 함수
void display(ListNode *head) { ListNode *p = head; while(p != NULL) { printf("%d->", p->data); p = p->link; } printf("\n"); } |
* 탐색 함수
ListNode *search(ListNode *head, int x) { ListNode *p; p = head; while(p != NULL) { if(p->data == x) return p; p = p->link; } return p; } |
* 합병 함수
ListNode *concat(ListNode *head1, ListNode *head2) { ListNode *p; if(head1 == NULL) return head2; else if(head2 == NULL) return head1; else { p = head1; while(p->link != NULL) p = p->link; p->link = head2; return head1; } } |
* 역순 함수
ListNode *reverse(ListNode *head) { ListNode *p, *q, *r; p = head; q = NULL; while(p != NULL) { r = q; q = p; p = p->link; q->link = r; } return q; } |
* 원형 연결 리스트
- 마지막 노드의 링크가 첫번째 노드를 가리키는 리스트
- 한 노드에서 다른 모든 노드로의 접근이 가능
- 헤드 포인터가 마지막 노드를 가리키면 처음이나 마지막에 노드 삽입하기 용이
1. 리스트의 처음에 삽입
void insert_first(ListNode **phead, ListNode *node) { if(*phead == NULL) { node->link = node; *phead = node; } else { node->link = (*phead)->link; (*phead)->link = node; } } |
2. 리스트의 끝에 삽입
void insert_last(ListNode **phead, ListNode *node) { if(*phead == NULL) { node->link = node; *phead = node; } else { node->link = (*phead)->link; (*phead)->link = node; *phead = node; } } |
* 헤드 노드
- 데이터를 가지지 않음
- 단지 삽입, 삭제 코드를 간단하게 하기 위해 만들어진 노드
- 헤드 포인터와 다름
- 공백 상태에서 헤드 노드만 존재
* 이중 연결 리스트
- 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
- 링크가 양방향이므로 양방향 검색 가능
- 공간 많이 차지
- 코드 복잡
- 실제 사용되는 이중 연결 리스트의 형태 : 헤드노드 + 이중연결 + 원형연결
1. 노드의 구조
typedef int element; typedef struct DlistNode { element data; struct DlistNode *llink; struct DlistNode *rlink; } DlistNode; |
2. 삽입 연산
void dinsert_node(DlistNode *before, DlistNode *new_node) { new_node->llink = before; new_node->rlink = before->rlink; before->rlink->llink = new_node; before->rlink = new_node; } |
3. 삭제 연산
void dremove_node(DlistNode *phead_node, DlistNode *removed) { if(removed == phead_node) return; removed->llink->rlink = removed->rlink; removed->rlink->llink = removed->llink; free(removed); } |