C Linked List(연결리스트 구현)

연결리스트

- 추상적 자료형인 리스트를 구현한 자료구조로 노드(데이터 덩어리)를 저장할 때 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 자료구조이다.

  ※ 그렇기때문에 구조체 멤머변수 중 자신과 동일한 구조체의 주소를 저장할 수 있는 변수를 만들어 참조해야한다. (이 때, 주소를 저장하는 멤버 변수를 자기참조 구조체라고 함.)

- 장점 : 배열과 다르게 데이터를 동적으로 추가, 삭제가 가능하다.

- 단점 : 배열처럼 정렬되어있지 않고, 흩어져있기 때문에 배열의 인덱스로 접근하는것 처럼 특정 노드에 빠른 접근은 불가능하다.

  ※ 일일이 탐색하는 과정을 거쳐서 데이터를 찾아야 한다.

 

Linked List를 위한 구조체

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

 

위의 구조체를 바탕으로 우리가 구현할 연결리스트의 그림을 그려보자면 다음과 같이 표현할 수 있다.

추가

- 가장 마지막 노드를 찾아 그 뒤에 데이터를 추가한다.

1. 재귀함수를 통해 마지막 노드까지 찾아간다.

2. 새로운 데이터를 동적할당을 한 뒤, 마지막 노드에 연결해준다.

Node* AddData(Node* node, int data)
{
    if (node == NULL)
    {
    	Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->NEXT = NULL;

        return newNode;
    }

    node->NEXT = AddData(node->NEXT, data);
    return node;
}

 

 

탐색

- 이부분 역시 재귀함수로 데이터를 비교해서 같은 노드를 반환하면 된다.

Node* Search(Node* node, int data)
{
    if (node == NULL)
        return NULL;
	
    if (node->data == data)
        return node;

    return Search(node->NEXT, data);
}

 

 

삭제

1. 재귀함수로 데이터가 같은 노드를 찾는다.

2. 같은 노드를 찾으면 찾은 노드에 연결된 리스트를 임시 변수에 저장해둔다.

3. 찾은 노드의 동적할당을 해제한다.

4. 2번에 저장해둔 다음 리스트를 반환한다.

Node* Delete(Node* node, int data)
{
    if (node == NULL) return NULL;
	
    if (node->data == data)
    {
        Node* nextNode = node->NEXT;
        free(node);
		
        return nextNode;
    }
	
    node->NEXT = Delete(node->NEXT, data);
    return node;
}

 

 

여기까지만 구현해 두면, 어느 특정 위치에 데이터를 끼워넣든 삭제하든 나머지는 응용하기 나름이다.

마지막으로 풀 소스 코드를 올려본다.

#include <stdio.h>
#define MAX 10

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

Node* AddData(Node* node, int data)
{
    if (node == NULL)
    {
    	Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->NEXT = NULL;

        return newNode;
    }

    node->NEXT = AddData(node->NEXT, data);
    return node;
}

void ShowAllData(Node* node)
{
    if (node == NULL) return;

    printf("%d ", node->data);
    ShowAllData(node->NEXT);
}

Node* Search(Node* node, int data)
{
    if (node == NULL)
        return NULL;
	
    if (node->data == data)
        return node;

    return Search(node->NEXT, data);
}

Node* Delete(Node* node, int data)
{
    if (node == NULL) return NULL;
	
    if (node->data == data)
    {
        Node* nextNode = node->NEXT;
        free(node);
		
        return nextNode;
    }
	
    node->NEXT = Delete(node->NEXT, data);
    return node;
}

void main()
{
    Node* head = NULL;
    //데이터 추가
    for(int i = 0; i < MAX; i++)
        head = AddData(head, i);
    ShowAllData(head);
    
    //결과 : 0 1 2 3 4 5 6 7 8 9
    
    //탐샋
    Node* someNode = Search(head, 5);
    if(someNode != NULL)
        printf("%d\n", someNode->data);
        
    //결과 : 5
    
    //삭제
    head = Delete(head, 8);
    ShowAllData(head);
    //결과 : 0 1 2 3 4 5 6 7 9
}