C - 자료구조 연결리스트

연결리스트란 ?
원하는만큼 노드를 동적으로 추가/생성하여 사용하는 자료구조이다.
배열과 같이 특정 인덱스에 바로 접근하는것은 불가능하다. 왜냐하면 배열처럼 메모리에 정렬되어 있지 않고 각 노드들이 사방에 흩어져있는 형태이기 때문이다.
그렇기에 1~7의 노드가 존재한다고 가정하자. 내가 4번 노드에 접근을 하려면 1부터 4까지의 탐색을 통해 접근하여야 한다.

단일 연결 리스트의 경우 이전 노드의 주소를 저장하지 않기에 데이터의 저장은 HEAD노드 -> 마지막노드 한방향으로 값을 저장한다

먼저 NODE 구조체는 값을 저장하는 data, 다음 노드를 가리키는 next포인터변수가 존재한다.

처음 생성하는 Head 노드는 값을 저장하지 않고 다음 노드만을 가리키는 역할을 하며 당연히 처음 생성하면 Head노드의 주소값은 NULL을 가리키며 초기화 해줘야한다.

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

typedef struct NODE{
    int data;
    struct NODE* next;
}node;


int main(void){

    node* head = (node*)malloc(sizeof(node));
    //head 노드 생성, 동적할당
    head->next = NULL; 
    //head 노드가 가리키는 다음 노드는 NULL로 초기화 해줌
    node* node1 = (node*)malloc(sizeof(node));
    //node1생성
    node1->next = head->next;
    //node1의 다음 주소는 head노드가 가리키던 주소(NULL) 저장
    node1->data = 10;
    //node1의 데이터에 10 저장
    head->next = node1;
    //head노드가 가리키는 다음노드느 node1의 주소를 저장

    node* node2 = (node*)malloc(sizeof(node));
    node2->next = node1->next;
    //node2가 기리키는 다음 노드는 node1이 가리키던 주소(NULL) 저장
    node2->data = 20;
    //node2의 데이터에 20저장
    node1->next = node2;
    //node1의 next는 node2의 주소값을 저장

    //순회용 노드 생성
    node* curr = head->next;
    while(curr!=NULL){
        printf("%d\n", curr->data);
        curr = curr->next;
    }
    /*
    while문은 curr의 값이 NULL이 아니면 계속하여 반복한다
    처음 curr엔 head->next의 값 즉 Node1의 주소를 담고 있음
    NULL이 아니므로 동작
    curr->data 즉 node1의 데이터 10을 출력
    그 후 curr에는 curr->next 즉 Node2의 주소값을 저장
    다음 반복문에서 또한 NULL이 아니기에 반복함
    curr->data는 Node2의 데이터이기에 20출력
    그 후 curr에는 curr->next 즉 NULL 값을 저장
    반복문 종료
    */
    
    //node1 삭제
    head->next = node1->next;
    //head노드의 next값에 node1의 next가 가리키는 주소값을 대입
    free(node1);
    //node1은 더이상 연결되어 있지 않고 필요가 없기에 할당받은 메모리 해제

    node* cur = head->next;
    while(cur!=NULL){
        printf("%d\n", cur->data);
        cur = cur->next;
    }

    free(head);
    free(node2);
    //할당받은 메모리 해제
    
    return 0;

}

출력 결과

10
20
20

위의 예제와 같이 단일 연결리스트의 노드 생성/삭제를 할 수 있다.

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

typedef struct node{
    int data;
    struct node* next;
}node;

typedef struct nd{
    node *head;
    node *tail;
}nd;

node* Creat(int data){
    node *newnode = (node*)malloc(sizeof(node));
    newnode->data = data;
    newnode->next = NULL;
    return newnode;
    /*
    노드 생성 함수 단, 연결되어 있지 않은 상태
    생성된 노드는 NULL을 가리키고 있으며 data를 가지고 있음
    */
}

