연결리스트 (LinkedList)

연결리스트(LinkedList)는 자료구조의 가장 기초적인 자료구조이다.

데이터를 저장하기 위한 선형구조로써 데이터간 1:1로 대응하고 있다.

연결리스트는 크게 데이터와 다음 List를 가리키는 포인터로 이루어져 있다고 생각하면 된다.

위 그림 처럼 연결..... 되어 있다고 생각하면 된다.

먼저 노드를 삽입하기 위해서는

위 순서대로 새로운 노드가 삽입하기 위한 위치의 노드를 가리키고

이전노드가 새로운 노드를 가리키게 됩니다.

다음 노드를 삭제하기 위해서는

이전의 노드가 삭제 하려는 노드가 가리키던 노드를 가리키고...

음...... 제일 첫 번째 노드부터 1, 2, 3번 노드 라 하면

기존에는 1->2, 2->3으로 되어있던 리스트를

1->3으로 변경한 후 2번 노드를 삭제하면 됩니다.

소스코드는 헤더파일과 소스파일로 최대한 모듈화 할려고 생각하여 코딩하였습니다.

많이 부족해도 너그러이 봐주시기 바랍니다.

LinkedList.h

#ifdef _LINKEDLIST_
#endif _LINKEDLIST_

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

typedef struct ListNodeType{
 int data;
 struct ListNodeType* pLink;
}ListNode;

ListNode* CreateNode(int data);  //List 생성
void AddList(ListNode* Head, int data, int index);  //List 추가
void DeleteList(ListNode* Head, int index);  //List삭제
int GetList(ListNode* Head, int index);   //해당 index 데이터 반환
void PrintList(ListNode* Head);   //전체 List 출력

LinkedList.c

#include"LinkedList.h"

static int count=0;

//-----------------------------------------------------------
//LinkedList 생성 위한 함수
//함수명 : CreateNode
//입력인자 : 입력 데이터
//반환값 : List 포인터(헤더)
//-----------------------------------------------------------
ListNode* CreateNode(int data)
{
 ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
 if(NewNode==NULL)
 {
  printf("Create Error\n");
  return; 
 }

 NewNode->data=data;  //데이터 입력
 NewNode->pLink=NULL; //첫 헤더 생성이기에 다음 포인터 = NULL
 count++;
 return NewNode;
}

//--------------------------------------------------------
//List 추가 함수
//함수명 : AddList
//입력인자 : ListNode *Head, int data(입력 데이터), int index(몇 번째 리스트)
//--------------------------------------------------------
void AddList(ListNode* Head,int data, int index)
{
 int i;
 ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
 ListNode* PreNode = (ListNode*)malloc(sizeof(ListNode));
 //NewNode가 NULL이거나 원하는 위치가 전체 List의 개수보다 클때
 if(index>count) 
 {
  printf("Add Error\n");
  return; 
 }
  
 PreNode=Head;

 for(i=1;i<index;i++) 
 {
  PreNode=PreNode->pLink;
 }

 NewNode->pLink=PreNode->pLink;
 PreNode->pLink=NewNode;

 NewNode->data=data; 

 count++;     //List 갯수 카운트 증가 
}

//List제어 함수
//함수명 : DeleteList
//입력인자 : 최초위치 알기 위한 Head와 삭제 Index
void DeleteList(ListNode* Head, int index)
{
 int i;
 ListNode* PreNode = (ListNode*)malloc(sizeof(ListNode));
 ListNode* DeleteNode = (ListNode*)malloc(sizeof(ListNode));
 
 if(index>count) 
 {
  printf("Add Error\n");
  return; 
 }

 PreNode=Head;

 for(i=1;i<index;i++) 
 {
  PreNode=PreNode->pLink;
 }
 
 DeleteNode=PreNode->pLink;
 PreNode->pLink=DeleteNode->pLink;

 count--;     //List 갯수 카운트 감소 
 free(DeleteNode);
}

//index의 위치의 값 알기 위한 함수
//index 위치의 값을 반환한다.
int GetList(ListNode* Head, int index)
{
 
 int i;
 ListNode* GetNode = (ListNode*)malloc(sizeof(ListNode));
 
 if(index>count) 
 {
  printf("Add Error\n");
  return; 
 }
 GetNode=Head;

 for(i=1;i<index;i++)
 {
  GetNode=GetNode->pLink;
 }

 return GetNode->data;
}

//List에 저장된 모든 값 출력
void PrintList(ListNode* Head)
{
 int i=0;
 ListNode* Node = (ListNode*)malloc(sizeof(ListNode));

 Node=Head;

 while(i!=count)
 {
  printf("index : %d, Data : %d \n", i++, Node->data);
  Node=Node->pLink;
 }

}