[C언어] 단일 링크드리스트

연결 리스트란?

단일 링크드 리스트는 각각의 노드들이 데이터와 포인터를 가지고 있고, 
한 줄로 연결이 되어있는 자료구조 중 하나입니다.

배열의 단점인 중간에 데이터를 삽입, 삭제를 못하고, 
데이터를 정적으로 할당해줄수 없기때문에 비효율적입니다.

 

반면에 링크드리스트는 중간에 삽입,삭제,수정 등 이 가능하고

데이터를 malloc 함수를 이용해 동적으로 할당이 가능합니다.

 

 

제가 작성 한 코드는 추가 , 삽입 , 삭제 , 수정 , 출력 옵션이 있습니다.

 

사진 1-1

사진 1-1은 추가 옵션으로 노드가 3개 생성되었을 때의 그림입니다.

 

1. 이름, 나이: 구조체로 생성하여 이름과 나이를 각각 입력받아 데이터를 저장하는 멤버 변수입니다.
2. 주소 : 다음 노드의 주소를 가리킬 포인터입니다.
3. head : head는 처음 노드의 주소를 가리킬 포인터입니다.
4. tail : tail는 마지막 노드의 주소를 가르킬 포인터 입니다.

 

각각 노드들은 다음 노드의 주소를 알고 있어 서로 연결되어 있는 모습입니다.

 

 

사진 1-2

만약 노드 1과 노드 2 사이에 노드 4를 중간에 삽입하고 싶다면 사진 1-2과 같이 그림이 해석됩니다.

 

노드1의 포인터가 노드4를 가르키고 노드4의 포인터가 노드2를 가르키면,

노드들은 계속 연결이됩니다.

 

나머지 옵션들의 설명은 생략하겠습니다. 코드는 아래와 같습니다!

#include <stdio.h>
#include <stdlib.h>
typedef struct node{	
	char name[20];
	int age;	
	struct node* next;
}node;
int menual();
node* show(node* p);	
node* append(node* p);
node* insert(node* p); 
node* deletion(node* p);
node* update(node* p);
void heapfree(node* p);

void heapfree(node* p){
	node* tmp =p;
	while(p!=NULL){
		tmp=p->next;
		free(p);
		p=tmp;
	}
	printf("종료되었습니다!\n");
}

node* update(node* p){
	int n,a;
	int i;
	show(p);
	printf("수정하실 노드의 번호를 입력하세요!\n");
	scanf("%d",&n);
	
	if(n==1){
	printf("수정하실 이름을 입력하세요!\n");
	scanf("%s",p->name);
	printf("수정하실 나이를 입력하세요!\n");
	scanf("%d",&p->age);
		
	}	
	else{
	for(i=1; i<n; i++){
	p=p->next;	
	}
	
	printf("수정하실 이름을 입력하세요!\n");
	scanf("%s",p->name);
	printf("수정하실 나이를 입력하세요!\n");
	scanf("%d",&p->age);
	
	}
	return p;
}
node* deletion(node* p){
	node* start=p;
	int i,n;
	node* tmp;
 
	printf("삭제 하실 번호를 입력하세요!!\n");
	scanf("%d",&n);
	
	if(n==1){
		start=p->next;
		free(p);
	}
	else{
		for(i=1; i<n-1; i++){
		p=p->next;
		}
		
		tmp=p->next;
		p->next=p->next->next;
		p=p->next;
		free(tmp);
	}
	return start;
}
node* insert(node* p){
	int pos,i;
	node* item=(node*)malloc(sizeof(node));
	node* start=p;
	show(p); 
	
	printf("삽입하실 번호를 입력하세요!!.");
	scanf("%d",&pos);
	printf("삽입 할 이름을 입력하세요. ");
	scanf("%s",item->name);
	printf("삽입 할 나이를 입력하세요.");
	scanf("%d",&item->age);
	
	if(pos==1){
	item->next=start;
	start=item;
	}
	else{	
	for(i=1; i<pos-1; i++){
	p=p->next;	
	}
	item->next=p->next;
	p->next=item;
	}
	return start;
}
node* show(node* p){
	int i=0;	
	while(p->next!=NULL){
	printf("[%d]번째 %s %d\n",++i,p->name,p->age);		
	p=p->next;		
	}
	return p;
}
node* append(node* p){
	
	printf("추가 할 이름을 입력하세요.\n");
	fflush(stdin);
	gets(p->name);
	printf("추가 할 나이를 입력하세요.\n");
	scanf("%d",&p->age);
	
	p->next=(node*)malloc(sizeof(node));
	p=p->next;						
	p->next=NULL;
	return p;										
}
int menual(){
	int n;

	printf("1.추가\n");
	printf("2.출력\n");
	printf("3.삽입\n");
	printf("4.삭제\n");
	printf("5.수정\n");
	printf("6.종료\n");
	
	scanf("%d",&n);
	return n;
}
int main(){ 
	node* tail,*head=(node*)malloc(sizeof(node));
	head->next=NULL;
	tail=head;	
	while(1){	
	switch(menual()){
		case 1 :
			tail=append(tail);	
			break;
		case 2 :
			show(head);
			break;	
		case 3 :
			head=insert(head);	
			break;
		case 4 :
			head=deletion(head);
			break;
		case 5 :
			update(head);
			break;
		case 6:
			heapfree(head);
			break;
	}
}

	return 0;
}