[C언어] 연결리스트(Linked List)

연결리스트(Linked List)란?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다.

 

장점

- 원하는 만큼 노드를 동적으로 추가/삭제할 수 있다.

 

단점

- 배열처럼 메모리공간에 정렬되어있지 않고 사방에 흩어져있어서 배열의 인덱스처럼 특정 노드에 바로 접근할 수 없다.

 

 

원리

 

연결리스트에서 각 칸은 노드(Node)라고 부르고, 노드는 구조체로 구현한다.

struct node
{
    int data;               //데이터가 저장되는 공간, 저장할 데이터에 따라 자료형 달라짐
    struct node *next;     //다음 노드의 주소를 저장할 포인터
};
typedef struct node Node;

 

이렇게 선언한 구조체를 통해 연결리스트를 만들 수 있다.

#include <stdio.h>
struct node
{
    int data;
    struct node *next;
};
typedef struct node Node;

int main()
{
    Node a,b,c,d;
    
    a.data = 1;
    a.next = &b;
    
    b.data = 2;
    b.next = &c;
    
    c.data = 3;
    c.next = &d;
    
    d.data = 4;
    d.next = NULL;
    
    return 0;
}

 

 

 

위 코드는 정적 으로 구현된 연결리스트이다.

data는 저장하고자하는 데이터를 저장할 수 있는 멤버이고,

next는 다음 노드의 주소 값을 저장함으로써 노드의 앞, 뒤를 연결해줄 수 있다.

 

 

노드를 원하는만큼 생성하고 삭제할 수 있어야 하기 때문에 연결리스트는 동적 으로 만들어져야한다.

 

Node *head = NULL;  //첫 번째 노드의 주소 저장
Node *tail = NULL;  //마지막 노드의 주소 저장

 

 

head ?

 

head가 없다면 연결리스트를 읽을 수 없다.

왜냐하면 각 노드가 동적으로 구현되어 있어 각 노드는 주소로만 접근이 가능한 상태라,

각 노드는 다음 노드의 주소만을 기억하기에 이전 노드의 주소를 알 수 있는 방법이 없다. 

따라서 head의 존재는 연결리스트를 첫 번째 노드부터 읽기 위해 반드시 필요하다

 

tail?

 

tail은 연결리스트의 새로 생성된 노드를 연결시켜주기 위해 필요하다.

일반적인 연결리스트 노드 생성 방식은 새로 생성된 노드를 마지막 노드 뒤에 연결하는 방식이다.

이때, 마지막 노드의 주소값을 tail에 저장하여 방금 새로 생성된 노드와 연결해줄 수 있다.

 

 

구현(생성, 탐색, 삭제)

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

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

Node *head = NULL;  //첫 번째 노드의 주소 저장
Node *tail = NULL;  //마지막 노드의 주소 저장

int main()
{
    while(1)
    {
        int input;                      
        printf("연결할 데이터를 입력하세요. ");
        scanf("%d",&input);

        if(input <= 0) break;       //입력 데이터가 0 또는 음수이면 종료

        Node *newnode = (Node*)malloc(sizeof(Node));    //노드 동적 생성

        newnode->data = input;  //노드의 데이터 삽입
        newnode->next =NULL;    //새로 생성된 노드는 항상 마지막 노드이므로 next 없음

        if(head==NULL) head = newnode;  //head가 null이면 현재 연결리스트에 노드가 없다는 뜻-> 새로 생성한 노드를 head로 설정
        else tail->next = newnode;      //마지막에 생성했던 노드의 다음 노드를 방금 생성한 노드와 연결

        tail = newnode;     // 방금 생성한 노드가 마지막 노드이므로 tail 변경
    }

    printf("연결리스트 현재 상태 : ");
    Node *cur = head;       //첫번째 노드부터 탐색
    while(cur != NULL)      //더이상 탐색할 노드가 없을 때까지 반복
    {
        printf("%d", cur->data);
        cur = cur->next;    //연결된 다음 노드로 이동
    }
    puts("");

    while (1)
    {
        int k;
        printf("삭제할 데이터를 입력하세요 : ");
        scanf("%d",&k);

        if(k <= 0) break;   

        int search = 0;         //검색 여부 검사(1이면 있다, 0이면 없다)
        Node *cur_prev = NULL;  //cur을 뒤 따라 다니는 포인터
        cur = head;             //첫 번째 노드부터 탐색
        while(cur !=NULL)       //더이상 탐색할 노드가 없을 때까지 반복
        {
            if(cur->data ==k)   //입력한 데이터를 연결리스트에서 찾으면
            {
                search = 1;     
                break;
            }   
            cur_prev = cur;     //cur의 이전 노드
            cur = cur->next;    //연결된 다음 노드로 이동
        }

        if(search ==1)
        {
            printf("%d를 삭제합니다. \n", k);
            
            if(cur ==head) head = cur->next;    //삭제할 노드가 head이면 head를 연결된 다음 노드로 이동
            else cur_prev->next = cur->next;    //삭제할 노드의 이전 노드와 다음 노드를 연결

            free(cur);  //삭제
        }
        else
        {
            printf("%d를 찾을 수 없습니다.\n",k);
        }
    }

    printf("(삭제 후) 연결리스트 현재 상태:");
    cur = head;
    while(cur != NULL)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    puts(" ");
}

 

puts(" ")
-> /문자열을 출력하는 함수, 오직 문자열만 출력! 후 줄바꿈
printf("\n")보다 더 빠르다.

 

 

 

참고

https://jeongorithm.tistory.com/11