Linked List(1) - Singly Linked List

Singly Linked List는 한쪽 방향으로만 엮어 있는 Linked List이다.

 

주요 연산: 

-노드 생성/소멸

-노드 추가

-노드 탐색

-노드 삭제

-노드 삽입

 

장점: 새로운 노드의 추가/삽입/삭제가 쉽고 빠르다. 배열은 요소를 삽입하거나 제거하기가 어렵다.

단점: 포인터 때문에 노드마다 추가의 메모리가 필요하다. 특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도도 느리다.

 

노드 포인터는 head와 tail이 있고, 노드 구성은 data와 pointer로 되어있다.

// g++ -o singlyLinkedList.exe singlyLinkedList.cpp; ./singlyLinkedList.exe

#include <iostream>
typedef int ElementType;
typedef struct tagNode
{
    ElementType Data;
    struct tagNode* nextNode;
} Node;

// 노드 생성
Node* SLL_CreateNode(ElementType NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->Data = NewData;
    NewNode->nextNode = NULL;
    return NewNode;
}
// 노드 소멸
void SLL_DestroyNode(Node* Node)
{
    free(Node);
}
// 노드 추가
void SLL_AppendNode(Node** Head, Node* NewNode) //Node* Head이지 않은 이유는 지역변수로 저장되기 때문에
{
    if((*Head) == NULL)
        *Head = NewNode;
    else
    {
        Node* Tail = (*Head);
        while(Tail->nextNode != NULL)
            Tail = Tail->nextNode;
        Tail->nextNode = NewNode;
    }
}
// 노드 탐색
Node* SLL_GetNodeAt(Node* Head, int Location)
{
    Node* Current = Head;
    while(Current != NULL && (--Location) >= 0)
        Current = Current->nextNode;
    return Current;
}
// 노드 삭제. 호출 이휴 SLL_DestroyNode함수를 호출하여야 한다.
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;
        // 해당 노드의 다음 노드를 이전 노드의 nextNode 포인터에 연결
    }
}
// 노드 삽입
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;
}
//노드 수 세기
int SLL_GetNodeCount(Node* Head)
{
    int count = 0;
    Node* Current = Head;
    while(Current != NULL)
    {
        Current = Current->nextNode;
        count++;
    }
    return count;
}
int main()
{
    int i = 0;
    int count = 0;
    Node* List = NULL;
    Node* current = NULL;
    Node* newNode = NULL;

    for(i=0;i<5;i++)
        SLL_AppendNode(&List, SLL_CreateNode(i));
    SLL_InsertNewHead(&List, SLL_CreateNode(-1));
    SLL_InsertNewHead(&List, SLL_CreateNode(-2));
    count = SLL_GetNodeCount(List);
    for(i=0;i<count;i++)
    {
        current = SLL_GetNodeAt(List, i);
        printf("List[%d] : %d \n", i, current->Data);
    }
}

https://download.hanbit.co.kr/exam/1687/ 에서 소스코드 확인이 가능하다.