자료구조 공부#14 (연결리스트2)

2021.04.13 - [이론공부/자료구조] - 자료구조 공부#13 (연결리스트)

---

원형 연결리스트

마지막 노드의 링크가 첫 첫번째 노드를 가리키는 리스트

한 노드에서 다른 모든 노드로의 접근이 가능함

 

이전시간에 배운 단순 연결리스트에 비해 마지막, 처음 노드에 삽입하는 연산이 쉬워진다.

 

원형 연결리스트 구조

 

원형 연결 리스트에서 처음에 삽입하는 연산 구조

 

 

원형 연결 리스트에서 head->link가 가지고 있는 값을 새로 넣는 node->link에 담고. 기존 head->link에 있는값을 노드의 주소값을 넣는 구조

 

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; //(1)
        head->link = node; 		 //(2)
    }
    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; // (1)
        head->link = node;		 // (2)
        head = node;			 // (3)
    }
    return head; // 변경된 헤드포인터를 리턴
}

 

 

원형 연결 리스트 응용

원형큐를 연결리스트로 구현이 가능하다

 

 

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode {
	element data;
	struct  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; // (1)
		head->link = node; // (2)
	}
	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; // (1)
		head->link = node; // (2)
		head = node; // (3)
	}
	return head; // 변경된 헤드 포인터를 반환한다.
}


// 리스트의 항목 출력
void print_list(ListNode* head) {
	ListNode* p;
	if (head == NULL) return;
	p = head->link;
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (p != head);
	printf("%d->", p->data); // 마지막 노드 출력
}



int main(void) {
	ListNode* head = NULL;

	head = insert_last(head, 20);
	head = insert_last(head, 30);
	head = insert_last(head, 40);
	head = insert_first(head, 10);
	print_list(head);
	
	return 0;
}

수업 도중에 작성한 코드

---

느낀점 : 연결리스트의 구조를이해하자