연결 리스트에 데이터를 삽입하고 삭제하는 방법

우선 간단히 구현을 했는데염~

 

이런 문제는 스스로 해보는 것이 님에게 도움되는 것이에영^^

 

소스와 주석을 드릴게염 연결리스트는 자료구조 책에 자세히 나와 있느니

 

한번 읽어 보시고 소스를 보시는 것도 많은 도움이 됩니다.

 

 

------------------------------------------------ 소스 ----------------------------------------

 

#include
#include

 

typedef struct _node
{
 int data;   //데이터 변수
 struct _node *link;   // 노드 포인터 변수
}NODE, *PNODE;

 

PNODE nalloc(int data)  //1개의 노드 생성
{
 PNODE n = malloc(sizeof(NODE));
 n -> data = data;
 n ->link = NULL;
 return n;
}

 

void print(PNODE p) 
{
 for( ; p ; p = p-> link)
  printf("%d\n", p->data);   //print...
}

 

PNODE nodeadd(PNODE head, int data)   //데이터를 각 노드에 저장하는 함수
{
 PNODE pp = NULL, p = head, n = nalloc(data);
 
 if(head == NULL)
  return n;
 if(n ->data data)
 {
  n ->link = p;
  return n;
 }   //앞쪽 정렬~~
 while(p && p->data data)  //p != NULL //!p
 {
  pp = p;
  p = p->link;
 }  //뒤쪽 정렬~~
 n->link = p;
 pp -> link = n;
 return head;
}

 

PNODE nodeRemove(PNODE head, int data)  //노드 삭제 함수
{
 PNODE pp = NULL, p = head;

 if(p->data == data) //삭제값이 첫번째 노드일때
 {
  pp = p->link;
  free(p);
  return pp;
 }
 
 while( p && data != p->data )  //끝까지 비교!!
 {
  pp = p;
  p = p ->link;
 }

 if(p == NULL || p->data != data) //찾는 값이 없을때
  puts("데이터 찾지 못함");
 else
 {
  pp->link = p->link;
  free(p);
 }

 return head;
 
}

 

