링크드 리스트(Linked List)

• 링크드 리스트 기본 구조
  

-노드는 정보(Data) & 다음 노드(Next)가 누구인지 저장하고 있다.

-링크드 리스트는 자료를 검색할때 앞에서 순차적으로 검색한다.

-Head노드와 End노드는 Data를 저장하지 않는 형식으로 구현(이건 편의상 이렇게 한것, 크게 상관은 없다).

        typedef struct _Node

        {

               char Data;             //데이터

               struct _Node *Next;    //다음 노드

        } NODE;

• 링크드 리스트 삽입

삽입할 데이터가 들어갈 위치를 찾고,

노드#01(앞 자리의 노드) 의 다음노드(Next) = 삽입노드

삽입 노드의 다음노드(Next) = 노드#02(뒷자리 노드)

삽입 종료

결론적으로 삽입한 노드의 뒷노드 들이 한칸씩 밀리게 된다.

void LinkedList::Insert(char data)

{

        //최초 검색 노드를 헤더로 설정

        NODE* indexNode = m_head;

 

        //현재 노드의 NEXT가 end노드면 반복문 중단

        for (indexNode; indexNode->Next != m_end; indexNode = indexNode->Next)

        {

               if (indexNode->Next->Data > data)

                       break;

        }

 

        //##중복된 데이터 삽입 금지##

        if (indexNode->Data == data)

               return;

 

        //새로운 노드 생성 및 메모리 할당

        NODE *newNode = (NODE*)malloc(sizeof(NODE));

 

        //새 노드에 데이터 저장

        newNode->Data = data;

        newNode->Next = indexNode->Next;

 

        //현재 노드의 Next로 새 노드를 할당

        indexNode->Next = newNode;

}

• 링크드 리스트 삭제

삭제할 노드를 찾고,

삭제할 노드의 전 노드(노드#01)의 다음노드(Next)를
삭제할 노드의 다음노드(삭제 노드의 Next)로 설정

그 후에 삭제할 노드를 삭제

삽입과 반대로, 삽입한 노드의 뒷노드 들이 한칸식 앞으로 당겨지게 된다.

void LinkedList::Delete(char data)

{

        //최초 검색 노드를 헤더로 설정

        NODE* indexNode = m_head;

        NODE* deleteNode = NULL;

 

        //현재 노드의 NEXT의 데이터가, 입력받은 데이터와 같다면 반복중단

        for (indexNode; indexNode->Next != m_end; indexNode = indexNode->Next)

        {

               if (indexNode->Next->Data == data)

               {

                       deleteNode = indexNode->Next;

                       break;

               }

        }

 

        //현재 리스트에 입력받은 데이터가 없다면 함수 중단

        if (deleteNode == NULL)

               return;

 

        indexNode->Next = deleteNode->Next;

         

//매모리 할당 해제 <= malloc으로 매모리를 할당 했으니 free 이용

        free(deleteNode);

}

• 전체 코드

#pragma once 

class LinkedList

{

private:

        typedef struct _Node

        {

               char Data;

               struct _Node *Next;

        } NODE;

       

private:

        NODE *m_head, *m_end;

 

public:

        LinkedList();

        ~LinkedList();

 

        void Insert(char data);

        void Delete(char data);

        void Print();

};

#include "stdafx.h"

#include "LinkedList.h"

 

 

LinkedList::LinkedList()

{

        m_head = (NODE*)malloc(sizeof(NODE));

        m_end = (NODE*)malloc(sizeof(NODE));

 

        m_head->Next = m_end;

        m_end->Next = m_end;

}

 

 

LinkedList::~LinkedList()

{

}

 

void LinkedList::Insert(char data)

{

        //최초 검색 노드를 헤더로 설정

        NODE* indexNode = m_head;

 

        //현재 노드의 NEXT가 end노드면 반복문 중단

        for (indexNode; indexNode->Next != m_end; indexNode = indexNode->Next)

        {

               if (indexNode->Next->Data > data)

                       break;

        }

 

        //##중복된 데이터 삽입 금지##

        if (indexNode->Data == data)

               return;

 

        //새로운 노드 생성 및 메모리 할당

        NODE *newNode = (NODE*)malloc(sizeof(NODE));

 

        //새 노드에 데이터 저장

        newNode->Data = data;

        newNode->Next = indexNode->Next;

 

        //현재 노드의 Next로 새 노드를 할당

        indexNode->Next = newNode;

}

 

void LinkedList::Delete(char data)

{

        //최초 검색 노드를 헤더로 설정

        NODE* indexNode = m_head;

        NODE* deleteNode = NULL;

 

        //현재 노드의 NEXT의 데이터가, 입력받은 데이터와 같다면 반복중단

        for (indexNode; indexNode->Next != m_end; indexNode = indexNode->Next)

        {

               if (indexNode->Next->Data == data)

               {

                       deleteNode = indexNode->Next;

                       break;

               }

        }

 

        //현재 리스트에 입력받은 데이터가 없다면 함수 중단

        if (deleteNode == NULL)

               return;

 

        indexNode->Next = deleteNode->Next;

 

        free(deleteNode);

}

 

void LinkedList::Print()

{

        for (NODE *node = m_head->Next; node != m_end; node = node->Next)

        {

               printf("%c ", node->Data);

        }

 

        printf("\n");

 

}