[ 자료구조 ] 싱글 링크드 리스트(Single Linked List)

배열 유감

임의의 디렉토리 내에 존재하는 파일의 목록으로 소트웨어가 필요로 한다면 어떻게 해야 할까? 그 디렉토리 내에 존재하는 파일은 0개일 수도, 10개일 수도, 수천, 수만 개일 수도 있다.

 

"아, 제발 파일이 항상 10개 미만으로만 있으면 좋겠다.ㅠㅠ"라는 염원 하나로 다음과 같이 배열을 선언할 수 있을까?

 

char* files[10];

 

그렇다고 무작정 크게 선언할 수도 없다. 53365개보다 더 많은 파일이 존재할 수도 있으니 말이다.

 

char* files[53365];

 

너무 작게 선언하자니 일을 제대로 할 수가 없고 무작정 크게 선언하자니 메모리가 울 것 같다. 이 문제를 해결하기 위해 필요한 것은 배열처럼 데이터 집합을 보관하는 기능을 가지면서도, 한편으로는 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조이다. 이 자료구조는 '리스트(List: 목록)"라고 불린다. 리스트는 스택과 큐, 그리고 트리와 같은 자료구조를 이해할 수 있는 기반이 된다는 점에서 중요한 의미를 가진다.

링크드 리스트

구조체 (C 언어)

 

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

 

C++에서는 다음과 같이 작성해도 struct 키워드 없이 Node 구조체의 인스턴스를 만들 수 있지만, C 언어에서는 항상 귀찮은 struct 키워드를 동반해야 한다.

 

Node node; /* C++ */

struct Node node; /* C언어 */

 

따라서 typedf 키워드를 이용해서 Node 구조체를 정의하자.

 

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

 

노드 생성

 

Node* CreateNode(int NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
    
    NewNode->Data = NewData;
    NewNode->NextNode = NULL;
    
    return NewNode;
}

 

왜 NewNode를 malloc() 함수로 동적 할당하여 선언하였을까?의 답변과 관련된 글

[ 정적 메모리, 자동 메모리, 자유 저장소와 malloc() 함수, free() 함수 ]

노드 소멸

 

void DestoryNode(Node* Node)
{
    free(Node);
}

 

노드 추가

노드 추가 연산은 링크드 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 것이다. CreateNode() 함수로 노드를 생성하고, 생성된 노드의 주소 값을 현재 링크드 리스트의 테일 노드의 NextNode로 지정해주면 된다.

 

void AppendNode(Node** Head, Node* NewNode)
{
    /* 헤드 노드가 NULL이라면 새로운 노드가 Head가 된다. */
    if((*Head) == NULL)
    {
        *Head = NewNode;
    }
    else
    {
        /* Tail을 찾아서 NewNode를 연결한다. */
        Node* Tail = (*Head);
        while(Tail->NextNode != NULL)
        {
            Tail = Tail->NextNode;
        }
        
        Tail->NextNode = NewNode;
    }
}

 

노드 탐색

링크드 리스트는 배열처럼 인덱스를 이용하여 즉시 원하는 요소를 얻어낼 수 없다. 헤드부터 시작해서 다음 노드에 대한 포인터를 징검다리 삼아 노드의 수를 세어나가야만 원하는 요소에 접근할 수 있다.

 

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

 

노드 삭제

링크드 리스트 내에 있는 임의의 노드를 제거하는 연산이다. 삭제하고자 하는 노드를 찾은 후, 이전 노드의 다음 노드를 현재 노드의 다음 노드로 연결시키면 된다.

 

void DeleteNodeAt(Node* Head, Node* Remove)
{
    if(Head == Remove)
    {
        Head = Head->NextNode;
    }
    else
    {
        Node* Current = Head;
        while(Current != NULL && Current->NextNode != Remove)
        {
            Current = Current->NextNode;
        }
        
        if(Current != NULL)
        {
            Current->NextNode = Remove->NextNode;
        }
    }
}

 

노드 삽입

노드와 노드 사이에 새로운 노드를 끼워 넣는 연산이다.

 

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

 

 

[참고] 뇌를 자극하는 알고리즘