원형 연결리스트

[정다훈]

원형 연결 리스트의 구조

- 마지막 노드가 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결리스트

==> 마지막 노드의 링크필드가 NULL이 아닌, 첫번째 노드의 주소이다.

장점

- 하나의 노드에서 다른 모든 노드로의 접근이 가능

- 하나의 노드를 따라가다보면 다시 자기 자신으로 돌아옴

- 특히, 리스트의 끝에 노드를 삽입하는 연산이 단순 연결리스트보다 효율적 --> 헤드 포인터가 마지막 노드를 가리키도록 구성

처음과 끝에 보다 쉽게 삽입 및 삭제 가능

원형 연결 리스트의 구현

- 마지막 노드의 링크를 첫번째 노드로 연결

- 공백 리스트인 경우: 삽입하는 노드가 리스트의 첫번째 노드이자 마지막 노드이다. (링크에 NULL이 아닌 자기자신의 주소)

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

#include <stdio.h> #include <stdlib.h>   typedef int element; typedef struct {     element data;     ListNode* link; }ListNode;   ListNode* insert_first(ListNode* head, element data) {     ListNode* node = (ListNode*)malloc(sizeof(ListNode));     node->data = data;       if (head == NULL) {         head = node;         node->link = head;     }     else {         node->link = head->link; //새로운 노드의 링크가 첫번째 노드를 가리키게함         head->link = node;      }     return head; }   ListNode* insert_last(ListNode* head, element data) {     ListNode* node = (ListNode*)malloc(sizeof(ListNode));     node->data = data;       if (head == NULL) {         head = node;         node->link = head;     }     else {         node->link = head->link; //끝에 추가된 노드의 링크를 첫번째 노드를 가리키게함         head->link = node; //추가된 노드 이전 노드의 링크는 추가된 노드를 가리키게함         head = node; //head의 위치만 새로운 노드로 바꾸어줌 ->새로운 노드는 마지막 노드가 됨     }     return head; } Colored by Color Scripter

cs

이중 연결 리스트의 구현

# 삽입

new_node 왼쪽 링크를 before로 설정

new_node 오른쪽 링크를 before->rlink로 설정

before->rlink->llink = new_node

before->rlink = new_node