[Data Structure] 단순 연결 리스트
2021. 12. 9. 22:00ㆍMajor`/자료구조
단순 연결 리스트 (Singly Linked List)
- 단방향 연결
- 마지막 노드의 링크값 = NULL
- 헤드 포인터 : 연결 리스트의 맨 처음 노드를 가리키는 포인터
단순 연결 리스트 ADT
void insert_node(s_listnode **head, s_listnode *pre, s_listnode *new_node)
- 삽입연산
void remove_node(s_listnode **head, s_listnode *pre, s_listnode *removed)
- 삭제연산
void print_list(s_listnode *head)
- 리스트 순서대로 출력
s_listnode *search(s_listnode *head, int value)
- 리스트안에 존재하는 value 찾아내기
s_listnode *concat(s_listnode *head1, s_listnode *phead2)
- 리스트 2개 연결하는 합병연산
노드 정의/생성/삭제
- 정의 : 자기 참조 구조체 이용
- 생성 : malloc()을 호출하여 동적 메모리로 생성
- 삭제 : free()를 호출하여 동적 메모리 해제
● 노드 정의
typedef int element;
typedef struct {
element data;
struct s_listnode* link; // 다음 노드를 가리키는 링크 포인터
// ex) p->link : p의 다음 노드, p의 다음노드에 접근하는 방법
}s_listnode;
● 노드 생성
s_listnode* p1 = (s_listnode*)malloc(sizeof(s_listnode));
p1->data = 10;
p1->link = NULL;
● 노드 연결
s_listnode* p2 = (s_listnode*)malloc(sizeof(s_listnode));
p2->data = 20;
p2->link = NULL;
p1->link = p2;- p1->link = p2;를 통해서 p1~>p2 연결
단순 연결 리스트 ADT 구현
1. 삽입연산
- void insert_node(s_listnode **phead, s_listnode *pre, s_listnode *new_node)
- 헤드포인터가 함수 안에서 변경되기 때문에 헤드포인터의 포인터가 필요
① head가 NULL인 경우 (공백리스트)
- new_node가 첫 번째 노드로 설정
- 마지막 노드이기 때문에 new_node의 link는 NULL를 가리키게 한다
- head의 주소에 new_node를 넣어준다
② pre가 NULL인 경우 (리스트 맨 앞에 new_node 삽입)
- 이전 노드가 NULL → new_node가 리스트의 맨 앞 노드로 설정
- new_node의 link는 다음 노드의 주소를 가리키게 한다 → 다음 노드의 주소를 가리키는 것 = head
- head의 주소에 new_node를 넣어준다
③ head, p가 NULL이 아닐 경우 (리스트 중간에 new_node 삽입)
- new_node의 link는 다음 노드의 주소를 가리키게 한다 → 다음 노드의 주소를 가리키는 것 = pre->link
- pre가 new_node를 가리키게 한다
void insert_node(s_listnode** head, s_listnode* pre, s_listnode* new_node) {
if (*head == NULL) { // 공백리스트 인 경우
new_node->link = NULL; // 마지막 노드이기 때문에 new_node의 link는 NULL를 가리키게 한다
*head = new_node; // head의 주소에 new_node를 넣어준다
}
else if (pre == NULL) { // pre가 NULL이면 new_node는 첫번째 노드로 삽입
new_node->link = *head;
// new_node의 link는 다음 노드의 주소를 가리키게 한다
// 다음 노드의 주소를 가리키는 것 = head
*head = new_node; // head의 주소에 new_node를 넣어준다
}
else { // new_node는 pre 다음에 삽입
new_node->link = pre->link; // new_node의 link는 다음 노드의 주소를 가리키게 한다
pre->link = new_node; // pre가 new_node를 가리키게 한다
}
}
void insert_last(s_listnode** head, s_listnode* new_node) {
s_listnode* p = *head;
while (p->link != NULL) {
p = p->link; // 마지막 노드까지 도달
}
p->link = new_node; // p가 new_node를 가리키게 한다
}
void insert_first(s_listnode** head, s_listnode* new_node) {
new_node->link = *head;
*head = new_node;
}
2. 삭제연산
- void remove_node(s_listnode **head, s_listnode *pre, s_listnode *removed)
- free(removed)를 통해서 removed 동적 할당 해제 → removed 삭제
① pre가 NULL인 경우
- 맨 앞 노드 삭제
- → 헤드포인터 변경
- head의 주소에 head의 주소의 link를 넣어준다
② pre가 NULL이 아닌 경우
- 중간 노드 삭제
void remove_node(s_listnode** head, s_listnode* pre, s_listnode* removed) {
if (pre == NULL) {
*head = (*head)->link;
}
else {
pre->link = removed->link;
}
free(removed);
}
3. 탐색연산
- s_listnode *search(s_listnode *head, int value)
- 반환값 = value를 가지고 있는 노드의 주소
s_listnode* search(s_listnode* head, element value) {
// list에 head가 있나 탐색하는 함수
// 반환값 = value를 가지고 있는 노드의 주소
s_listnode* p = head;
while (p != NULL) { // p가 NULL이 될 때 까지
if (p->data == value) return p;
p = p->link; // data와 value가 다르면 계속 다음 노드를 가리키기
}
return p; // 탐색 실패하면 NULL 리턴
}
4. 합병연산
- head1과 head2를 연결
- head1이 NULL → return head2
- head2이 NULL → return head1
s_listnode* concat(s_listnode* head1, s_listnode* head2) {
s_listnode* p;
if (head1 == NULL) return head2;
else if (head2 == NULL) return head1;
else {
p = head1;
while (p->link != NULL)
p = p->link; // head1의 마지막 노드까지 도달하기
p->link = head2; // 마지막 노드가 head2를 가리키게 한다 == head1과 head2 연결
return head1;
}
}
5. Full Code (LinkedList)
#include <stdio.h>
#include <stdlib.h>
// 단순 연결 리스트
typedef int element;
typedef struct {
element data;
struct s_listnode* link; // 다음 노드를 가리키는 링크 포인터
// ex) p->link : p의 다음 노드, p의 다음노드에 접근하는 방법
}s_listnode;
void insert_node(s_listnode** head, s_listnode* pre, s_listnode* new_node) {
if (*head == NULL) { // 공백리스트 인 경우
new_node->link = NULL; // 마지막 노드이기 때문에 new_node의 link는 NULL를 가리키게 한다
*head = new_node; // head의 주소에 new_node를 넣어준다
}
else if (pre == NULL) { // pre가 NULL이면 new_node는 첫번째 노드로 삽입
new_node->link = *head;
// new_node의 link는 다음 노드의 주소를 가리키게 한다
// 다음 노드의 주소를 가리키는 것 = head
*head = new_node; // head의 주소에 new_node를 넣어준다
}
else { // new_node는 pre 다음에 삽입
new_node->link = pre->link; // new_node의 link는 다음 노드의 주소를 가리키게 한다
pre->link = new_node; // pre가 new_node를 가리키게 한다
}
}
void insert_last(s_listnode** head, s_listnode* new_node) {
s_listnode* p = *head;
while (p->link != NULL) {
p = p->link; // 마지막 노드까지 도달
}
p->link = new_node; // p가 new_node를 가리키게 한다
}
void insert_first(s_listnode** head, s_listnode* new_node) {
new_node->link = *head;
*head = new_node;
}
void remove_node(s_listnode** head, s_listnode* pre, s_listnode* removed) {
if (pre == NULL) {
*head = (*head)->link; // head의 주소에 head의 주소의 link를 넣어준다
}
else {
pre->link = removed->link;
}
free(removed);
}
void print_list(s_listnode* head) {
s_listnode* p = head;
if (p == NULL)
printf("Error : List is empty\n\n");
else {
while (p != NULL) { // p가 NULL이 되는 순간 (마지막 노드에 도착) 탈출
printf("%d -> ", p->data);
p = p->link; // 다음 p의 주소 가리키기
}
printf("NULL\n\n");
}
}
s_listnode* search(s_listnode* head, element value) {
// list에 head가 있나 탐색하는 함수
// 반환값 = value를 가지고 있는 노드의 주소
s_listnode* p = head;
while (p != NULL) { // p가 NULL이 될 때 까지
if (p->data == value) return p;
p = p->link; // data와 value가 다르면 계속 다음 노드를 가리키기
}
return p; // 탐색 실패하면 NULL 리턴
}
s_listnode* concat(s_listnode* head1, s_listnode* head2) {
s_listnode* p;
if (head1 == NULL) return head2;
else if (head2 == NULL) return head1;
else {
p = head1;
while (p->link != NULL)
p = p->link; // head1의 마지막 노드까지 도달하기
p->link = head2; // 마지막 노드가 head2를 가리키게 한다 == head1과 head2 연결
return head1;
}
}
int main(void) {
s_listnode* head1 = NULL;
s_listnode* p1 = (s_listnode*)malloc(sizeof(s_listnode));
p1->data = 30; p1->link = NULL;
s_listnode* p2 = (s_listnode*)malloc(sizeof(s_listnode));
p2->data = 60; p2->link = NULL;
s_listnode* p3 = (s_listnode*)malloc(sizeof(s_listnode));
p3->data = 70; p3->link = NULL;
s_listnode* head2 = NULL;
s_listnode* p4 = (s_listnode*)malloc(sizeof(s_listnode));
p4->data = 300; p4->link = NULL;
s_listnode* p5 = (s_listnode*)malloc(sizeof(s_listnode));
p5->data = 600; p5->link = NULL;
s_listnode* p6 = (s_listnode*)malloc(sizeof(s_listnode));
p6->data = 700; p6->link = NULL;
s_listnode* p7 = (s_listnode*)malloc(sizeof(s_listnode));
p7->data = 1000; p7->link = NULL;
s_listnode* p8 = (s_listnode*)malloc(sizeof(s_listnode));
p8->data = 5000; p8->link = NULL;
printf("---head1---\n");
printf(">>> insert p1(30) : pre = NULL\n");
insert_node(&head1, NULL, p1);
print_list(head1);
printf(">>> insert p2(60) : pre = NULL\n");
insert_node(&head1, NULL, p2);
print_list(head1);
printf(">>> insert p3(70) : pre = p1\n");
insert_node(&head1, p1, p3);
print_list(head1);
if (search(head1, 50) != NULL)
printf("리스트에 50이 있습니다!!\n\n");
else
printf("리스트에 50이 없습니다.\n\n");
if (search(head1, 30) != NULL)
printf("리스트에 30이 있습니다!!\n\n");
else
printf("리스트에 30이 없습니다.\n\n");
printf("---head2---\n");
printf(">>> insert p4(300) : pre = NULL\n");
insert_node(&head2, NULL, p4);
print_list(head2);
printf(">>> insert p5(600) : pre = p4\n");
insert_node(&head2, p4, p5);
print_list(head2);
printf(">>> insert p6(700) : pre = p5\n");
insert_node(&head1, p5, p6);
print_list(head2);
printf(">>> insert_last p7(1000)\n");
insert_last(&head2, p7);
print_list(head2);
printf(">>> insert_first p8(5000)\n");
insert_first(&head2, p8);
print_list(head2);
printf(">>> remove_node p6(700) : pre = p5\n");
remove_node(&head2, p5, p6);
print_list(head2);
printf(">>> concat(head1, head2)\n");
concat(head1, head2);
print_list(head1);
return 0;
}
