Data Structure/자료구조

[자료구조] 단순 연결 리스트 구현

lumana 2024. 3. 26. 01:27

Singly Linked List(SLL) 구현

구조체

typedef int ElementType; // 필요할 때 원하는 타입으로 바꿔 쓰자

typedef struct tagNode {
    ElementType Data; // 데이터
    struct tagNode* NextNode; // 다음 노드
} Node;

연결 리스트의 주요 연산

  • 노드 생성 / 소멸
    • 힙(자유 저장소)에 새로운 노드를 생성
Node* SLL_CreateNode(ElementType newData) {
    Node* NewNode = (Node*)malloc(sizeof(Node)); // 새로운 노드 동적할당으로 생성

    NewNdoe->Data = newData; // 데이터 저장
    NewNode->NextNode = NULL; // 다음 노드에 대한 포인터는 NULL로 초기화

    return NewNode; // 새롭게 할당한 노드의 주소 반환
}

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

  • 노드 추가
    • 연결 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 연산(꼬리를 덧붙임)
    • 힙에 새로운 노드를 생성한 다음 그 주소를 테일의 NextNode 포인터에 저장하면 된다.
void SLL_AppendNode(Node** Head, Node* NewNode) {
    // 헤드 노드가 NULL이면 새로운 노드가 헤드 노드가 된다
    if ((*Head) == NULL) {
        *Head == NewNode;
    }
    else {
        // 일단 테일 노드를 헤드 노드로 두고 테일을 찾는다.
        Node* Tail = (*Head);
        // 테일의 NextNode가 NULL이 나올 때 까지 테일을 NextNode로 옮긴다
        while (Tail->NextNode != NULL) {
            Tail = Tail->NextNode;
        }
        // Tail 노드를 찾았으면 Tail노드의 NextNode가 새로 생성한 NewNode를 가리키게 한다
        Tail->NextNode = NewNode;
    }
}

// 사용법
Node* List = NULL;
Node* NewNode = NULL;
NewNode = SLL_CreateNode(117); // 힙에 새로운 노드를 생성
SLL_AppendNode(&List, NewNode); // 생성한 노드를 List에 추가
NewNode = SLL_CreateNode(119); // 힙에 또 다른 노드를 생성
SLL_AppendNode(&List, NewNode); // 생성한 노드를 List에 추가
  • AppendNode의 파라미터에서 Head를 이중포인터로 받는 이유는 함수 내에서 포인터를 매개변수로 받아 수정하려면 이중 포인터가 필요하기 때문이다. Node* Head로 선언하면 깊은 복사가 일어나서 실제론 값이 변하지 않기 때문!
  • 단순히 에스터리스크가 있다고 해서 call by address로 작동할 거라고 생각하면 안 된다. (Node* 자체는 Node형을 가리키는 주소 값 이니까)
  • 노드 탐색
    • 배열과 다르게 링크드 리스트는 헤드부터 시작해서 차근 차근 노드의 개수만큼 노드를 거쳐야 원하는 요소에 접근할 수 있다.
    • 임의의 위치에 있는 노드를 찾아 반환하는 함수
    • 코드
// Location 만큼 이동한다
Node* SLL_GetNodeAt(Node* Head, int Location) {
    Node *current = Head;
    while (current != NULL && (--Location) >= 0) {
    current = current->NextNode;
    }
    return current;
}
  • 사용 예시
Node* List = NULL;
Node* Mynode = NULL;

SLL_AppendNode(&List, SLL_CreateNode(117));
SLL_AppendNode(&List, SLL_CreateNode(119));

MyNode = SLL_GetNodeAt(List, 1); // 두 번째 노드의 주소를 MyNode 에 저장
printf("%d\n", MyNode->Data); // 119 출력

 

  • 노드 삭제
    • 삭제하고자 하는 노드를 찾은 후 해당 노드의 다음 노드를 이전 노드의 NextNode 포인터에 연결하면 그 노드를 삭제할 수 있음
    • 코드
//  노드 제거 
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* List = NULL;
Node* MyNode = NULL;

