전글


이 장점을 생각하여 함수 구현에 대해생각해보면


이 함수를 구현하는데 필요한 인자는 3가지입니다.


앞노드의 정보,새노드의 데이터정보,후노드의 정보


하지만 노드생성 함수를통해 얻을수잇는 노드는 1가지입니다.


만약 다음 노드값이 존재하지 않는다면


혹은 연결된 다음노드가 존재한다면


다음노드는 어떻해처리해줘야할까요?



노드의 구성을 원형으로 생각해봅시다




여기서 새로운 개념이 등장합니다


노란색부분은 우리가 생성한 노드들이고


헤드와 테일이라는 새로운 부분이생겻습니다.


이두가지의 역활에대해 생각해봅시다


일단 헤드는 첫번쨰 노드의 주소를 가르키고있습니다


왜 첫번째 노드의 주소를 따로 저장해줘야할까요?


이질문에대해선 링크드리스트의 자료접근 방식에대해 알아야합니다.


링크드리스트는 첫번째 노드의 주소를통해 각노드에 접근을할수잇습니다.


헌데 이 첫번쨰 노드의 주소를 저장하지않는다면?


배열에서 int a[5];


에서 a값이 없는것과 같은이치입니다.


노드의 값들을 참조하거나 넣을수없지요


따라서 헤드라는 부분에 첫번쨰 노드의 주소값이 저장되어져야합니다.


마지막 테일부분에대해생각해봅시다


테일은 노드의형태로 다음노드의주소에 헤드주소를 저장하고잇습니다.


그렇기때문에 원형이라고 부르는것입니다.


노드를생성해서 붙여넣을떄 


노드를 맨앞에 추가하든 


노드와 노드 중간에 추가하든


맨마지막에 노드를 추가하든


항상 노드  와  노드 사이에 노드를 추가한다는 공통점을지니게됩니다.


따라서 함수를 한가지유형으로만 구현해줄수있게됩니다.


이 개념을 바탕으로 노드를 연결하는 함수를 구현해봅시다.


헤드와테일은 노드생성함수를이용해 이름만 head,tail로 지정해줍시다


그리고 두값을 연결시켜봅시다.


struct Node* head;

struct Node* tail;

head->next=tail;

head->preb=tail;

tail->next=head;

tail->preb=head;


이제 연결된 이두 노드 사이에 노드를 추가할수잇는 함수를 구현해봅시다.


함수의 이름은 insertNode이며 인자로는


전노드의 주소와


저장되어질 데이터의 주소를 받고잇습니다.


struct Node* insertNode(struct node* preb,void* data);


이제 새로운 노드를 선언해봅시다.


stucrt node * NewNode=CreateNode(data);


NewNode란 이름으로 노드를 생성햇고


인자로받앗던 데이터를 넘겨줬습니다.


prev->next->prev=NewNode;


전노드의 다음노드값의 전노드값에 새로 생성한 노드값을 넣어줫습니다.


NewNode->next=prev->next;



새로생성한 노드의 next값에 전노드의 next값을 넣어주엇습니다


preb->next=NewNode;


전노드의 next값에 새로 추가한 노드의 주소값을 넣어주엇습니다.


NewNode->preb=preb;


새로생성한 노드에 전노드의 주소를 넣어주엇습니다.



이제 마지막으로 리턴값에 새로 할당한 노드값을 리턴해줍시다.


함수의 구성이 완료된거같으니 정리해봅시다.


struct Node* insertNode(struct node* preb,void* data)

{

stucrt node * NewNode=CreateNode(data);

prev->next->prev=NewNode;

NewNode->next=prev->next;

preb->next=NewNode;

NewNode->preb=preb;



return NewNode;

}



이제 노드들을 생성하고 연결하는 작업을 해보겟습니다.


예제를통해알아보죠


#include <stdio.h>

#include <string.h>

#include <stdlib.h>


struct Node{                             //노드구조체 선언

        Node* next;

        Node* preb;

        void* data;

};

struct Node* CreateNode(void * data)           //노드생성함수

{

struct Node* NewNode=(struct Node*)malloc(sizeof(struct Node));

NewNode->data=data;

NewNode->next=NULL;

NewNode->preb=NULL;

return NewNode;

}


struct Node* insertNode(struct Node* preb,void* data)        //노드추가함수

{

struct Node* NewNode=CreateNode(data);

preb->next->preb=NewNode;

NewNode->next=preb->next;

preb->next=NewNode;

NewNode->preb=preb;



return NewNode;

}


int main()           //메인함수

{

        struct Node * head=CreateNode(NULL);

        struct Node * tail=CreateNode(NULL);

        head->preb=tail;                                          // 헤드와 테일 묶어주는작업

        head->next=tail;

        tail->preb=head;

        tail->next=head;

        int a;

        scanf("%d",&a);


        struct Node* Current=insertNode(head,(void*)a);            


 //현재 노드의 정보를 Current 변수에 담고있습니다


        while(1)                 //입력값이 -1일때까지 링크드리스트에 자료를 집어넣습니다.

        {

                a=0;

                scanf("%d",&a);

                Current=insertNode(Current,(void*)a);

                if(a==-1) break;

        }

        Current=head->next;

        while(Current!=head)         //입력값을 출력합니다.

        {

                

                printf("%dn",(int)(Current->data));

                Current=Current->next;

        }

                

}




이렇게해서 링크드 리스트에대한 설명이 끝낫습니다.


궁금한점이나 의문점이 있으시면 댓글을 달아주시면 감사하겟습니다.



-----------------------------------------------



잘이해가안되서 남들한테 설명한다는 입장에서 공부햇슴..


혹시 틀린점이나 부족한점 궁금즘있으면 댓글좀달아줘