[자료구조] 연결 리스트(C언어)

728x90

연결 리스트(Linkedlist)

연결 리스트란 노드가 연결되어 있는 자료구조이다. 이때 노드는 노드만의 데이터와 포인터를 갖고 있다. 여기서 데이터는 우리가 저장하고자 하는 대상이 될 수도 있다, 예를 들면 수열, 등수에 따른 시험 점수 등이 될 수 있다. 즉 관리되는 데이터를 표현하는 것이 노드의 데이터 부분이다. 노드의 포인터는 사실 연결 리스트를 연결 리스트로 만들어주는 가장 중요한 특성이다. 포인터는 다음 노드 또는 이전 노드와의 연결을 담당한다. 즉 데이터 관리를 위한 포인터인 것이다.

우리가 알고 있는 일반적인 배열과는 다르게 데이터의 추가와 삭제가 어느 지점에서도 O(1)만에 가능하다는 장점이 있다. 하지만 단점으로는 데이터로의 임의적 접근이 상당히 제한된다는 점이다. 왜냐하면 초기 데이터의 접근은 맨 앞 또는 맨 뒤에서만 할 수 있기 때문이다.

노드

노드는 구조체로 표현된다.

typedef struct Node {
	// 관리되는 데이터
	int data;
	// 데이터 관리를 위한 포인터
	struct Node* next;
} Node;

자기 참조 구조체가 사용되는데, 그 이유는 Node의 next 포인터는 Node를 가리켜야 하기 때문이다.

리스트 배열로 선언하고 놀아보기

(기능 : 리스트 출력, 맨뒤에 노드 붙이기)

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

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

int size = 0;
int user = 0;
int user_data = 0;
char c;

void initial_ask() {
    while (1) {
        printf("Type 1 to print the list\nType 2 to add a node\nType 0 to exit\n");
        scanf_s("%d", &user);
        while ((c = getchar()) != '\n');
        if (user > 2 || user < 0) {
            printf("Wrong input, please try again\n");
        }
        else {
            return;
        }
    }
}

void user_one(Node* list) {
    Node* ptmp = list;
    while (ptmp != 0) {
        printf("%d->", ptmp->data);
        ptmp = ptmp->next;
    }
    printf("NULL\n");
}

void user_two(Node** list) {
    printf("What value?");
    scanf_s("%d", &user_data);
    while ((c = getchar()) != '\n');

    Node* alist = (Node*)realloc(*list, (size + 1) * sizeof(Node));

    if (alist == NULL) {
        printf("Memory reallocation failed\n");
        return;
    }

    alist[size].data = user_data;
    alist[size].next = NULL;

    if (size > 0) {
        alist[size - 1].next = &alist[size];
    }

    *list = alist;
    size++;
}


int main() {
    printf("How many initial nodes?");
    scanf_s("%d", &size);

    Node* linkedlist = (Node*)malloc(size * sizeof(Node));
    system("cls");

    for (int i = 0; i < size - 1; i++) {
        linkedlist[i].data = i + 1;
        linkedlist[i].next = &linkedlist[i + 1];
    }

    linkedlist[size - 1].data = size;
    linkedlist[size - 1].next = NULL;

    while (1) {
        initial_ask();
        if (user == 1) {
            user_one(linkedlist);
        }
        else if (user == 2) {
            user_two(&linkedlist);
        }
        else if (user == 0) {
            free(linkedlist);
            return 0;
        }

        printf("Press Enter key to continue");
        while (1)
            if (_kbhit())
                break;
        while ((c = getchar()) != '\n');
        system("cls");
    }
}

배열로 선언했을 때의 단점은 노드의 중간 지점에 노드를 끼워 넣을 수 없다는 점이다.

여기서 배운 점은 다음과 같다.

switch case문에 지역 변수를 선언하기 위해서는 {}를 붙여주어야 한다.
찾아보니까 VS2013버전 이하에서는 오류가 생긴다고 한다. 물론 중괄호를 붙여도 선언된 그 변수는 해당 case 내에서만 사용가능하다.
printf("value?");
scanf_s("%d", &user_input);
while ((c = getchar()) != '\n');
Node* add = (Node*)malloc(sizeof(Node));
linkedlist[size - 1].next = &add;
add->data = user_input;
add->next = 0;
size++;
위의 로직은 먹히지 않는다. 위의 코드는 첫 번째로 받은 인풋일 때만 먹힌다. 왜냐하면 size를 증가시키는 동시에 배열의 크기를 키우기는커녕 존재하지도 않는 메모리에만 &add를 할당하고 있는 꼴이다. size++;를 지우면 마지막 노드의 data값만 바꿔주는 기능으로 바뀐다.

리스트 노드로 선언하고 놀아보기

사실 배열로 선언할 거였으면 노드를 사용할 필요가 있었나 싶기도 하다. 그래서 이번에는 조금 더 단일 연결 리스트에 가까운 접근으로 자료구조를 만들어 볼 것이다.

리스트의 맨 앞 노드를 가리키는 포인터를 head로 정의하자. 즉 노드가 총 3개 있는 단일 연결 리스트는 다음과 같은 형상을 띤다.

이렇게 만들면 노드의 추가와 삭제이 더 편리한 장점이 있다.

구현한 함수