SLL_AppendNode(&List, SLL_CreateNode(117));
SLL_AppendNode(&List, SLL_CreateNode(119));
SLL_AppendNode(&List, SLL_CreateNode(212));

MyNode = SLL_GetNodeAt(List, 1); // 두 번째 노드의 주소를 MyNode 에 저장
printf("%d\n", MyNode->Data); // 119 출력

SLL_RemoveNode(&List, MyNode); // 두 번째 노드 제거

SLL_DestroyNode(Mynode); // 링크드 리스트에서 제거한 노드를 메모리에서 완전히 소멸시킴

 

  • 노드 삽입
    • 이전 노드의 NextNode 포인터가 새로운 노드를 가리키고, 새 노드의 NextNode 포인터가 다음노드를 가리킨다
void SLL_InsertAfter(Node* Current, Node* NewNode)
{
        NewNode->NextNpde = Current->NextNode;
        Current->NextNode = NewNode;
}
  • 노드 개수 세기 연산
    • 링크드 리스트 내에 존재하는 노드의 개수를 세어 그 결과를 반환
    • 코드
      int SLL_GetNodeCount(Node* Head)
  {
          int Count = 0;
          Node* Current = Head;

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

          return Count++;
  }

링크드 리스트 예제 프로그램

#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* NewHead);    // 노드 추가
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);                   // 노드 개수

int main()
{
    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);

    // 노드 리스트 출력
    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;
}

// 노드 생성
Node* SLL_CreateNode(ElementType newData)
{
    Node* newNode = (Node*)malloc(sizeof(Node));


    newNode->data = newData;    // 데이터 저장
    newNode->nextNode = NULL;   // 다음 노드에 대한 포인터 NULL로 초기화

    return newNode;     // 노드 주소 반환
}

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

// 노드 추가
void SLL_AppendNode(Node** head, Node* newNode)
{
    // 헤드 노드가 NULL일 경우 새로운 헤드 생성
    if((*head) == NULL) {
        *head = newNode;
    }
    else {
        // 헤드가 존재할 경우 테일을 찾아 NewNode를 연결
        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* removeNode)
{
    if(*head == removeNode)
    {
        *head = removeNode->nextNode;
    }
    else {
        Node* current = *head;
        while(current != NULL && current->nextNode != removeNode) {
            current = current->nextNode;
        }

        if(current != NULL) {
            current->nextNode = removeNode->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;

    // 다음 노드가 NULL이 아닐 경우 카운트 1씩 증가
    while(current != NULL) {
        current = current->nextNode;
        count++;
    }

    return count;
}

링크드 리스트의 장단점

  • 단점
    • 다음 노드를 가리키는 포인터 때문에 각 노드마다 추가적인 메모리가 필요함
    • 특정 위치에 있는 노드에 접근하기 위한 비용이 크며, 접근 시간도 많이 소요된다
  • 장점
    • 새로운 노드의 추가, 삽입, 삭제가 쉽고 빠름
      • 현재 노드의 다음 노드를 얻어오는 연산에 대해서는 비용이 발생하지 않음(단점은 아닌데 장점이라 보기도 애매하긴 하네요)
    • * 반면 배열은 새로운 요소를 삽입하거나 기존 요소를 제거하기가 어려움
  • DB에서 조회한 레코드를 순차적으로 다루는데 아주 적합함(순차 접근 + 추가 삽입 삭제 --> 찰떡)

참조) 박상현, 『이것이 자료구조+알고리즘이다 with C언어』, 한빛미디어(2022)

'Data Structure > 자료구조' 카테고리의 다른 글

[자료구조] 배열 기반 스택 구현  (0) 2024.03.26
[자료구조] 환형 링크드 리스트 구현  (0) 2024.03.26
[자료구조] 이중 연결 리스트(Doubly Linked List) 구현  (0) 2024.03.26
[자료구조] 스택의 응용 - 미로 탐색  (0) 2024.01.15
[자료구조] 스택의 응용 - 후위 표기 수식의 계산  (0) 2024.01.15

'Data Structure/자료구조'의 다른글

  • 현재글[자료구조] 단순 연결 리스트 구현

관련글

티스토리툴바