[자료구조/C언어] - ③ 리스트 - 단순연결리스트 삽입,추가/삭제/생성

리스트는 두가지의 방법으로 만들어 줄 수 있습니다.

 

1. 배열

배열을 이용한 리스트는 가장 쉽게 사용할 수 있습니다.

그러나  몇가지 단점이 존재합니다.

   1. 동적으로 공간을 생성할 수 없다

      만약 배열의 크기가 100인데 실제 데이터는 10개밖에 없다면 공간낭비가 심하겠죠

   2. 리스트의 추가 삭제가 어렵다

     내가 지정한 위치에서 삭제 또는 추가를 한다면 뒤의 데이터를 모두 당기거나 밀어줘야합니다

 

 

2.단순연결리스트

​  단일연결리스트는 하나의 노드안에 실제 정보인 데이터필드

​  다음 노드를 가르키는 포인터 링크를 가지고 있습니다.

​

 

 

​

typedef struct Listnode{
 int data;
 struct Listnode *link;
}Listnode;

​이렇게 구조체를 이용하여 리스트노드를 만들어 준 뒤

​필요할 때마다 노드들을 삭제 생성하며 리스트를 구현하는 방법입니다. 

​

 

​

단순연결리스트는 main에서 head 포인터 하나면 모든 것을 해결할 수 있습니다.

​ head는 리스트의 가장 처음을 가르킵니다. 삭제나 추가를 할 때 헤드가 가르키는 곳은 바뀔수는 있지만

항상 맨 앞을 가르켜야합니다! 그리고 리스트의 가장 마지막 노드의 링크는 NULL 이여야 합니다.

​​

리스트를 구현하기 위해 필요한 기능들을 이제 만들어 보겠습니다

 

 

#include <stdio.h> #include <stdlib.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ typedef struct Listnode{ int data; struct Listnode *link; }Listnode; Listnode *createnode();//노드 생성 void addnode(Listnode *, int); //연결리스트에 노드 추가 void printnode(Listnode*); //전체 연결리스트 출력 int countnode(Listnode *); //전체가 몇개 int searchnode(Listnode *, int); //몇번째인 지 void insertnode(Listnode *,int,int); //리스트 중간에 찾는 값 뒤에 삽입 void insertnode2(Listnode *,int,int); //리스트 중간에 찾는 값 앞에 삽입 void deletenode(Listnode *,int); void reverse(Listnode *); /* p=h 복사 p=p->link 이동 p->link=n 연결 p->link=n->link : 연결정보만복사 데이터는 그대로 p=p->link->link: 2칸 이동 */ int main(int argc, char *argv[]) { Listnode *h; int i; h=createnode(); for(i=0;i<5;i++){ addnode(h,10+i); } printnode(h); printf("\n갯수:%d",countnode(h)); printf("\n위치(13):%d\n",searchnode(h,13)); insertnode(h,14,-2); printf("추가 14의 뒤에 -2\n"); printnode(h); printf("추가 -2의 앞에 -1\n"); insertnode2(h,-2,-1); printnode(h); printf("-2 삭제\n"); deletenode(h,-2); printnode(h); printf("12 삭제\n"); deletenode(h,12); printnode(h); printf("10 삭제\n"); deletenode(h,10); printnode(h); printf("뒤집기\n"); reverse(h); printnode(h); return 0; } Listnode *createnode(){ Listnode *p; p=(Listnode*)malloc(sizeof(Listnode)); p->data=0; p->link=NULL; return p; } void addnode(Listnode *h, int data){ Listnode *p, *q; q=createnode(); q->data=data; p=h; while(p->link!=NULL){ p=p->link; } p->link=q; } void printnode(Listnode* h){ Listnode *p; p=h; while(p->link!=NULL){ p=p->link; printf("%3d",p->data); } printf("\n"); } int countnode(Listnode *h){ Listnode *p; p=h; int cnt=0; while(p->link!=NULL){ p=p->link; cnt++; } return cnt; } int searchnode(Listnode *h, int m){ Listnode *p; p=h; int place; int cnt=0; while(p->link!=NULL){ p=p->link; cnt++; if(p->data==m) return cnt;; } return; } void insertnode(Listnode *h,int before,int after){ Listnode *p; Listnode *m; m=createnode(); m->data=after; p=h; int temp; while(p->link!=NULL){ p=p->link; if(p->data==before){ m->link=p->link; p->link=m; break; } } } void insertnode2(Listnode *h,int search,int add){ Listnode *p,*q; p=h; q=createnode(); q->data=add; while(p->link!=NULL){ if(p->link->data==search){ q->link=p->link; p->link=q; break; } p=p->link; } } void deletenode(Listnode *h,int search){ /*free 해줄때는 꼭 free해줄 위치에 가서 지움 지우기전에 지울 내용의 전 링크에 지울 내용의 후 링크를 복사해줘야 함 */ Listnode *p; Listnode *q; q=createnode(); p=h; while(p->link!=NULL){ q=p; p=p->link; if(p->data==search){ q->link=p->link; free(p); break; } } } void reverse(Listnode *h){ Listnode *p; Listnode *q; Listnode *r; q=NULL; r=NULL; p=h->link; while(p!=NULL){ r=q; q=p; p=p->link; q->link=r; } h->link=q; } <TEXTAREA/>

 

결과!

 

 

리스트 역순 아래링크 참고

http://euns2ol.tistory.com/6