[C/C++]단 방향 LinkedList 이용한 삽입,삭제,검색,갱신

C나 C++을 이용할 때면,



LinkedList를 많이 쓰는데,


항상 쓸 때 마다 잊어 먹는 적이 많아서...


적어 두려 합니다.


LinkeList는

구조체로 되어있는 포인터에 다음 메모리 주소를 가르키는 link를 연결하여,


그 값에 접근 하는 형식의 구조를 띄고 있습니다.


LinkedList의 기본 개념은

구조체 안에 다음 구조체의 주소를 저장하는 개념입니다.

이런식의 선형적 구조를 띄는것이 일반적입니다.

이를 메모리에 나타내 보면

아마 위와 같은 그림으로 표현이 가능할 듯 싶습니다.

이를 토대로 기본적으로 구현해볼 기능은 

CRUD(Create, Remove, Update, Delete) 기능입니다.

구조체를 일단 선언 합니다

char* / int / int 를 삽입하여 보겠습니다.

우선 삽입,

이런 식으로, 초기화 하는 부분, 

Insert 하는 부분을 구분하여 구현 하신다면, 좀더 객관적으로 소스코드 분석 및

구현이 가능할 것입니다.

이를 토대로 List에 insert를 해보는 코드를 삽입하였고,

아래는 결과화면 입니다.

모든 값이 제대로 들어 간 것을 확인하실수 있습니다.

다음으로 삭제 입니다.

삭제의 경우에는 경우의 수가 존재합니다.

1) LinkedList의 처음 부분을 삭제하면서, next에 값이 존재 할 때,

mData->next에 값이 없다면 문제 될 것이 없습니다.

하지만, 값이 존재한다면, mData가 delete 되면서 mData->next의 주소를

찾을 수가 없습니다. 그렇기에 삭제 전에,

mData->next를 mData로 바꾸는 작업이 필요합니다.

2) LinkedList의 중간 부분을 삭제 할 때,

어떻게 보면, 가장 고려할 부분이 없을 것 같습니다.

단순히 mData->next 를 mData->next->next로 주소값을 바꿔 주는 작업만

수행하면 되기 때문입니다.

3) LiknedList의 마지막 부분을 삭제 할 때,

mData->next->next->next 를 NULL로 초기화 하는 작업을 수행하시면 문제 없을 것 

같습니다.

왜 next->next->next를 NULL로 초기화 하냐면, 

쓰레기 값을 가지는 주소를 가지고 있기 때문에, 

(주소 값은 가지고 있는데, 구조체 안 값들이 쓰레기 값)

while(head != NULL)의 코드를 수행할 때, 에러를 발생하기 때문입니다.

다음으로 코드와 결과값 입니다.

순서대로 처음, 중간 마지막을 제거하는 방식으로 진행합니다.

 경우의 수 3가지를 고려하여 삭제에 대해 수행합니다.

삭제 및 출력이 완료된 모습입니다.

갱신 및 검색의 경우도 삭제 연산의 while문을 참고하시면,

쉽게 구현하실 수 있으실 겁니다.

단방향 리스트의 경우나 양방향 리스트의 경우나 별 차이가 없기 때문에,

단순히 pre, next의 주소 값들의 설정 문제이기에, 크게 어렵지 않으실 겁니다.

아래는 전체 소스코드 입니다

// LinkedList.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.

//

#include "stdafx.h"
#include 
using namespace std;

typedef struct Data{
 int data;
 char* string;
 int size;
 Data* next;
}Test;

Test* mData;
void InsertList(int data, char *buf, int size);
Test* InitList(int data, char* buf, int size);
void PrintTest();
void DeletePrint();


void DeletePrint(char* buf)
{
 cout << buf << " / " << "삭제 완료" << endl << endl;
}
bool DeleteList(char* buf) // char 값을 통해 삭제할 데이터 구분
{
 Test* head = mData;
 Test* mTemp = NULL;
 while (head != NULL)
 {
  if (strcmp(buf, head->string) == 0)
  {
   if (head->next != NULL && mTemp != NULL){ // 리스트와 리스트 사이의 값을 삭제 시,
    mTemp->next = head->next;
    delete head;
    DeletePrint(buf);
    return true;
   }else if(head->next == NULL && mTemp != NULL)// 제일 끝 값을 삭제 시
   {
    mTemp->next = NULL;
    delete head;
    DeletePrint(buf);
    return true;
   }
   else if (mTemp == NULL && head->next != NULL) // Head의 값을 삭제시 
   {
    mData = head->next; // 처음 값을 next로 지정
    delete head;
    DeletePrint(buf);
    return true;
   }
  }
  mTemp = head; // 이전 리스트의 주소를 저장
  head = head->next; // 다음으로 이동
 }
 cout << "삭제할 값이 없습니다." << endl;
 return false;

}


void InsertList(int data,char *buf,int size)
{
 if (mData == NULL) // Head 리스트가 NULL일 때,
  mData = InitList(data, buf, size);
 else {
  Test* head = mData; // mData로 search시 주소값이 변경되기에, 대체 리스트 생성
  while (head->next != NULL)
   head = head->next; // 비어있는 리스트 탐색

  head->next = InitList(data, buf, size); // 추가 
 }
}

Test* InitList(int data,char* buf,int size)
{
 Test* mTest = new Test;
 mTest->data = data;
 mTest->string = new char[size];
 memcpy(mTest->string, buf, size);
 mTest->size = size;
 mTest->next = NULL;

 return mTest;

} // 초기화 및 할당

void PrintTest()
{
 Test* head = mData;
 while (head != NULL)
 {
  cout << head->string << " / " << head->data << " / " << head->size << endl;
  head = head->next;
 }
 cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
 
 InsertList(0, "test0", 6);
 InsertList(1, "test1", 6);
 InsertList(2, "test2", 6);
 InsertList(3, "test3", 6);
 InsertList(4, "test4", 6);
 InsertList(5, "test5", 6);
 PrintTest();

 DeleteList("test0");
 PrintTest();
 DeleteList("test3");
 PrintTest();
 DeleteList("test5");
 PrintTest();

 return 0;
}

추가로 읽으면 좋을 것