[C언어] 링크드 리스트 구현

https://domaindeveloper.tistory.com/20

[자료구조] 링크드 리스트(linked list)

(링크드 리스트에 대한 설명)

노드를 C언어로 표현하면 구조체로 나타낼 수가 있다.

 

typedef struct Node
{
    int Data;  //데이터 필드
    struct Node* NextNode; //다음 노드를 가르키는 포인터
} Node;

 

링크드 리스트에서 필요한 연산은 다섯 가지가 있다.

• 노드 생성 / 소멸
• 노드 추가
• 노드 탐색
• 노드 삭제
• 노드 삽입

 

1. 노드 생성 / 소멸

//노드 생성
Node* CreateNode(ElementType NewData) //elementtype 에는 int, double등등
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
    
    
    NewNode->Data = NewData;  //데이터 저장
    NewNode->NextNode = NULL; //다음노드는 NULL로 초기화
    
    return NewNode;
}

//노드 소멸
void DestroyNode(Node* Node)
{
    free(Node);
}

malloc을 사용하여 노드를 생성하는 이유는 노드를 자유 저장소에 생성하기 위함이다.

 

노드를 자동 메모리에 저장한다면, 노드 생성 함수가 끝나고 자동으로 메모리에서 소멸되어 버린다.

 

void* malloc(size_t size);
void free(void *memblock);

malloc과 free의 함수이다.

이것을 보면 함수를 어떻게 사용해야 할지 알게 된다.

ElementType* something = (ElementType*)malloc(sizeof(ElementType));
free(something);

2. 노드 추가

 

노드 추가란 링크드 리스트의 테일노드에 새로운 노드를 만들어 연결하는 것이다.

 

새로운 노드를 만들어 덧붙였다면, 새로운 노드를 tail로 바꾸어 줘야 한다.

append Node

 

void AppendNode(Node** Head, Node* NewNode)
{
    if( (*Head) == NULL ) //(*Head)가 NULL이란 말은 LinkedList가 안만들어 졌다는 것
    {
        *Head = NewNode; //즉 새로운 노드가 Head
    }
    
    else
    {
        Node* Tail = (*Head);         
        while(Tail->NextNode != NULL) //Tail노드 찾기
        {
            Tail = Tail->NextNode;
        }
        
        Tail->NextNode = NewNode; // Tail노드 찾으면 다음 노드를 newNode로 변경
    }
}

 

구현한 AppendNode의 사용법은 이러하다.

Node* List = NULL;
Node* NewNode = NULL;

NewNode = CreateNode(121);
AppendNode(&List, NewNode);

NewNode = CreateNode(333);
AppendNode(&List, NewNode);

 

3. 노드 탐색

 

노드 탐색은 배열과 비교해서 성능이 떨어지는 부분 중 하나이다.

 

링크드 리스트는 헤드부터 시작해서 다음 노드에 대한 포인터를 따라 노드의 수를 세어나가야만 원하는 노드에 접근할 수 있다.

 

Node* GetNodeLocation(Node* Head, int Location)
{
    Node* Current = Head;
    while(Current != NULL && (--Location) >= 0)
    {
        Current = Current->NextNode;
    }
}

GetNodeLocation은 이렇게 사용한다

Node* List = NULL;
Node* NewNode = NULL;

NewNode = CreateNode(121);
AppendNode(&List, NewNode);

NewNode = CreateNode(333);
AppendNode(&List, NewNode);

MyNode = GetNodeLocation(List, 1) // 두번째 노드를 MyNode에 저장
printf("%d\n", MyNode->Data); //바뀐 보안 정책으로 <printf_s>사용이 권장됨

 

 

4. 노드 삭제

 

노드 삭제는 링크드 리스트 내에 있는 노드를 제거하는 것이다.

삭제할 노드를 찾은 후, 해당노드의 다음 노드를 이전노드의 NextNode 포인터에 연결하면 된다.

Remove Node

void RemoveNode(Node **Head, Node* Remove)
{
    if(*Head == Remove)
    {
        *Head = Remove->NextNode;
    }
    else
    {
        //노드 탐색 부분
        Node* Current = *Head; 
        while( Current != NULL && Current->NextNode != Remove )
        {
            Current = Current->NextNode;
        }
        if(Current != NULL)
        {
            //제거할 노드의 NextNode를 그 앞의 노드의 NextNode로 바꾼다.
            Current->NextNode = Remove->NextNode;
        }
    }
    

}

 

5. 노드 삽입

 

노드 삽입은 노드와 노드사이에 노드를 끼워넣는 것이다.

void InsertNode(Node* Current, Node* NewNode)
{
    NewNode->NextNode = Current->NextNode;
    Current->NextNode = NewNode;
}