본문 바로가기
DSA

리스트 2(Linked List)

by KWONE 2024. 10. 28.

노드 정의:


  
//노드의 정의
typedef int element;
typedef struct ListNode {
element data;
struct ListNode *link;
}ListNode;

삽입 연산:


  
//삽입 연산
ListNode* insert_first(ListNode *head,element value) {
ListNode *p=(ListNode*)malloc(sizeof(ListNode));;
p->data=value;
p->link=head;
head=p;
return head;
}
ListNode* insert(ListNode *head,ListNode *pre,element value) {
ListNode *p=(ListNode*)malloc(sizeof(ListNode));
p->data=value;
p->link=pre->link;
pre->link=p;
return head;
}

삭제 연산:


  
//삭제 연산
ListNode* delete_first(ListNode *head) {
ListNode *removed;
if(head==NULL) return NULL;
removed=head;
head=head->link;
free(removed);
return head;
}
ListNode* delete(ListNode *head,ListNode *pre) {
ListNode *removed;
removed=pre->link;
pre->link=removed->link;
free(removed);
return head;
}

출력 연산(리스트 방문 알고리즘):


  
//출력 연산(리스트 방문 알고리즘)
void print_list(ListNode *head) {
for(ListNode *p=head;p!=NULL;p=p->link) {
printf("%d->",p->data);
}
printf("NULL \n");
}

for문에서 p가 p->link를 타고 다음 노드로 가고 다시 다음노드의 링크를 타고 가다 결국 NULL값이 나올때(마지막)까지 탐색


탐색 연산:


  
ListNode* search_list(ListNode *head,element x) {
ListNode *p=head;
while(p!=NULL) {
if(p->data==x) return p;
p=p->link;
}
return NULL; //탐색 실패
}

탐색 예시:


  
int main(void) {
ListNode *head=NULL;
for(int i=0;i<5;i++) {
head=insert_first(head,i);
print_list(head);
}
if(search_list(head,3) != NULL) {
printf("리스트에서 3을 찾았습니다. \n");
}
else {
printf("리스트에서 3을 찾지 못했습니다. \n");
}
return 0;
}

출력:

 


리스트 합체 연산:


  
ListNode* concat_list(ListNode* head1,ListNode* head2) {
if(head1==NULL) return head2;
else if(head2==NULL) return head1;
else {
ListNode *p;
p=head1;
while(p->link!=NULL) { //p에 head1으로 시작하는 리스트 복제
p=p->link;
}
p->link=head2; //복제된 head1인 p->link에 head2연결
return head1; //head1+head2로 이어진 리스트 반환
}
}

  
int main(void){
ListNode* headl = NULL;
ListNode* head2 = NULL;
headl = insert_first (headl, 10);
head1 = insert_first(headl, 20);
headl = insert_first(headl, 30);
print_list (head1);
head2 = insert_first(head2, 40);
head2 = insert_ first(head2, 50);
print_list(head2);
ListNode *total = concat_ list(headl, head2);
print_list(total);
return 0;
}


전체 코드:


  
#include <stdio.h>
#include <stdlib.h>
//노드의 정의
typedef int element;
typedef struct ListNode {
element data;
struct ListNode *link;
}ListNode;
/*
//공백 리스트의 생성 (헤드포인터가 NULL이면 공백이다.)
ListNode *head=NULL;
//노드의 생성
head = (ListNode *)malloc(sizeof(ListNode));
head->data=10;
head->link=NULL;
//노드의 연결
ListNode *p;
p=(ListNode *)malloc(sizeof(ListNode));
p->data=20;
p->link=NULL;
head->link=p;
*/
//삽입 연산
ListNode* insert_first(ListNode *head,element value) {
ListNode *p=(ListNode*)malloc(sizeof(ListNode));;
p->data=value;
p->link=head;
head=p;
return head;
}
ListNode* insert(ListNode *head,ListNode *pre,element value) {
ListNode *p=(ListNode*)malloc(sizeof(ListNode));
p->data=value;
p->link=pre->link;
pre->link=p;
return head;
}
//삭제 연산
ListNode* delete_first(ListNode *head) {
ListNode *removed;
if(head==NULL) return NULL;
removed=head;
head=head->link;
free(removed);
return head;
}
ListNode* delete(ListNode *head,ListNode *pre) {
ListNode *removed;
removed=pre->link;
pre->link=removed->link;
free(removed);
return head;
}
//출력 연산(리스트 방문 알고리즘)
void print_list(ListNode *head) {
for(ListNode *p=head;p!=NULL;p=p->link) {
printf("%d->",p->data);
}
printf("NULL \n");
}
int main(void) {
ListNode *head=NULL;
for(int i=0;i<5;i++) {
head=insert_first(head,i);
print_list(head);
}
for(int i=0;i<5;i++) {
head=delete_first(head);
print_list(head);
}
return 0;
}