[자료구조]C언어 연결리스트(linked list) 구현, 소스코드

안녕하세요 오늘은 자료구조의 연결 리스트를알아보겠습니다.

 

리스트란 순서를 가진 항목들의 모임이라고 할 수 있습니다.

 

예를 들어 요일(월화수목금토일), 한글자음(ㄱㄴㄷ...) 등 순서가 있는 항목들로 이루어진 집합입니다.

 

기존의 배열과는 다르게 메모리를 동적으로 할당하여 메모리의 낭비없이 자유롭게 삽입 및 삭제가 가능하고,

 

그 크기가 제한되지 않습니다.

 

다만, 구현이 복잡한 단점이 있습니다.

 

 

 

위의 그림처럼 하나의 박스를 노드(Node)라고 하는데,

 

한 노드에는 데이터필드와 링크필드로 구성되어있습니다.

 

데이터필드는 해당 노드의 값이고 링크필드는 다음에 오는 노드를 가리키는 포인터값이 들어갑니다.

 

가장 첫 노드를 가리키는 포인터는 헤드포인터, 가장 마지막노드가 가리키는 link값은 NULL이 들어갑니다.

 

 

typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode *link;
}ListNode;

 

위와 같이 구조체로 리스트노드를 생성하고 그 안에는 element와 *link 값으로 구성되어집니다.

 

그럼 노드의 생성은 어떻게할까요?

 

아까 위에 말했듯이, 메모리를 동적으로 할당하기 때문에

 

#include<malloc.h> 를 반드시 써줘야 합니다.

 

ListNode *p1,*p2;
p1=(ListNode *)malloc(sizeof(ListNode));
p2=(ListNode *)malloc(sizeof(ListNode));
    
p1->data=10;
p1->link=p2;
p2->data=20;    
p2->link=NULL;

 

 

 위처럼 malloc함수를 사용하여 ListNode의 크기만큼 동적으로 할당해줍니다.

 

위와같이 작성하게 되면 p1을 시작노드로 data가 10, 다음노드는 p2, p2의 데이터는 20, 다음노드는 NULL이 됩니다.

 

그럼 리스트내의 모든 데이터를 출력해보는 함수를 작성해보겠습니다.

 

void display(ListNode *head){
    ListNode *p=head;
    while(p!=NULL){
        printf("%d\n", p->data);
        p=p->link;
    }
}

*head값은 리스트의 가장 첫 노드를 가리킵니다.

 

시작노드인 p는 link를 쭉 따라가다 p->link값이 NULL이면 while 문을 빠져나갑니다.

 

즉, 모든 데이터를 출력하고 가장 마지막 노드를 만나면 종료되는거죠

 

display(p1); 를 호출해서 결과를 확인해볼까요?

 

 

 

위 처럼 p1부터 p2까지의 데이터가 잘 출력됨을 확인 할 수 있습니다.

 

다음은 지금까지의 단순 연결리스트의 전체 소스코드입니다. 

 

#include <stdio.h>
#include <malloc.h> 
typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode *link;
}ListNode;
 
void display(ListNode *head){
    ListNode *p=head;
    while(p!=NULL){
        printf("%d\n", p->data);
        p=p->link;
    }
}
 
int main(){
    
    ListNode *p1,*p2;
    p1=(ListNode *)malloc(sizeof(ListNode));
    p2=(ListNode *)malloc(sizeof(ListNode));
    
    p1->data=10;
    p1->link=p2;
    p2->data=20;
    p2->link=NULL;
    
    display(p1);
    
    return 0;
}

 

이처럼 매우 쉽게 구현할 수 있습니다.

 

하지만 이는 정말 단순한 연결리스트이고,

 

원형연결리스트, 이중연결리스트등 더욱 복잡하지만 노드간의 접근성이 더욱 높은 리스트들이 있습니다.

 

또한 지난번에 포스팅한 스택과 큐를 리스트로도 구현할 수 있습니다.

 

시간이 되면 더욱 추가하여 올리도록 하겠습니다.