고급 연결 리스트

연결리스트 처음과 마지막 노드 삽입/삭제

• 연결리스트의 처음과 마지막에 노드를 삽입 삭제 할 경우 노드 수 n과 노드를 삭제하려면 앞 노드의 주소를 알아야한다
• 시간 복잡도 → O(n)

원형 연결 리스트

정의

• 연결리스트의 맨 끝 노드를 첫 번째 노드와 연결시켜서 원형으로 만든 리스트
• 단순 연결리스트의 마지막 노드를 끝 노드와 연결 시켰다

예시

• 리스트를 원형으로 만든 다음 리스트의 포인터가 마지막을 가리킨다. 그 후 리스트의 처음과 마지막에 노드를 삽입하는 경우를 살펴보자.

 

문제

void delete_first(list_ptr *ptr){
if ((*ptr)==NULL){ printf("원소 없음");} //빈리스트
else{
/* 원형리스트의 맨 앞 부분을 삭제하는 함수 */
//ptr의 링크 값을 바꿔야한다. 
(*ptr)->link=(*ptr)->link->link;

}

int length(list_ptr *ptr){
if ((*ptr)==NULL){ return 0;} //빈리스트
else{
int *i=(*ptr);
int count=0;
/* 원형리스트의 길이를 세는 함수 */. 
while(i!= null){
&i=(*i)->link;
count++
}
return count;
}}

/* DBLAB circularlist.c */
#include <stdio.h>
#include <malloc.h>

struct node {
        int data;
        struct node * link;
};
typedef struct node list_node;
typedef list_node * list_ptr;

list_ptr create(int n) {
   list_ptr first=NULL, temp=NULL;
   int i;
   for(i=0; i < n; i++)
   {     
     temp = (list_ptr)malloc(sizeof(list_node));  
     temp->data=(i+1); /* 리스트의 값 */  
     temp->link=first; /* 새로운 노드를 리스트의 맨 앞에 삽입한다. */  
     first = temp; 
   } 

   for(temp=first; temp->link; )
   {  temp=temp->link; }
   temp->link=first;  
   return temp; /* 마지막 노드 포인터 반환 */
} 

int add(list_ptr ptr) { 
        list_ptr last=ptr; int s=0;
        printf("The list contains: ");
		do
		{  ptr=ptr->link; s=s+ptr->data;
		   printf("%4d", ptr->data); }
        while(ptr!=last); 
        return s;  
} 
void print_list(list_ptr ptr) { 
        list_ptr last=ptr;
        printf("The list contains: ");
		do
		{  ptr=ptr->link;
		   printf("%4d", ptr->data); }
        while(ptr!=last); 
        printf("\\n");  
} 
   
int main()
{       
	list_ptr ptr = NULL;
        ptr = create(4); /* 4개의 노드를 가진 연결리스트를 만든다 */
        print_list(ptr);
		printf("\\naddition %d\\n", add(ptr));

}