[알고리즘] Linked List ( 노드 추가, 탐색, 삭제, 삽입 )

https://steady-developer-hyemin.tistory.com/17

[알고리즘] Linked List ( List / Linked List 란? )

https://steady-developer-hyemin.tistory.com/18

[알고리즘] Linked List ( 노드 생성 / 소멸 )

노드 추가 연산

- 링크드 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 것을 의미합니다.

- 자유 저장소에 노드를 생성한 다음, 새로은 노드의 주소를 테일의 NextNode 포인터에 대입하면 됩니다.

/* 노드 추가 */
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;
    }
}

*Head가 NULL인 경우에는 링크드 리스트의 헤드가 새로운 노드를 가리키도록 합니다.

이 것은 링크드 리스트가 비어있는 경우 새 노드가 링크드 리스트의 유일한 노드가 되는 상황을 처리합니다.

 

*Head가 NULL이 아닌 경우, 링크드 리스트의 끝까지 이동한 뒤에 새로운 노드를 추가합니다.

끝까지 이동하기 위해 Tail이라는 포인터를 사용합니다.

 

Tail -> NextNode 가 NULL인 지점을 찾으면, 이 위치에 NewNode를 연결하여 링크드 리스트의 끝에 새로운 노드를 추가합니다.

 

 

이렇게 구현한 함수는 다음과 같이 사용합니다.

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

NewNode = SLL_CreateNode( 110 ); /* 자유 저장소에 노드 생성 */
SLL_AppendNode(&List, NewNode); /* 생성한 노드를 List에 추가 */

NewNode = SLL_CreateNode( 150 ); /* 자유 저장소에 노드 생성 */
SLL_AppendNode(&List, NewNode); /* 생성한 노드를 List에 추가 */

 

노드 탐색 연산

- 탐색 연산은 링크드 리스트가 갖고 있는 약점 중 하나 입니다.

- 배열이 인덱스를 이용하여 즉시 원하는 요소를 취할 수 있게 하는데 반해, 링크드 리스트는 헤드부터 시작해서 다음 노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 수를 세어나가야만 원하는 요소에 접근할 수 있습니다.

 

/* 노드 탐색 */
Node* SLL_GetNodeAt(Node* Head, int Location)
{
	Node* Current = Head;
    
    While (Current != NULL && (--Location) >= 0)
    {
    	Current = Current -> NextNode;
    }
    return Current;
}

(Location : 찾고자 하는 노드의 위치를 나타내는 정수)

Current 포인터를 Head로 초기화 합니다. 포인터는 링크드 리스트를 순회하면서 현재 위치를 나타냅니다.

 

While 루프를 사용하여 Current가 NULL이 아니고, Location이 0보다 크거나 같을 때까지 루프를 실행합니다.

이 때, Location을 1씩 감소 시키고, Current를 다음 노드로 이동 시킵니다. 위치가 0이거나 Current가 NULL이 되면 루프가 종료됩니다.

 

루프가 종료되면 Current는 찾고자 하는 위치에 있는 노드를 가리키게 됩니다. 그리고 노드의 포인터를 반환합니다.

 

다음과 같이 사용할 수 있습니다.

Node* List = NULL;
Node* MyNode = NULL;

SLL_AppendNode( &List, SLL_CreateNode (110) ); /* 노드를 생성하여 List에 추가 */
SLL_AppendNode( &List, SLL_CreateNode (150) ); /* 노드를 생성하여 List에 추가 */

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

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

 

노드 삭제 연산

- 링크드 리스트 내에 있는 임의의 노드를 제거하는 연산입니다.

- 삭제하고자 하는 노드를 찾은 후, 해당 노드의 다음 노드를 이전 노드의 NextNode 포인터에 연결하면 됩니다.

/* 노드 제거 */
void SLL_RemoveNode(Node** Head, Node* Remove)
{
    if (*Head == Remove)
    {
        *Head = Remove->NextNode;
        free(Remove);
    }
    else
    {
        Node* Current = *Head;
        while (Current != NULL && Current->NextNode != Remove)
        {
            Current = Current->NextNode;
        }
        if (Current != NULL)
        {
            Current->NextNode = Remove->NextNode;
            free(Remove);
        }
    }
}

if (*Head == Remove ) { ... }

삭제하려는 노드가 링크드 리스트의 첫 번째 노드인 경우 처리 합니다.

링크드 리스트의 헤드를 삭제하려는 노드의 다음 노드로 업데이트하고, free(Remove)를 호출하여 메모리를 해제합니다.

이렇게 함으로써 첫 번째 노드를 삭제하고 메모리 누수를 방지할 수 있습니다.

 

else { ... }

삭제하려는 노드가 링크드 리스트 중간에 있는 경우 처리 합니다.

while 루프를 사용하여 삭제하려는 노드의 이전 노드를 찾습니다. 

이전 노드의 NextNode를 삭제하려는 노드의 다음 노드로 연결하고, free(Remove)를 호출하여 메모리를 해제합니다.

Node* List = NULL;
Node* MyNode = NULL;

SLL_AppendNode( &List, SLL_CreateNode (110) ); /* 노드를 생성하여 List에 추가 */
SLL_AppendNode( &List, SLL_CreateNode (150) ); /* 노드를 생성하여 List에 추가 */

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

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

SLL_DestroyNode (MyNode ); /* 링크드 리스트에서 제거한 노드를 메모리에서 완절히 소멸 */

 

노드 삽입 연산

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

/* 노드 삽입 */
void SLL_InsertAfter(Node* Current, Node* NewNode)
{
	NewNode -> NextNode = Current -> NextNode;
    Current -> NextNode = NewNode;
}

새로운 노드(NewNode)의 NextNode 포인터를 현재 노드(Current)의 NextNode가 가리키는 노드로 설정합니다.

새로운 노드가 현재 노드 뒤에 오게 됩니다. 기존의 다음 노드를 새로운 노드의 다음 노드로 연결합니다.

 

현재 노드(Current)의 NextNode포인터를 새로운 노드(NewNode)로 설정합니다.

현재 노드의 다음 노드가 새로운 노드를 가리키게 됩니다. 따라서 새로운 노드가 현재 노드 뒤에 삽입되게 됩니다.

 

새 노드 기준 : 앞 노드의 NextNode 포인터가 자신을 가리키게 하고, 자신의 NextNode 포인터가 뒤 노드를 가리키게 합니다.