void first_add(nd* newnd, int data){
    /*
    헤드 오른쪽(첫번째)에 노드를 연결하는 함수
    매개변수로 head와 tail을 가지고 있는 nd 구조체와 data를 받는다.
    */
    node *newnode = Creat(data);
    //새로운 노드 생성
    if(newnd->head==NULL){
        //만약nd->head가 NULL을 가리키고 있다 == 노드가 하나도 존재하지 않을 경우
        newnd->head = newnode;
        newnd->tail = newnode;
        //처음 연결한 리스트이기에 head와 tail은 NULL이 아닌 새로 추가된 newnode를 가리킨다
    }
    else{
        //NULL이 아닌 어떤 다른 주소를 가리키고 있을 경우 즉, 처음 연결하는 노드가 아닐 경우
        newnode->next = newnd->head;
        //newnode의 next는 nd구조체의 head가 가리키는 값
        newnd->head = newnode;
        //nd구조체의 head값은 newnode의 주소를 가리킨다
        //즉 ㅁ(1) ㅁ(2)이 있다면 head는 (2)의 주소를 가리키게 되는 것으로 ->방향 리스트의 왼쪽에 노드가 추가된다는 것
    }

}

void last_add(nd* newnd, int data){
    /*
    처음 연결된 노드 끝에서 삽입 하는 함수 (->방향 기준 오른쪽에)
    */
    node *newnode = Creat(data);
    //노드를 새로 만들고
    newnd->tail->next = newnode;
    //nd구조체의 tail->next는 새로 만든 newnode의 주소값을 저장
    newnd->tail = newnode;
    //tail은 newnode를 가리킴

}

void node_print(nd *newnd){
    node *p = newnd->head;
    while(p!=NULL) {
        printf("%d ->", p->data);
        p = p->next;
    }
}

//삭제 기능


int main(void){

    nd* nda = (nd*)malloc(sizeof(nd));
    
    nda->head = NULL;
    nda->tail = NULL;

    first_add(nda, 5);
    last_add(nda, 1);
    first_add(nda, 32);
    last_add(nda, 6);
    last_add(nda, 7);
    node_print(nda);

    return 0;

}

단순연결리스트 기본 연산 (문자를 매개변수로)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _CRT_SECURE_NO_WARINGS

typedef struct ListNode {
	char data[4];
	struct Listnode* link;
}listnode;

typedef  struct {
	listnode* head;
}linkedlist_h;

//공백 연결 리스트를 생성하는 함수
linkedlist_h* createLinkedList_h(void) {
	linkedlist_h* L = (linkedlist_h*)malloc(sizeof(linkedlist_h));
	L->head = NULL;
	return L;
}

//연결리스트 전체 메모리 해제하는 함수
void freeLinkedList_h(linkedlist_h* L) {
	listnode* p;
	while (L->head != NULL) {
		p = L->head; //p에 헤드의 주소를 저장
		L->head = L->head->link; //헤드는 헤드의 링크가 가리키는 다음 노드 주소를 저장
		free(p); //p가 가지고 있는 주소의 노드 메모리 해제
		p = NULL; //p는 NULL을 가리킴
	}

}

void printList(linkedlist_h* L) {
	listnode* p;
	printf("Linked List = (");
	p = L->head; //p에 헤드의 주소를 저장
	while (p != NULL) { //p가 NULL을 가리킬때까지 반복
		printf("%s", p->data); //p가 가지고 있는 데이터를 출력한 후
		p = p->link; //다음 노드의 주소값을 저장
		if (p != NULL) printf(", "); //만약 저장한 다음 노드의 주소가 NULL을 가리키지 않을 경우 ,를 출력
	}
	printf(")\n");
}


void insert_FirstNode(linkedlist_h* L, char* x) {
	listnode* newnode; //새로운 노드 메모리 할당
	newnode = (listnode*)malloc(sizeof(listnode));
	strcpy(newnode->data, x); //newnode의 data에 x저장
	newnode->link = L->head; //newnode의 link는 L->head가 가리키고 있는 주소를 저장
	L->head = newnode; //L->head는 newnode의 주소를 가리킴
}

