[자료구조 공부] 단방향 LinkedList 구현

링크드 리스트(Linked List)란

- 데이터 항목들이 노드라는 개별 단위로 구성

- 각 노드가 다음 노드를 가리키는 참조(주로 포인터)를 통해 순서대로 연결되어 있는 선형 자료구조

- 링크드 리스트는 동적으로 데이터를 저장할 수 있어, 배열과 비교했을 때 크기 조정의 유연성이 뛰어납니다.

*선형 자료구조: 데이터 요소들이 순차적으로 나열된 구조

링크드 리스트의 기본 구조

노드(Node): 데이터와 다음 노드를 가리키는 포인터(또는 참조)를 포함합니다. 마지막 노드는 다음 노드가 없다는 것을 나타내기 위해 보통 null을 포인터 값으로 가집니다.
헤드(Head): 리스트의 첫 번째 노드를 가리키는 참조입니다. 리스트의 시작점 역할을 합니다.

링크드 리스트의 종류

단일 연결 리스트(Singly Linked List): 각 노드가 오직 다음 노드만을 가리키는 가장 간단한 형태의 링크드 리스트입니다. 순방향 탐색만 가능합니다.

2. 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드 양쪽을 가리키는 참조를 가지고 있어, 양방향 탐색이 가능한 구조입니다.

3. 원형 연결 리스트(Circular Linked List): 마지막 노드와 첫번째 노드가 서로를 가리켜 원형처럼 연결된 구조입니다. 단일 또는 이중 연결 리스트가 원형 형태를 가질 수 있습니다.

링크드 리스트의 장점

동적 크기 조정: 미리 크기를 지정할 필요 없이 데이터를 추가하거나 삭제할 때 메모리를 동적으로 할당하거나 해제할 수 있습니다.
효율적인 삽입/삭제: 배열에 비해 특정 위치에 데이터를 삽입하거나 삭제하는 과정이 메모리 재할당이나 데이터의 이동 없이 포인터 조정만으로 가능합니다.

링크드 리스트의 단점

랜덤 액세스 불가: 배열과 달리 특정 인덱스의 데이터에 직접 접근할 수 없어, 원하는 위치를 찾기 위해서는 처음부터 순차적으로 탐색해야 합니다.
메모리 사용 증가: 각 노드마다 데이터 외에도 포인터(참조)를 저장해야 하므로, 추가적인 메모리 공간이 필요합니다.
포인터 오류 가능성: 포인터를 잘못 관리하면 메모리 누수, 리스트의 손상 등의 문제가 발생할 수 있습니다.

더블 포인터를 사용한 싱글 링크드 리스트의 구현 코드

- 싱글 링크드 리스트 구현 코드입니다.

더블 포인터란

포인터의 포인터를 의미합니다. 즉, 포인터 변수가 메모리 주소를 저장하는 것처럼, 더블 포인터는 다른 포인터 변수의 메모리 주소를 저장합니다.

LinkedList.c

Node* SLL_CreateNode(ElementType NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));

    NewNode->Data = NewData;  
    NewNode->NextNode = NULL; 
    return NewNode;
}

Node* SLL_CreateNode(int newData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));

    NewNode->Data = newData;
    NewNode->NextNode = NULL;

    return NewNode;
}



void SLL_AppendNode(Node** Head, Node* NewNode)
{
    if ( (*Head) == NULL ) 
    {        
        *Head = NewNode;
    } 
    else
    {
        Node* Tail = (*Head);
        while ( Tail->NextNode != NULL )
        {
            Tail = Tail->NextNode;
        }

        Tail->NextNode = NewNode;
    }
}


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

void  SLL_InsertNewHead(Node** Head, Node* NewHead)
{
    if ( Head == NULL )
    {
        (*Head) = NewHead;    
    }
    else
    {
        NewHead->NextNode = (*Head);
        (*Head) = NewHead;
    }
}


void SLL_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 )
            Current->NextNode = Remove->NextNode;
    }
}

Node* SLL_GetNodeAt(Node* Head, int Location)
{
    Node* Current = Head;

    while ( Current != NULL && (--Location) >= 0)
    {
        Current = Current->NextNode;
    }

    return Current;
}


int SLL_GetNodeCount(Node* Head)
{
    int   Count = 0;
    Node* Current = Head;

    while ( Current != NULL )
    {
        Current = Current->NextNode;
        Count++;
    }

    return Count;
}

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode
{
    ElementType Data;
    struct tagNode* NextNode;
} Node;

Node* SLL_CreateNode(ElementType NewData);
void  SLL_DestroyNode(Node* Node);
void  SLL_AppendNode(Node** Head, Node* NewNode);
void  SLL_InsertAfter(Node* Current, Node* NewNode);
void  SLL_InsertNewHead(Node** Head, Node* NewHead);
void  SLL_RemoveNode(Node** Head, Node* Remove);
Node* SLL_GetNodeAt(Node* Head, int Location);
int   SLL_GetNodeCount(Node* Head);

#endif

Test_LinkedList.c

#include "LinkedList.h"

int main( void )
{
    int   i       = 0;
    int   Count   = 0;
    Node* List    = NULL;
    Node* Current = NULL;
    Node* NewNode = NULL;

    for ( i = 0; i < 5; i++ )
    {
        NewNode = SLL_CreateNode(i);
        SLL_AppendNode(&List, NewNode);
    }


    NewNode = SLL_CreateNode(-1);
    SLL_InsertNewHead(&List, NewNode);

    NewNode = SLL_CreateNode(-2);
    SLL_InsertNewHead(&List, NewNode);

    Count = SLL_GetNodeCount(List);
    for ( i = 0; i<Count; i++ )
    {
        Current = SLL_GetNodeAt(List, i);
        printf("List[%d] : %d\n", i, Current->Data);
    }

    printf("\nInserting 3000 After [2]...\n\n");

    Current = SLL_GetNodeAt(List, 2);
    NewNode  = SLL_CreateNode(3000);

    SLL_InsertAfter(Current, NewNode);

    Count = SLL_GetNodeCount(List);
    for ( i = 0; i<Count; i++ )
    {
        Current = SLL_GetNodeAt(List, i);
        printf("List[%d] : %d\n", i, Current->Data);
    }

    printf("\nDestroying List...\n");

    for ( i = 0; i<Count; i++ )
    {
        Current = SLL_GetNodeAt(List, 0);

        if ( Current != NULL ) 
        {
            SLL_RemoveNode(&List, Current);
            SLL_DestroyNode(Current);
        }
    }

    return 0;
}

더블 포인터가 필요한 이유

1) 함수가 호출이 종료되는 시점에 매개변수가 메모리 해제된다. 이로인해 함수의 매개변수 Head가 Heap 영역에서 가리키는 개체를 참조하지 않는다.

2) 그럼으로 매개변수 Head에 List의 주소 값을 넣는다. Head는 포인터 List를 가리키게 된다.

ex) Node** Head로 되어 있으면 List를 가리키려면 *Head를 하면된다.

*Head 시 List 변수를 가리키고 List 변수가 갖고있는 값은 메모리 어딘가의 쓰레기 값이다.

3) 이 때 NewNode가 Heap 영역의 NewNode를 가리키게 하기 위해 주소 값 newNode의 주소 값을 넣는다.

문톰의 긍정코딩