void main()
{
 PNODE head = NULL;
 int i, n;

 for(i = 0 ; i  {
  head = nodeadd(head, rand()% 1000);   //랜덤으로 1000까지 숫자를 발생하여 각각의 노드에 저장
 }
 print(head);  //노드 데이터 출력 함수

 printf("삭제할 노드값 입력 :"); 
 scanf("%d", &n); //삭제할 값 입력

 head = nodeRemove(head, n);  //삭제값이 없으면 끝까지 검색하여 오류
 print(head); //삭제후 노드 데이터 출력 함수
}

 

 

우선 실행 해보시구여~

구현 내용은 랜덤으로 10개의 숫자를 발생 후 각 노드에 데이터 저장~

그리고 삭제값 입력 후 해당되는 노드를 삭제하는 것입니다..

더 궁금한 사항이 있으면 쪽지 보내세영

 

 

 ㅇ_ㅇ 휴.. 이거 어렵죠.

 그렇지만 도전할 충분한 가치가 있다고 생각합니다.

 연결리스트는 C를 배우는 사람에게 포인터란 개념을 확실히 심어줄수 있는

 녀석입니다. 개념을 잡지 못했다면 코드를 봐도 다음에 다시 작성할 수 없습니다.

 

 때문에 정답을 가리켜드리기 보단 스스로 할수 있도록 힌트를 드릴께요.

 직접 예제를 작성해보도록 하세요.

 

 거듭 당부하지만 연결리스트는 어려운 만큼 꼭 스스로 짜봐야 하는 것입니다.

 

 1. 연결리스트란.

  -> 연결리스트는 한개의 구조체 혹은 클래스가 다른 구조체나 클래스를 가지고

 있는 형식으로 겉으로 보이는 것은 1개의 구조체(클래스)이지만 그 안에는

 몇개가 들어있는지도 모를 정도로 길게 연결된 형식입니다.

 

 X -> Y -> Z -> A -> NULL

 

 이런 식으로 X는 Y를 가리키고 Y는 Z를 가리키도록 합니다.

 밖에서는 X 밖에 접근할수 없지만 내부의 포인터 변수를 따라 들어가면

 A까지 접근할수 있습니다.

 

2. 연결 리스트의 삽입 삭제 방법

 

 그렇다면 이것의 장점은 무엇일까요.

 바로 삽입과 삭제가 편리하다는 장점입니다. 언제나 연결리스트는 배열과 비교가

 되기 마련인데 배열의 경우 삽입시

 

 1 2 3 4 5   -> 2와 3 사이에 6을 삽입할 경우

 

 2 다음 3의 자리에 6을 넣고 3,4,5 는 한칸씩 뒤로 미루는 작업이 필요합니다.

 그렇지만 연결 리스트의 경우

 2가 6을 가리키도록 하고 6은 3을 가리키도록 하는 2번의 작업으로 끝내게 됩니다.

 

 만약 배열이 100개라면? 최악의 경우 100번의 루프를 돌아야 되지만

 연결리스트는 100개라도 최악의 경우 2줄의 코드만 있으면 됩니다.

 

 삭제의 경우도 마찬가지 입니다.

 2가 3을 가리키도록 하고 6을 날려버리면 삭제가 끝입니다.

 

 그렇지만 단점은 무엇이 있을까요.

 바로 검색에서 문제점이 나옵니다. 배열의 경우 A[3] 이러면 단번에 값을 가져오지만

 리스트의 경우 자신이 원하는 값을 가져오기 위해서 계속하여 루프를 돌아야 합니다.

 

 100개의 데이타를 가진 배열에서 1개의 숫자를 뽑는 것은 너무 간단합니다.

 그렇지만 100개의 연결리스트에서 1개의 숫자를 뽑는 것은 최악의 경우 100번의

 비교문이 사용되어야만 합니다.

 

 때문에 검색보다는 삽입과 삭제가 많이 사용되는 곳에서는 연결리스트로 데이타를

 관리하곤 합니다.

 

 3. 삽입/ 삭제에 대한 예제 코드

 

 위에서 말했다시피 코드는 직접 작성해야 하므로 삽입에 대해서만

 간략히 작성해 보도록 하겠습니다.

 

 struct Student

 {

      int nNumber; // 학생의 번호 기억

      Student* stuNext; // 다음 학생 구조체를 가리킴.

 };

 

 이런식의 구조체가 있을 경우

 

 Student* InsertAt(Student* stu)

 { // 들어오는 것은 Student의 포인터. 나가는 것도 Student의 포인터입니다.

   // 들어오고 나가는 포인터는 맨 첫 노드. 즉 1번의 예제에서 보았던

   //    X 위치에 있는 녀석입니다.

    Student* stuTemp = new Student; // 입력을 받습니다.

    int nTemp = 0;

    scanf("%d", &nTemp);

    stuTemp->stuNext = NULL; // 여기까지 입력입니다.

 

    if(stu == NULL) // 만약에 아무것도 없을 경우...

    {  stu = stuTemp;

        return stu; } // 새로 생성한 녀석이 첫번째가 됩니다. 그리고 그녀석을 돌려줍시다.

 

   Student* stuEndSearch = stu; // 이 문장은 포인터의 첫 값을 잊어먹지 않도록 임시로

   // 만들어두었습니다.

    while(stuEndSearch->stuNext != NULL) // 이 문장도 중요합니다. 끝이 나올때까지..

   //즉 뒤의 값이 NULL 끝일 때까지 반복합니다.

     {

          stuEndSearch = stuEndSearch->stuNext; // 이렇게 하여 계속 뒤로 넘어갑니다.

     }

   

     // 여기까지 왔으면 stuEndSearch는 맨마지막 값을 쥐고 있습니다.

     stuEndSearch->stuNext = stuTemp; // 이제 마지막에 새로 삽입할 녀석을 넣습니다.

     return stu;

 }

 

 자 어떻습니까..

 상당히 복잡하고 어렵게 보일 것입니다. 아무리 주석을 상세히 달아도

 "대체 저걸 왜 쓰지?" 란 생각을 품게 될 것입니다.

 

 개략적인 흐름은..

 

 1. 포인터가 비어 있을 경우 새로 생성한 녀석이 첫번째가 된다.

 2. 포인터가 차있을 경우 맨 뒤까지 찾아들어가면서 (while문) 끝까지 갑니다.

 3. 끝에 도착하면 맨 뒤에 노드를 끼워넣습니다.

 

 이 3줄 입니다.

 

 고민해 보시고 전 간단히 맨 뒤에 노드를 삽입하도록 하였는데.

 해보실때는 중간에 삽입도 가능하도록 작성해 보세요.

 

 의문나는 사항은 메일이나 쪽지로 물어보시고

 전체적인 코드는 원하지 마세요. 연결리스트는 필히 스스로의 힘으로 작성해야만

 하는 것입니다.