ListNode* listinit()
새로운 리스트를 생성 및 반환해 줌.
ListNode* find_end(ListNode* head)
head부터 시작해서 마지막 노드를 찾아서 반환.
int len_of_list(ListNode* head)
리스트의 길이를 반환.
void add_first_node(ListNode* head, int user)
head 바로 다음에 data 부분이 user로 저장된 노드를 추가해 줌.
void add_last_node(ListNode* head, int user)
head를 통해 도달한 마지막 노드의 next에 data 부분이 user로 저장된 노드를 추가해 줌.
void insert_node(ListNode* head, int insert_location, int insert_data)
연결 리스트의 insert_location에 data 부분이 insert_data인 새로운 노드를 추가해 준다.
ListNode* find_node(ListNode* head, int find_data)
find_data를 data로 갖고 있는 노드를 찾아서 반환한다.
void rewrite_node(ListNode* head, int find_data, int rewrite_data)
find_data를 갖고 있는 노드를 찾아서 rewrite_data로 바꾸어준다.
void delete_node(ListNode* head, int del_loc)
del_loc 위치에 있는 노드를 삭제해 준다.
void delete_all_node(ListNode* head)
리스트의 사용이 더 이상 필요하지 않을 때 연결 리스트를 지워준다.
void print_all_node(ListNode* head)
연결 리스트의 내용들을 모두 볼 수 있게끔 head를 필두로 모든 노드들의 data를 차례대로 출력한다.

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

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

ListNode* listinit() {
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	head->data = 0;
	head->next = NULL;
	return head;
}

ListNode* find_end(ListNode* head) {
	ListNode* ptr = head;
	while (ptr->next != NULL) {
		ptr = ptr->next;
	}
	return ptr;
}

int len_of_list(ListNode* head) {
	int len = 0;
	ListNode* ptr = head;
	while (ptr != NULL) {
		ptr = ptr->next;
		len++;
	}
	return len;
}

void add_first_node(ListNode* head, int user) {
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = user;
	newnode->next = head->next;
	head->next = newnode;
}

void add_last_node(ListNode* head, int user) {
	ListNode* end = find_end(head);
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = user;
	newnode->next = NULL;
	end->next = newnode;
}

void insert_node(ListNode* head, int insert_location, int insert_data) {
	if (insert_location == 1) {
		add_first_node(head, insert_data);
	}
	else if (insert_location == len_of_list(head)) {
		add_last_node(head, insert_data);
	}
	else if (insert_location < 1 || insert_location > len_of_list(head)) {
		puts("Wrong range or input.");
		return;
	}
	else {
		int loc = 0;
		ListNode* ptr = head;
		while (loc++ < insert_location - 1) {
			ptr = ptr->next;
		}
		ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
		newnode->data = insert_data;
		newnode->next = ptr->next;
		ptr->next = newnode;
	}
}

ListNode* find_node(ListNode* head, int find_data) {
	ListNode* ptr = head;
	while (ptr != NULL && ptr->data != find_data) {
		ptr = ptr->next;
	}
	if (ptr == NULL) {
		puts("Data doesn't exist.");
		return head;
	}
	return ptr;
}

void rewrite_node(ListNode* head, int find_data, int rewrite_data) {
	ListNode* find = find_node(head, find_data);
	if (head == find) {
		return;
	}
	find->data = rewrite_data;
}

void delete_node(ListNode* head, int del_loc) {
	if (del_loc > len_of_list(head) || del_loc < 1) {
		puts("Out of range.");
		return;
	}
	else {
		int idx = 0;
		ListNode* ptr = head;
		while (idx++ < del_loc - 1) {
			ptr = ptr->next;
		}
		ListNode* del_ptr = ptr->next;
		ptr->next = del_ptr->next;

		free(del_ptr);
	}
}

void delete_all_node(ListNode* head) {
	ListNode* ptr = head;
	ListNode* help;
	while (ptr != NULL) {
		help = ptr->next;
		free(ptr);
		ptr = help;
	}
	free(head);
}

void print_all_node(ListNode* head) {
	ListNode* ptr = head->next;
	printf("HEAD->");
	while (ptr != NULL) {
		printf("%d->", ptr->data);
		ptr = ptr->next;
	}
	printf("NULL\n");
}

int main() {
	ListNode* h;
	h = listinit();

	add_last_node(h, 1);
	print_all_node(h);
	add_first_node(h, 2);
	print_all_node(h);
	add_first_node(h, 3);
	print_all_node(h);
	add_last_node(h, 4);
	print_all_node(h);
	insert_node(h, 10, 11);
	print_all_node(h);
	rewrite_node(h, 3, 101010);
	print_all_node(h);
	delete_node(h, 3);
	print_all_node(h);
	return 0;
}

출력 결과 >>

728x90

저작자표시 비영리 변경금지

'자료구조&알고리즘 > 자료구조' 카테고리의 다른 글

[자료구조] 덱(Deque)의 개념과 연결 리스트로 구현(C언어) (0)	2024.01.21
[자료구조] 스택을 활용해서 두 자리 수 이상의 연산이 가능한 계산기 만들기(C언어) (2)	2024.01.02
[자료구조] 큐(Queue).(C언어) (0)	2023.09.18

구르는감자

[자료구조] 연결 리스트(C언어)

연결 리스트(Linkedlist)

노드

리스트 배열로 선언하고 놀아보기

리스트 노드로 선언하고 놀아보기

구현한 함수

'자료구조&알고리즘 > 자료구조' 카테고리의 다른 글

티스토리툴바

[자료구조] 연결 리스트(C언어)

연결 리스트(Linkedlist)

노드

리스트 배열로 선언하고 놀아보기

리스트 노드로 선언하고 놀아보기

구현한 함수

'자료구조&알고리즘 > 자료구조' 카테고리의 다른 글

'자료구조&알고리즘/자료구조' Related Articles

티스토리툴바