은근한

Linked List [연결리스트] 본문

ALGORITHM/Data Structure

Linked List [연결리스트]

EsJoo 2016. 1. 16. 21:29

연결리스트란?


각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

데이터를 담고 있는 노드들이 연결되어 있는 상태이며 이러한 연결을 하기위해 포인터를 사용해 연결을 시켜준다.

연결리스트 종류는 단순연결리스트, 이중연결리스트 등이 있다.


LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
 
#include<stdio.h>
#include<stdlib.h>
 
typedef int ElemetType;
 
typedef struct tagNode
{
    ElemetType Data;
    struct tagNode* NextNode;
} Node;
 
Node* SLL_CreateNode(ElemetType 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
 
cs

헤더파일, 구조체 선언, 함수 선언부를 정리한 헤더파일(.h) 입니다.


LinkedList.c

 
#include "LinkedList.h"
 
Node* SLL_CreateNode(ElemetType 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)
{
    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;
}

cs

헤더파일에 선언된 함수의 원형 부분을 구현하여 함수정의부분입니다.


main.c

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
 
#include<stdio.h>
#include<stdlib.h>
 
typedef int ElemetType;
 
typedef struct tagNode
{
    ElemetType Data;
    struct tagNode* NextNode;
} Node;
 
Node* SLL_CreateNode(ElemetType 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
cs
헤더파일과 함수정의 파일을 ifndef 및 define으로 포함하여

메인 함수에서 사용한 파일입니다.



저작자표시

'ALGORITHM > Data Structure' 카테고리의 다른 글

실력키우기 - 자료처리 [Insertion Sort]  (0) 2016.01.18
실력키우기 - 자료처리 [Queue]  (0) 2016.01.18
실력키우기 - 자료처리 [stack]  (0) 2016.01.18
'ALGORITHM/Data Structure' Related Articles more