void insert_MiddleNode(linkedlist_h* L, listnode* pre, char* x) {
	listnode* newnode;
	newnode = (listnode*)malloc(sizeof(listnode));
	strcpy(newnode->data, x);
	if (L->head == NULL) {
		newnode->link = NULL;
		L->head = newnode;
	}
	else if (pre == NULL) { //삽입 위치를 지정하는 pre가 NULL인 경우
		newnode->link = L->head; //newnode를 첫번째 노드로 삽입
		L->head = newnode;
	}
	else {
		newnode->link = pre->link; //포인터 pre의 노드 뒤에 newnode 연결
		pre->link = newnode;
	}
}
void insert_LastNode(linkedlist_h* L, char* x) {
	listnode* newnode;
	listnode* temp;
	newnode = (listnode*)malloc(sizeof(listnode));
	strcpy(newnode->data, x); //문자 x를 newnode->data로 복사
	newnode->link = NULL; //newnode의 link는 NULL을 가리킴, 마지막 노드로 삽입하기 때문
	if (L->head == NULL) { //현재 리스트가 공백인 경우
		L->head = newnode; //헤드노드는 newnode를 가리킴
		return;
	}

	temp = L->head; //temp는 head노드를 가리킴
	while (temp->link != NULL) temp = temp->link; //temp의 링크가 NULL 즉 노드의 끝을 가리킬때까지 반복
	//temp = temp가 가리키고 있는 주소
	temp->link = newnode; //현재 마지막 노드인 temp의 링크는 newnode를 가리키게 함		
}

void delete_Node(linkedlist_h* L, listnode* p) {
	listnode* pre; //삭제할 노드의 이전 노드
	if (L->head == NULL) return; //공백 리스트일 경우 종료
	if (L->head->link == NULL) { //리스트의 노드가 하나인 경우 
		free(L->head); //첫번째 노드를 메모리에서 해제하고
		L->head = NULL; //리스트 시작 포인터를 NULL로 설정
		return;
	}
	else if (p == NULL) return; //삭제할 노드가 없다면 종료
	else{
		pre = L->head;
	while (pre->link != p) { //삭제할 노드 
		pre = pre->link; //이전 노드의 link를 이용해 계속 탐색
	}
	pre->link = p->link; //이전노드의 링크는 삭제할 노드의 링크로 연결 
	free(p); //메모리 해제
	}
}

listnode* search_Node(linkedlist_h* L, char* x) {
	listnode* temp;
	temp = L->head;
	while (temp != NULL) {
		if (strcmp(temp->data, x) == 0) return temp;
		else temp = temp->link;
	}
	return temp;
}

void reverse(linkedlist_h* L) { //리스트의 노드 순서를 역순으로 바꾸는 연산
	listnode* p;
	listnode* q;
	listnode* r;

	p = L->head;
	q = NULL;
	r = NULL;

	while (p != NULL) {
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}
	L->head = q;
}
int main(void) {

	linkedlist_h* L;
	listnode* p;
	L = createLinkedList_h();
	printf("(1)리스트에 월 수 일 노드 삽입하기\n");
	insert_LastNode(L, "월");
	insert_LastNode(L, "수");
	insert_LastNode(L, "일");
	printList(L);

	printf("\n(2)리스트에 수 노드 탐색하기\n");
	p = search_Node(L, "수");
	if (p == NULL) printf("찾는 데이터가 없습니다\n");
	else printf("%s를 찾았습니다", p->data);

	printf("\n(3)리스트의 수 뒤에 금 노드 삽입하기\n");
	insert_MiddleNode(L, p, "금");
	printList(L);

	printf("\n(4)리스트에서 일 노드 삭제하기\n");
	p = search_Node(L, "일");
	delete_Node(L, p);
	printList(L);

	printf("\n(5)리스트 순서를 역순으로 바꾸기\n");
	reverse(L);
	printList(L);

	freeLinkedList_h(L);
	getchar();



	return 0;
}

출력 결과

(1)리스트에 월 수 일 노드 삽입하기
Linked List = (월, 수, 일)

(2)리스트에 수 노드 탐색하기
수를 찾았습니다
(3)리스트의 수 뒤에 금 노드 삽입하기
Linked List = (월, 수, 금, 일)

(4)리스트에서 일 노드 삭제하기
Linked List = (월, 수, 금)

(5)리스트 순서를 역순으로 바꾸기
Linked List = (금, 수, 월)