C언어 연결리스트 (linked list)

구조체 알아보러 가기

포인터 알아보러 가기

연결리스트는 C에서 쉽게 구현할 수 있는 실용적인 데이터 저장방법입니다.

연결리스트의 각 데이터 항목은 구조체에 포함되어 있는데, 구조체는 데이터를 저장하는데 필요한 요소들을 가지고 있습니다. 구조체에 포인터가 가미되면 바로 연결리스트가 되는 것이죠.

struct person{

char name[20];

struct person *next;

};

person이라는 구조체를 정의하고, 데이터만을 이야기 한다면 person은 단지 20개의 요소로 구성되는 문자형 배열입니다.

 

 

data

next pointer

이 next pointer가 밑의 다음 구조체의 data에 연결되고, 

data

next pointer

 이 next pointer가 밑의 다음 구조체의 data에 연결되고,

data

next pointer

 이 next pointer가 NULL 값을 가리키게 됩니다.

연결리스트를 사용할 때는 각 링크를 추가, 삭제, 변경할 수 있어야 합니다. 링크를 변경하는 것은 어렵지 않지만, 링크를 추가하고 삭제하는 것은 약간 복잡합니다.

struct person{

char name[20];

struct person *next;

};

struct person *new;

struct person *head;

head = NULL;

이제 연결리스트의 시작 부분에 링크를 추가해 보겠습니다.

만약 head 포인터가 NULL값이면 연결리스트는 비어있는 것이고, 새로운 링크는 유일한 멤버가 됩니다. 만약, head 포인터가 NULL값이 아니라면 연결리스트는 이미 하나 이상의 링크를 가지고 있는 것이라 볼 수 있습니다.

먼저, malloc()을 이용하여 메모리 공간을 할당하고, 구조체형 변수를 생성합니다.

그다음 새로운 링크의 next 포인터를 head 포인터의 현재 값으로 설정합니다. 연결리스트가 비어 있다면 NULL값이 될 것이고, 그렇지 않다면 첫 번째 링크의 주소가 될 것입니다.

new = (person*)malloc(sizeof(struct person));

new->next = head;

head = new;

이 구문은 바로 위에서 설명해드린 연결리스트의 시작 부분에 링크를 추가하는 방법입니다.

예제를 보겠습니다.

 

#include <stdio.h> #include <stdlib.h> #include <string.h> struct data {  char name[20];  struct data *next; };  //연결리스트 data 구조체 typedef struct data PERSON; //구조체에 대한 typedef형을 정의하고 typedef PERSON * LINK;  //포인터를 사용해서 가리킵니다 /* 굳이 typedef형이 반드시 필요한건 아닙니다만, struct data 대신에 PERSON을 사용하고 struct data* 대신에 LINK를 사용하게 해줌으로써 코드를 단순화 할 수 있습니다. */ main(){  LINK head = NULL;  LINK newp = NULL;  LINK current = NULL; //head, newp, current에 대한 요소 포인터입니다.  newp = (LINK)malloc(sizeof(PERSON)); //첫번째 요소를 추가합니다.  newp->next = head;      //이 예제에선 연결리스트가 비어있지 않은 것으로 가정합니다.  head = newp;  strcpy(newp->name, "Abigail");  current = head;       //연결리스트의 마지막에 요소를 추가합니다.  while(current->next != NULL)  {   current = current->next;  }  newp = (LINK)malloc(sizeof(PERSON));  current->next = newp;  newp->next = NULL;  strcpy(newp->name,"Catherine");  newp = (LINK)malloc(sizeof(PERSON)); //연결리스트의 두번째 위치에 새로운 요소를 추가합니다.  newp->next = head->next;  head->next = newp;  strcpy(newp->name, "Beatrice");  current = head;  //모든 데이터 항목을 차례대로 출력합니다.  while(current !=NULL)  {   printf("%s\n", current->name);   current = current->next;  }  printf("\n"); }