[lecture] C언어복습.연결리스트

linked list 를 어떻게 c언어로 구현하는지

배열(array)은 구현이 간단하고 빠르지만 크기가 고정되고 중간에 삽입과 삭제가 어렵다. 연결리스트는 각각의 원소가 포인터를 사용하여 다음 번째 원소의 위치를 가리킨다. 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있지만,구현이 어렵고 오류가 나기 쉽고 포인터 연산을 많이 하기 때문에 느리다. 하지만 왜 쓰냐면, 배열의 단점을 완벽하게 커버하기 때문이다. 

연결 리스트의 구조는 노드 = 데이터 필드 + 링크 필드 로 이루어져 있다. 여기서 첫 번째 노드를 가리키는 포인터를 헤드 포인터라고 한다.

자기 참조 구조체(self-referential structure)란 특별한 구조체로서 구성 멤버 중에 같은 타입의 구조체를 가리키는 포인터가 존재하는 구조체이다. 

//데이터의 정의
typedef struct data{
	int id;
    char name[20];
    char phone[12];
}DATA;

//노드의 정의
typedef struct NODE{
	DATA data;
    struct NODE *link;
}NODE;

연결 리스트의 삽입 연산

NODE *insert_NODE(NODE *plist, NODE *pprev, DATA item);

//리스트의 처음에 삽입하는 경우
pnew->link = plist;
plist = pnew;

//리스트의 중간에 삽입하는 경우
pnew->link = pprev->link;
pprev->link = pnew;

NODE *insert_node(NODE *plist, NODE *pprev, DATA item){

	NODE *pnew = NULL;
    
    if(!(pnew = (NODE*)malloc(sizeof(NODE)))){
    	printf("메모리 동적 할당 오류\n");
        exit(1);
    }
    pnew->data = data;
    if(pprev == NULL){	//연결리스트의 처음에 삽입
    	pnew->link = plist;
        plist = pnew;
    }
    else{				//연결리스트의 중간에 삽입
    	pnew->link = pprev->link;
        pprev->link = pnew;
    }
    return plist;
}

연결리스트의 삽입 연산의 종류로는 1. 처음에 삽입 2. 중간에 삽입 3. 마지막에 삽입 가 있다. 2번과 3번같은 경우에는 같다고 볼 수 있다. 

연결 리스트의 삭제 연산

NODE *delete_node(NODE *plist, NODE *pprev, NODE *pcurr);

//리스트의 처음을 삭제하는 경우
plist = pcurr->link;
free(pcurr);

//리스트의 중간에 삭제하는 경우
pprev->list = pcurr->link;	//pprev->link = pprev->link->link;
free(pcurr);

NODE *delete_node(NODE *plist, NODE *pprev, NODE *pcurr){
	if(pprev == NULL)
    	plist = pcurr->link;
    else
    	pprev->link = pcurr->link;
    free(pcurr);
    return plist;
}

연결 리스트의 순회 연산

void print_list(NODE *plist){
	NODE *p;
    
    p=plist;
    printf("(");
    
    while(p){
    	printf("%d",p->data);
        p = p->link;
    }
    printf(")\n");
}

노드의 개수 세기

int get_length(NODE *plist){
	NODE *p;
    int length = 0;
    
    p=plist;
    
    while(p){
    	length++;
        p = p->link;
    }
    printf("리스트의 길이는 %d\n", length);
    return length;
}

합계 구하기

int get_sum(NODE *plist){
	NODE *p;
    int sum = 0;
    
    p=plist;
    
    while(p){
    	sum += p->data;
        p = p->link;
    }
    printf("리스트의 합계는 %d\n", sum);
    return sum;
}

#include <stdio.h>
#include <stdlib.h>

/*NODE 라는 구조체 안에 int형 데이터를 저장할 변수 하나와,
 * 다음 노드의 주소를 저장할 자기 참조 구조체 포인터 선언 */
typedef struct NODE{
    int data;
    struct NODE* next;  //노드 구조체의 주소 저장 > struct NODE 형태의 주소값을 저장하는 포인터 변수
}node;

int main(){
    node* head = (node*)malloc(sizeof(node));   //헤드노드 생성, node구조체 크기만큼 동적할당
    head->next = NULL;  //헤드노드의 next값은 null > 출발점
    //node1 새로운 노드 새로 할당
    node* node1 = (node*)malloc(sizeof(node));
    node1->next = head->next;    //NULL과 헤드노드 사이에 node1 이라는 새 노드 추가
    node1->data = 10;   //node1의 데이터에는 10을 저장
    head->next = node1; //헤드노드의 다음노드는 node1의 주소를 저장
    /*포인터에서 각각의 원소들(변수)에 직접적으로 접근하여 값을 수정할 때에는 -> 연산자 사용*/
    //node2 새로운 노드 새로 할당
    node* node2 = (node*)malloc(sizeof(node));
    node2->next = node1->next;  //node2의 다음노드 주소는 node1이 가르키던 주소
    node2->data = 20;
    node1->next = node2;    //node1의 다음주소는 node2로 저장
    //노드3개를 생성하고 데이터를 넣음
    //순회용 노드 생성
    node* curr = head->next;    //curr은 node1의 주소를 대입받음 > curr은 node1 > node1 메모리주소에 직접 접근
    while(curr != NULL){    //curr에 저장된 값이 NULL이 아닐 때 반복
        printf("%d\n", curr->data); //node1->data와 같음 >curr은 현재 node1의 주소를 가지고 있고 node1의 데이터는 10이므로 10이 출력
        curr = curr->next;  //node1->next값이 curr에 대입, node->next에는 node2의 주소가 들어있으므로 curr은 이제 node2
    }
    //동적할당 해제
    free(head);
    free(node1);
    free(node2);
    return 0;
}