10. 단일 연결리스트

연결리스트란?

노드를 순서대로 연결하여 표현한 자료구조이다.

연결리스트에서 데이터를 탐색, 삽입, 삭제를 수행하는 경우 특정 위치에 대한 포인터만 수정하면 되므로 배열과 달리 크기가 동적으로 변경될 수 있다는 장점이 존재한다.

연결리스트의 종류는 아래와 같다.

 1. 단일 연결리스트 : 단방향으로만 데이터 접근이 가능한 연결리스트

 2. 단일 원형 연결리스트 : 단방향으로만 데이터 접근이 가능하며 마지막 노드에서 처음 노드로 이동이 가능하다.

 3. 이중 연결리스트 : 양방향으로 데이터 접근이 가능한 연결리스트

 4. 이중 원형 연결리스트 : 양방향으로 데이터 접근이 가능하며 마지막 노드에서 처음 노드로 이동이 가능하다.

---

노드란?

데이터를 저장하는 단위로, C언어에서는 구조체로 정의한다.

연결리스트의 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다.

---

단일 연결리스트 구현

이론으로 접근하는 것보다 직접 구현해 보도록 하자

삽입, 삭제 함수등으로 인해 코드가 길다 보니 천천히 읽어보고 포인터들의 변화를 중점적으로 살펴보도록 하자

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

// 노드에 대한 구조체 정의
typedef struct Node *NodePointer;
typedef struct Node{
    int data;
    NodePointer next;
}Node;

// 새로운 노드를 연결리스트 가장 앞에 삽입
NodePointer Insert_Front(NodePointer head, int data){
    NodePointer New_Node = (NodePointer)malloc(sizeof(Node));
    New_Node -> data = data;
    New_Node -> next = head;
    return New_Node;
}
//새로운 노드를 연결리스트 가장 뒤에 삽입
NodePointer Insert_Back(NodePointer head, int data){
    NodePointer temp = head;
    NodePointer New_Node = (NodePointer)malloc(sizeof(Node));
    New_Node -> data = data;
    New_Node -> next = NULL;
    
    if(head == NULL) // 연결리스트에 노드가 없다면(가장 첫 노드에 삽입)
        head = New_Node;
    else{ // 연결리스트에 노드가 있다면(가장 끝 노드에 삽입)
        while(temp->next) temp = temp -> next;
        temp -> next = New_Node;
    }
    return head;
}
// 연결리스트의 가장 앞 노드를 삭제
NodePointer Delete_Front(NodePointer head){
    NodePointer temp = head;
    if(!head) return head; //삭제할 노드가 없다면 NULL 반환
    
    head = head -> next;
    free(temp);
    
    return head;
}
// 연결리스트의 가장 뒷 노드를 삭제
NodePointer Delete_Back(NodePointer head){
    NodePointer temp = head;
    if(!head) return head; //삭제할 노드가 없다면 NULL 반환
    
    if(!head->next) { // 삭제할 노드가 첫 노드일 경우
        free(head);
        head = NULL;
    }
    else{ // 삭제할 노드가 마지막 노드일 경우
        while(temp->next->next) temp = temp->next;
        free(temp->next);
        temp->next = NULL;
    }
    return head;
}
// 연결리스트를 처음부터 끝까지 출력
void Print_Node(NodePointer head){
    NodePointer temp = head;
    while(temp){
        printf("%d ", temp -> data);
        temp = temp -> next;
    }
    printf("\n");
}

int main()
{
    Node* head = NULL;
    
    head = Insert_Front(head, 3);
    head = Insert_Front(head, 2);
    head = Insert_Front(head, 1);
    Print_Node(head); // 1 2 3 
    head = Insert_Back(head, 4);
    head = Insert_Back(head, 5);
    Print_Node(head); // 1 2 3 4 5
    head = Delete_Front(head);
    Print_Node(head); // 2 3 4 5
    head = Delete_Back(head);
    Print_Node(head); // 3 4 5

    return 0;
}

연결리스트뿐만 아니라 포인터를 사용하는 C언어 코드는 코드를 작성하는 사람의 성향, 학습한 책 등으로 인해 정말 다양한 코드 형태를 나타낸다. 그러므로 하나의 코드만 보지 말고 다양한 코드를 보고 이해하면서 내가 사용하기 가장 편한 형태를 만들어보도록 하자.

 

포인터를 사용하는 모든 프로그램 공부를 손으로 할 경우 무작정 코드를 작성해 보는 것이 아니라 포인터를 화살표로 하여 그림으로 그려가면서 공부를 하게 되면 조금 수월하게 할 수 있을 것이다.